a better explanation of "header-swap is not perfectly indistinguishable"

[Zooko <zooko@zooko.com>]

I think that my earlier post "header-swap isn't perfectly indistinguishable" [1] 
didn't convey the issue very clearly.  Here I will restate it, hopefully more 
clearly and with more motivation why you should care.


Suppose I'm running a mix node.  100 messages come in.  Now I take the first 
one, and I process it (decryption, etc.).  Now assume (for sake of argument -- 
this assumption may need to be revisited afterward) that 50% of the messages 
that get sent through this network are two-way-anonymous, and 50% are sender-
anonymous.  So before I have begun processing this first message, I have a 50% 
chance of guessing which kind it is.  That is, I have no better knowledge of 
the kind of *this* message than I have just by knowing the global statistics 
of what kinds of messages are being sent.

During the processing I determine whether or not it is a swap message (this is 
a header-swap network).  Now I have more knowledge!  If it is a swap message, 
then I know that there is a 0.66 chance that it is a sender-anonymous message.  
If it is *not* a swap message, there is a 0.46 chance that it is a sender-
anonymous message!  Either way, I have learned something about the kind that 
it is.

Could I use this small amount of knowledge to combine with other knowledge in 
order to penetrate more deeply into the user's anonymity?  I think that this 
very much depends on some parts of the Mixminion design which are currently 
incomplete, such as the batching strategy and usage patterns (e.g. fragmenting, 
retrying, polling).

There is still a re-assuring kind of indistinguishability that header-swap 
does offer, though.  Suppose I take these 100 messages and I group them into 
swaps (there will be about 15) and non-swaps (there will be about 85).  Now 
I look just at the swaps.  I know that of these 15, approximately 10 of them 
are sender-anonymous and the remainder are two-way-anonymous, but processing 
the message does not give me *any* information to distinguish one swap message 
from another.  Likewise of the 85 non-swaps, I know that approximately 39 of 
them will be sender-anonymous and 46 of them will be two-way-anonymous, but 
I do not have any criteria for distinguishing one of the non-swap messages 
from another.


In sum, it is important to keep in mind that header-swap does *not* guarantee 
perfect indistinguishability, as defined like this:

Perfect Indistinguishability:  For a given message, a node's chance of 
correctly guessing whether the message is sender-anonymous or two-way-
anonymous after processing the message is not non-negligibly better than its 
chance of correctly guessing before processing the message.


Regards,

Zooko

[1] http://archives.seul.org/mixminion/dev/May-2002/msg00039.html