# Can decoying provide security against traffic analysis?

Eve is an intelligence agency with the capability to scan all cleartext communications and do traffic analysis against encrypted communications.

There are n Alices, who each want to communicate secretly with some of the other Alices. So, they want the content of their communication to be secret, and the fact that they are actively trying to communicate secretly to be secret.

There are also N>>n Bobs, who disagree with mass surveillance but don't want to do anything which would give them any legal liability, such as transmitting illegal material (IE, they don't want to run TOR nodes).

So the Bobs decide to help by sending junk communications to other Bobs, which are indistinguishable from encrypted data. An individual Bob, if challenged, can show that his transmissions are junk, thus avoiding legal liability (NB - I Am Not A Lawyer). For the purpose of the exercise Eve in not allowed to challenge 'many' Bobs.

Eve wins if she can distinguish the Alices from the Bobs, or at least, as many Alices as possible. In particular, Eve may start by knowing at least some of the Alices; we don't want the security of the other Alices to collapse if she does.

A dumb approach is as follows: For each period of time, each Bob (or masquerading Alice) chooses another Bob(Alice) to communicate with at random from a public list. The Bobs send junk, the Alices send their encrypted message. In this scheme, the Alices are indistinguishable from the Bobs, but the Alices only obtain 1/N of the bandwidth of an individual communication, which is very low since N is large, and have very high latency, since they have to wait many time periods before they happen to communicate with who they want.

Is it possible to do better?

• Well, it seems to me that a natural generalization of your scheme is as follows. Construct a regular expander graph of size N. Choose a node at random and assign it to one of the Alices. Then from that node, start a self-avoiding random-walk of size n. Those nodes are assigned to the Alices. The Bobs are randomly assigned to the remaining nodes. Each node talks only to its immediate neighbor in the graph. Obviously the security of this scheme depends on the degree $d$ of the graph. – user8477 Jul 2 '13 at 21:30
• Now if Eve only identified Alices that are consecutive in the random walk, Eve doesn't have a chance much better than $1/(d-1)$ of identifying the next Alice. If on the other hand, she identified two Alices separated by a single node on the random walk, it will be much easier to find the middle node. In general, given two discovered Alices and the length $l$ of the path between them, the ability of Eve to determine the path between them depends on how many paths of length $l$ exist between these two Alices. This number grows exponentially with $l$. – user8477 Jul 2 '13 at 21:53
• @user8477: That looks like it could be part of the solution. One difficulty is that the protocol by which an Alice obtains a node needs to be indistinguishable from the protocol by which a Bob obtains a node. But we can define the means by which a Bob obtains a node however we want, so it ought to be doable somehow. Thanks. – Ealdwulf Jul 3 '13 at 10:10
• Could be relevant: www-users.cs.umn.edu/~hopper/public_key_steganography.pdf – Daniel Apon Jul 3 '13 at 17:59