Provable Unlinkability Against Traffic Analysis already after O(log(n)) steps!

      Marcin Gomulkiewicz, Marek Klonowski, Miroslaw Kutylowski

We consider unlinkability of communication problem: given m users,  each
sending  a message to some destination, encode and route the messages so
that an adversary analyzing the traffic  in  the  communication  network
cannot  link  the  senders with the recipients. A solution should have a
small communication overhead, that is, the number of additional messages
should be kept low.

We consider security of the onion protocol against traffic analysis.  It
turns out that one source of difficulties is too strong adversary model.
In a recent work, Berman, Fiat  and  Ta-Shma  develop  a  new  and  more
realistic model in which only a constant fraction of communication lines
can be accessed by an adversary, but on the other  hand  the  number  of
messages  does  not need to be high and the preferences of the users are
taken  into  account.  For  this  model,  they  prove  that  with   high
probability  a  good  level  of  unlinkability  (expressed  as variation
distance between certain probability distributions)  is  obtained  after
O(log^5 m) steps of the onion protocol where m is the number of messages
sent.

In this paper we improve these results: we show that the same  level  of
unlinkability  is  obtained with high probability already after O(log m)
steps of the onion protocol. Asymptotically, this  is  the  best  result
possible.

On top of that, our analysis is  much  simpler.  It  is  based  on  path
coupling technique for showing rapid mixing of Markov chains.