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.