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.