I have an idea, it is very likely not original but I have never read about it before. The problem is that Alice wants to ask Bob if he has a certain item in his database, but Alice doesn't want Bob to know what she is interested in. The solution is for Bob to run a bloom filter, adding items as normal. When Alice does membership query, she already knows the hash of the item she is interested in, and she knows the parameters of Bobs bloom filter. So Alice needs to do PIR to get each bit from the bloom filter where it will be set to 1 or 0 (1 for all if the item is in the database, probabilistically). So this is really cool but for it to be really really cool it needs a low bandwidth single bit PIR (not sequential block PIR). I only know one PIR scheme really well (the Pynchon Gate PIR), and it would work for this but it would be even worse than simply sending Alice the entire database (Since Alice's query size grows by 1 bit for each message in the database, and in this case each message is 1 bit). Does anyone know a good PIR protocol that would work well with this for low bandwidth anonymous membership query?