I want Alice to be able to ask Bob if he has a message for her, without Bob knowing which messages Alice is looking for. The easiest solution is for Bob to tell Alice all of the messages he has. This is great unless there are 500,000 users sending 10 messages a day each tagged with 128 bit string. Now the meta data alone is about 76 megabytes, and there are 500,000 users so Bob now takes about 36 terabytes of bandwidth a day just letting everybody know the metadata of which messages are available. If everybody checks for 1,000 messages a day and the PIR cost is even 512 bits per query, 500,000 * 1,000 * 512 = 29.8 gigabytes of bandwidth for all clients to check for so many messages. But the results are dependent on the cost of the PIR, and the only PIR I know would not work well for this at all (only theoretically would it work, in practice it would be absolutely stupid). Essentially you and I do ECDH key exchange and come to a shared secret. We communicate with each other through Bob by tagging messages with our shared secret prior to uploading them to Bob anonymously. Now you know the message tags that indicate that a message is waiting for you, but you cannot ask Bob "Hey do you have this message tag?" because then Bob knows what message will be for you. So you need a way to ask Bob if he has something without him being able to tell what you are asking if he has. The solution could be for Bob to keep a bloom filter. Bloom filter is essentially a block of bits , a fresh bloom filter all bits are set to 0. When Bob gets an item he takes its hash value, translates the hash value into a series of numbers that map to a bit position in the grid, and Bob sets the bit positions in the grid to be 1. If all bit positions mapping to an inserted item are set to 1 then you can query the bloom filter and see that the message has probabilistically been added. So now we have Bob with his bloom filter, and he gets these message tags when people send messages to him for others to download and he puts the tags in his bloom filter. Now I can ask Bob if he has the message by doing PIR to get the bits at the positions in his bloom filter (Since I know the message tag I know the bits that will be set to 1 if the message has been added, since I also have the public parameters of Bob's bloom filter). If after I do PIR and get all of the bits they are all 1, then I know Bob has my message, if any of them are 0 then I know Bob doesn't have my message, but in either case Bob cannot tell which messages I asked him if he has. And now Bob doesn't need to send me and 500,000 other people 76 megabytes a day.