At 8:57 AM 01/12/95, Wei Dai wrote:

Alice is sending mail to. After the first day, she can eliminate about half of the remailer users from the list of possible targets, because they, like the the random user above, received a mail even though Alice didn't send one out during the collection period of that batch. Now, since Eve can eliminate on average half of the list every day, Bob will be the only person left on that list after about (log base 2 of one million) = 20 days.

Suppose Alice sent out some different numbers of cover e-mail: [...] 3 log base 1 of 1,000,000 = infinity!

Yeah, I think it made sense. Let me try to rephrase what you are saying in English rather then math, to see if it's still what you are saying. 1) Attacker Eve wants to figure out who Alice is sending mail to. 2) She can weed people out by noting 'collection periods' where Alice sends mail, but certain people don't receive any mail, and eventually arrive at Bob. 3) If Alice sends mail out in _ever_ collection period, perhaps just to the bit bucket, this method won't work, because there won't be any periods where Alice doesn't send mail out. Hmmm. The basic idea here is simply that you should send out lots of cover mail, at least one piece in every collection period, to prevent this kind of attack. Best, a random number of cover pieces, but at least one every collection period. Several thoughts: 1) If Alice and Bob are both corresponding with many people, things get more complicated. I tried to model it similarly to the way you modeled your simpler situation, but got confused quickly. This would be a good thing to look at. Alice sends and receives mail to several people other then Bob, and same with Bob. I'm not sure how this changes things, if at all. 2) In real life, it's more likely for an attacker to want to discover Alice knowing Bob then it is for him to want to discover Bob knowning Alice. It's Alice who is being anonymous here by using the anonymous RemailerNet, of course. I don't think this changes things either, but it's something to keep in mind.