Re: [freehaven-dev] mix-acc: witnesses provide linkability in rare case

[Roger Dingledine <arma@mit.edu>]

On Tue, May 01, 2001 at 07:33:46PM +0100, David Hopwood wrote:
> > Speaking of which, does our deadline notion itself increase linkability?
> > I believe it does.
> 
> Why?
 
One of the benefits that mix-nets get over low-latency streams is the
ability to delay and batch messages to reduce the amount of linkability
between messages and senders/receivers: Eve cannot link messages as
easily if they are batched/delayed/reordered well.

Yet some of the power of batching/delaying/reordering comes in having
a number of messages at once. With only one message, these techniques
are not useful.

There is a tradeoff between security and usability: the system is more
useable if messages come out soon after they come in, but the system is
more secure if messages come out long after they come in.

In a normal mix-net, some mixes will provide low security (high usability)
and some high security (and correspondingly high latency). Senders can
choose the mixes they use based on their security requirements (and
also considering that secure but less usable mixes may offer a lower
anonymity set -- few people use them).

But in our modified mix-net, all the messages come in to the mix and
must come out before deadline, else the mix has 'failed'. So this produces
a cap on the amount of security a mix can provide, but leaves the number
(or frequency) of incoming messages the same.

Anyway, I think I've just convinced myself in both directions of the
"are witnesses anonymity-breaking" argument. DavidM/Mike, want to chime
in here?

Thanks,
--Roger