From: "Wei Dai" <weidai@eskimo.com>
Date: Wed, 25 Jan 95 16:58:19 PST
To: anonymous-remailer@shell.portal.com
Subject: Re: Remailer
Message-ID: <199501260057.AA15184@mail.eskimo.com>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

> From: Louis Cypher (alt.anonymous.messages)
> 
> Define "f" as the fraction of remailer using population sending a 
> message in a given tick. This is also the probability that any 
> individual will send a message in a given tick. The probability of a 
> given pair of corespondents in a given tick is
> 	f^2
> The probability of a pair of corespondents occurring m times in n 
> ticks is
>         m
> p= 1 - Sum [(f^2)^i (1 - f^2)^(n-i) n! / (i! (n-i)!)]
>        i=0

Hmm... this sounds very similar to the results of my 
analysis which I posted yesterday (Subject: analysis of Chaum's MIX
continued), which I think is slightly more general.

> Lets put some numbers in there.... [deleted]
> So, for a remailer using population of 10,000 you had better send less 
> than 5 messages per month to your accomplice.  This only gets worse 
> the longer you keep it up. You can not send 4 per month, month after 
> month.

Plugging these numbers into my formula, the "threshold of
tracibility" comes out to be 4 messages.  This is probably due to the 
fact that I used a normal approximation for the binomial 
probability (the p in the above formula).

The general conclusion however is the same: unless most 
users send a lot of dummy mail to each other, a Chaum type 
mix will not provide very good untracibility.

The other possible way to increase untracibility is to 
decrease the number of batches per unit time (i.e., 
increase average latency).  This implies that with a 
Chaumian mix, there is an unavoidable tradeoff between 
untracibility, bandwidth (i.e., how much dummy mail has to 
be sent), and latency.

Wei Dai


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBLybywzl0sXKgdnV5AQF0+AP/e5sKTVt5plvGydmILm+cBF14q6IJttDJ
U0Es21jMH0hYPreiRwfUXwMc+bLs/RfTdmGBr0KUPHow0khlzfGHjU8ZKOMknSI/
+qvqHlMRPDfvKnp244qsQUJ1UmLAezeNObO4OMbejWbRRGu+Dd1iEeBpgnFOh0bH
6grf4VupdpU=
=+Um1
-----END PGP SIGNATURE-----