Mobile mixing
Marcin Gogolewski, Miroslaw Kutylowski, Tomasz Luczak
We consider a process during which encoded messages are processed
through a network; at one step a message can be delivered only to a
neighbor of the current node; at each node a message is recoded
cryptographically so that an external observer cannot link the messages
before and after re-coding. The goal of re-coding is to hide origins
%MKU destinations of the messages from an adversary who monitors the
traffic. Recoding becomes useful, if at least two messages
simultaneously enter a node -- then the node works like a mix server.
We investigate how long must be the route of messages so that traffic
analysis does not provide any substantial information for the adversary.
Anonymity model we consider is very strong and concerns distance between
a priori probability distribution describing origins of each message,
and the same probability distribution but conditioned upon the traffic
information. We provide a rigid mathematical proof that for a certain
route length, expressed in terms of mixing time of the network graph,
variation distance between the probability distributions mentioned above
is small with high probability (over possible traffic patterns).
While the process concerned is expressed in quite general terms, it
provides tools for PROVING privacy and anonymity features of many
protocols. For instance, our analysis extends results concerning
security of an anonymous communication protocol based on onion encoding
-- we do not assume, as it is done in previous papers, that a message
can be sent directly between arbitrary nodes. However, the most
significant application now might be proving immunity against traffic
analysis of RFID tags with universal re-encryption performed for privacy
protection.