Ghost Train for Anonymous Communication

                      Przemyslaw Blaskiewicz, Miroslaw Kutylowski,
                       Jakub Lemiesz, Malgorzata Sulkowska

We study the problem of hiding communication: while it is easy to encrypt a message 
sent from Alice to Bob, it is hard to hide that such a communication takes place.  
Communiaction hiding is one of the fundamental privacy problem, especially for dynamic networks 
with an adversary having a~complete view of the traffic and  controlling a large number of nodes.   

Following the Beimel-Dolev's buses concept and drunk motorcyclist protocol by Young and Yung 
we propose a new theoretical concept  called \textit{Ghost Train}. The ghost trains are travelling 
at random through the network just as drunk motorcyclists and one version of Beimel-Dolev buses. 
However, there are no bus seats or motorcyclists holding a ciphertext. 
Instead, hidden messages are repeatedly inserted into the ghost trains.
The trains are not generated by the senders, once created they travel forever, 
and hold messages in the way that the older messages gradually decay and are replaced by new messages 
inserted into the train. The communication pattern (a train route) is random and stochastically 
independent from the existing sender-destination pairs, thus the protocol is fully oblivious. 
Additionally, it works for dynamic networks where the nodes can join and leave the network 
(unlike the Beimel-Dolev solution) and yet it is not possible to indicate the origin 
of any given package (unlike in the drunken motorcyclist protocol).

Our protocol is based on basic tools (Bloom filters, PRNGs) and a novel concept of 
inserting many ciphertexts on the same place and their decay. 


Keywords:
Anonymous Communication; Traffic Analysis; Random Walk; Bloom Filter; Shared Keys

accepted for SpaCCS 2016
to appear in LNCS