header-swap isn't perfectly indistinguishable (was: problem in 3.2 "Replies")

[Zooko <zooko@zooko.com>]

 David Hopwood wrote:
>
> I'm not convinced there is really any problem with forcing all chains to be
> the same length; the extra hops for forward messages still contribute to
> anonymity, so they are not wasted.
[...]
> Consider any synchronous design (e.g. a pure cascade, or a batch synchronous
> design [...]
> Note also that increasing the path length in this case does not have much
> effect on latency, which is primarily determined by the batch period (and how
> many times a message is delayed to the next batch). It does have an effect on
> reliability for forward-only messages, but the reliability is no worse than
> for replies.


I've written a message here [1] showing how my old two-payloads technique [2] 
is actually more efficient than two-headers-swap when the latter requires 
doubled-path-lengths.  Two-payloads also has better latency and reliability, 
of course, due to having paths one half as long.  (I especially commend to 
your attention the table at the end which shows how the reliability of both 
two-payloads and header-swap are very poor.  I believe this to be a big 
problem that we have not yet addressed.)

(By the way, for mutually-anonymous messages *any* technique would require 
2K hops -- K of them chosen by one anonymous party and K of them chosen by the 
other.  So all of the comparisons in that message in which header-swap suffers 
twice the path length of the others do *not* apply to mutually-anonymous 
messages.)

In addition, my recent realization about statistical distinguishing [3] 
tells me that header-swap doesn't offer indistinguishability as well as two-
payloads does.

From your comments about latency it appears that you are envisioning a 
batching strategy that enforces a very high added constant latency to each 
message.  I hope that is not necessary, as I wish to use Mixminion for 
applications with latency on the order of minutes, not of days.

But in any case, it appears to me that the batching strategy interacts 
significantly with the indistinguishability technique in terms of latency, 
reliability, and anonymity.

So personally I am shelving my ideas and preferences about 
indistinguishability techniques until I grok batching strategies.

(But I will admit that plain-old-distinguishable remains my secret favorite, 
followed by own invention "two-payloads".)

Now I have quite a lot of reading to do about batching strategies and attacks 
on them.  :-)

Regards,

Zooko

Zooko.Com -- Security and Distributed Systems Engineering

[1] http://archives.seul.org//mixminion/dev/Apr-2002/msg00089.html
[2] http://archives.seul.org//mixminion/dev/Apr-2002/msg00013.html
[3] http://archives.seul.org//mixminion/dev/May-2002/msg00039.html