Okay here is a simple and theoretically sound demonstration that unfortunately will not work in practice. Alice is the user and she talks to Carol, and Bob is the server. Bob has a bloom filter. Okay, I am keeping this small because I need to write the entire thing out for demonstrative purpose. So Bob's blank bloom filter looks like this 00000 Alice sends a message through Bob to Carol tagged with "I am some secret between Alice and Carol". Bob uses a public algorithm to translate this tag into a series of bit positions, let's say position 0, 2 and 4. So now Bob sets the bits at those positions to be 1 in his bloom filter, to show (probabilistically) that a message with the tag "I am some secret between Alice and Carol" has been added to the database. This gives us a bloom filter that looks like this: 10101 Now Carol wants to know if Bob has a message to her that came from Alice. Since Carol knows "I am some secret between Alice and Carol" and she knows the public algorithm Bob used to translate this secret into a series of bits to set to 1 in his bloom filter, now Carol can determine probabilistically if Bob has that message in his database, by doing PIR to get the bit values at positions 0, 2 and 4 in Bob's bloom filter. This is where I need to diverge significantly, because I only know one PIR system very well, and it does not work well for this, and it assumes distributed copies of the database. So now let's assume that there are 2 Bob's , and neither cooperates with the other, and they both have the same bloom filter. So the Bob's databases look like this: 10101 and Carol needs to get position 0, 2 and 4. In Pynchon Gate PIR Alice would do this by first generating a random string with one bit for each message in the database. In this case each message in the database IS a bit, so it kind of sucks, but for example: 00101 And now Carol needs to make a second random *looking* string that causes the first string to Xor to 0 at all positions except for the position she wants. So first Carol wants position 0: 00101 0 XOR 1 = 1 0 XOR 0 = 0 1 XOR 1 = 0 0 XOR 0 = 0 1 XOR 1 = 0 so Carol now has the second string 10101. So now Carol has the two strings 00101 and 10101 and she sends one to the first Bob and one to the second Bob. The Bob's then XOR together messages at positions marked by 1 in the string the receive and send the result back to Alice. So the database is 10101: Bob1 gets 00101 1 XOR 1 = 0 Bob2 gets 10101 1 XOR 1 = 0 XOR 1 = 1 Carol gets 0 and 1 in response, 0 XOR 1 = 1, so the first bit in the bloom filter is set to one. I am not going to write this out all the way, but Carol does this for each of the bit positions associated with the message, and she finds that the result is 111 which means that probabilistically the message from Alice has been added to the list of messages.