Actually found a solution in the advanced crypto archives. I can break messages down into single packets and have the packets tagged with iteratively hashed contact strings. So after doing a key exchange with you we both generate two random strings associated with ourselves for each other, for example: My Public Contact String: a4244aa43ddd6e3ef9e64bb80f4ee952f68232aa008d3da9c78e3b627e5675c8 My Shared Private String: ac8406ff09a4e60a031a2db5340ba1a6e8154773c39b6b797e5b76dc00e41433 Your Public Contact String: 20b2ba0d04afc53a0e448e084286168e9e7b310dcc3c9d5895ece72208f457f6 Your Shared Private String: 31b78669a324805ea5d0d8593fce14cc6631b36b1bdd3105afadd6d83359fe3f Now assuming all message packets are 1kb, let's say you send me a 2 KB message. So the first packet is tagged with your original public contact string 20b2ba0d04afc53a0e448e084286168e9e7b310dcc3c9d5895ece72208f457f6 and the next packet is tagged with the hash value of your original public contact string concatenated with your private contact string: 49cf76433764ffd0064d312cc59958e3342e4e06a6b71d7c9244570c0b1e90ee etc for every message. When I receive messages I use this system: http://hms.isi.jhu.edu/acsc/privss/ and first I search for the first hash that I know will be concatenated to any messages from you, and I set my limit to be 1 returned packet (this protocol lets you set the maximum number of documents, in my case packets, to be returned by the search). After I get your first packet it has information letting me know there is a second packet, so now I do the keyword search for the next contact string, etc, until I have all of the packets you have sent to me so far. I do this for all of my contacts or until I hit a predefined amount of packets for a given cycle (period of time), and if the number of packets I receive so far does not equal the maximum number of packets I receive per cycle, I search for and receive padding packets up to my maximum. It still might be more efficient if I have an anonymous membership query system so I only search for messages that are actually waiting for me though, depending on how efficient I can make the anonymous membership query versus how efficient it is to search for keywords that do not map to anything in particular. This is actually pretty neat I can probably make it work for static content websites as well, and possibly even specialized interactive hidden services. This encrypted keyword search algorithm has really good bandwidth properties, the bandwidth required is the size of the message received plus a small bit of metadata, so to receive 1kb packet only costs a little over 1kb, and with this I can let the clients get messages part by part from throughout the database instead of having to get a sequential bucket like I would need to do with block PIR (which means there is no need for a semi-trusted nymserver that can tell who is communicating with who, in order to block all messages to a single user together so they can be received with block PIR).