Re: traffic analyzing Chaum's digital mix

[Wei Dai <weidai@eskimo.com>]

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

On Fri, 20 Jan 1995, Hal wrote:
 
> Another interesting aspect of your analysis is the possible role of
> latency.  Earlier I had thought of latency as primarily a way of doing
> mixing, an alternative or addition to batching which mixes messages
> without holding them up quite as much.  But in terms of this in/out
> analysis latency could play a part in blurring the batch boundaries,
> adding more uncertainty and making the job of the analyst harder so he
> would need more data to establish his scores.

Latency (by which I take to mean some kind of random delay) will 
probably make the analyst's job harder, but I suspect not by much.  The 
method of analysis I outlined earlier can be modified to apply to mixes 
that use random delay instead of batching as the method of mixing.  
Instead of adding up the number of times Alice's message to the mix is 
followed up by a message from the mix to a user, take the sum of the 
probabilities that each message the user receives is from Alice.

So you would do something like this for each user of the mix:
	  message #    probability this message came from Alice
		1                       0.000135
		2                       0
		3                       0.000012
		4                       0.004332

		     SUM:               0.004479

Each probability can be calculated from the statistical distribution of 
the delay time, the length of time between the Alice sending the last 
message to the mix and the user receiving a message from the mix, and 
the timing and number of other messages sent by the mix around this 
period of time.

This method is more general than the one I talked about earlier, since 
it is equivelent to the former method when you apply it to a batching 
mix (that is, the original Chaumian mix).

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

iQCVAwUBLyB8YDl0sXKgdnV5AQHZxAQApKQgYfhGhBu+3QXzCEi1/3B55jgdHa6X
6ZeZQWZYjEhLXnOA6Z4SEHKjOVYpMHb+VkvW+vG+QZVR+cjajstg6HczwEguXjSX
ObTm2gaQGRFaUOD+0fUEWFxxkqNxYEL0hRAesX3TyGYI/MQ4WzysweCzCk75+Dm2
glKeTRgnFKo=
=36jW
-----END PGP SIGNATURE-----