Provable Anonymity for  Networks of Mixes
               Marek Klonowski and Miroslaw Kutylowski



We  analyze  networks  of   mixes   used   for   providing   untraceable
communication.  We  consider  a network consisting of k mixes working in
parallel and exchanging  the  outputs  --  which  is  the  most  natural
architecture for composing mixes of a certain size into networks able to
mix a larger number of inputs at once.

We prove that after O(log k) rounds the network  considered  provides  a
fair  level  of  privacy  protection  for  any  number  of  messages. No
mathematical proof of this kind has been published before. We show  that
if at least one of server is corrupted we need substantially more rounds
to meet the same requirements of privacy protection.