[Cryptography] multi-key encryption of "meta" data

[John Kelsey]

Imagine a completely trusted mail server used by everyone.  If you had such a thing, you could get what you want by having a protocol wherein each user connected once every day to the mail server over an encrypted channel (TLS), sent up a fixed amount of information, and pulled down a fixed amount of information.  No outsider would be able to determine whether you were sending/receiving any email--all they'd know would be that you *could* have sent/received email.  

The two ways I can imagine making that work without a trusted mail server are either:

a.  Come up with a protocol so that the mail server doesn't know who got what.  (This looks hard to me--it's related to searching on encrypted data, but looks harder than that to me.)  

b.  Replace the single mail server with some kind of network of nodes controlled by different entities.  What we know how to do right now is build a remailer network with some kind of longish delay, along with some kind of service that lets users drop information and chaff into/out of the system.  

--John