Rough run Oblivious Bloom Intersection
Download as PPTX, PDF
0 likes353 views
1. The document describes the Oblivious Bloom Intersection protocol for privately comparing sets between a client and server. 2. The client builds a Bloom filter from its set and the server builds garbled Bloom filters (GBFs) from its set using cryptographic techniques. 3. Oblivious transfer is used to retrieve bits from the GBFs to reconstruct the client's Bloom filter, revealing any intersecting elements without revealing non-intersecting elements.
Rough run Oblivious Bloom Intersection
- 1. Oblivious Bloom Intersection (Rough Run) -Aditya M. Mehta & Takai Wu
- 2. Step 1 : Form Bloom Filter from data at Client and Garbled Bloom filter from data at Server Input at Client , set C = 5,7 Input at Server , set S = 3,5,7,18,98,67 Assume that the sequence of hash algorithms are exchanged between the two parties, H = {MD5,MD4,MD2,SHA1}
- 3. At Client Build Bloom Filter BF 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 Initial value of BF 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 After Adding 1st Element 5 to BF After Adding 2nd Element 7 to BF 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0
- 4. How to Build GBFs
- 5. At Server Build GBFs The server Builds GBFs for set S, lambda = 4, and the no of shares is 4 Initial GBFs 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 After Adding 1st element 3 Index values = 2, 7, 9, 0 First emptySlot encountered = 2 Random no R1=2131 ,R2= 7210, R3 = 5117 Store R1, R2 and R3 at 7,9 and 0 respectively So store at position 2 = Secret xor R1 xor R2 xor R3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5117 0000 1927 0000 0000 0000 0000 2131 0000 7210 0000 0000 0000 0000 0000
- 6. Similarly we add rest of the elements to GBFs Adding 2nd element Adding 3rd element Adding 4th element 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5117 2151 1927 6575 0000 0000 6573 2131 5100 7210 2144 0000 7193 0000 0000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5117 2151 1927 6575 0000 0000 6573 2131 0000 7210 2144 0000 0000 0000 0000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5117 2151 1927 6575 0000 0000 6573 2131 0000 7210 2144 0000 7193 0000 0000
- 7. Contd. Adding 5th element Adding 6th element 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5117 2151 1927 6575 0000 6649 6573 2131 5100 7210 2144 0000 7193 0000 0000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5117 2151 1927 6575 2488 6649 6573 2131 5100 7210 2144 7601 7193 0000 0000 Insert Random lambda bit values at all null positions . Refer line 22 in Algorithm 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5117 2151 1927 6575 2488 6649 6573 2131 5100 7210 2144 7601 7193 3451 8912
- 8. Step 2 - OT
- 9. Contd. Create GBFs2 After Algorithm completes, what GBFs2 looks like 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 3221 2151 1927 6575 1231 5423 6573 2131 8797 7210 2144 7682 7193 9687 4352 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5117 2151 1927 6575 2488 6649 6573 2131 5100 7210 2144 7601 7193 3451 8912 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0
- 10. Step 3 - Query
- 11. Contd. For 5 Recovered = 2144 xor 2151 xor 6575 xor 6573= 5 .True matches For 7 Recovered = 2131 xor 7193 xor 2151 xor 7210 = 7 True matches