2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – user8477
    Commented Jul 2, 2013 at 21:30
  • 1
    $\begingroup$ 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$. $\endgroup$
    – user8477
    Commented Jul 2, 2013 at 21:53
  • $\begingroup$ @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. $\endgroup$
    – Ealdwulf
    Commented Jul 3, 2013 at 10:10
  • $\begingroup$ Could be relevant: www-users.cs.umn.edu/~hopper/public_key_steganography.pdf $\endgroup$
    – Daniel Apon
    Commented Jul 3, 2013 at 17:59

1 Answer 1

Reset to default
-1
$\begingroup$

How can Bobs prove that their transmissions are junk? Given that the transmissions can be encrypted using information theoretically secure one-time pads (OTPs), it is not possible to prove that they are not significant messages. Even if the messages from Bobs would be assumed to be encrypted with a single cipher of a good grade (AES?) it would be very hard to show that there is no key that decodes a given message into meaningful content, because, assuming such a method would exist, it would simultaneously show that the cipher (AES?) is broken. A statistical method showing that a message from a Bob cannot be an AES-encrypted message would correspond to a distinguisher for AES and that would also signal that it is a weak cipher.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I should have said that Bobs generate their junk using a stream cipher. So, a Bob can prove that his total transmissions have kolmogorov complexity of 'keysize' bits. Sure, a Bob can't prove that he's not leaking the secret key of Bank of America, but he can show that he's not transmitting most kinds of illegal or secret material, which are bigger than a few hundred bits. $\endgroup$
    – Ealdwulf
    Commented Jul 2, 2013 at 16:49
  • $\begingroup$ That's a good point, you're right. I implicitly thought about sending random junk data, but obviously it doesn't need to be random. $\endgroup$
    – antti.huima
    Commented Jul 2, 2013 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.