Securing privacy of "who communicates with whom" under Orwell-like conditions

Question

Assume that there is a big and powerful country with an information-greedy secret service which has backdoors to all internet nodes throughout the world which permit him to observe all exchanged data and all computations done inside the nodes.

Is it still possible under these conditions to ensure by mathematical means that this secret service cannot find out who communicates with whom, if one designs internet protocols in a suitable way?

My feeling is that the answer is likely "yes", but I am not working in cryptography. -- Probably a cryptographer can tell more.

Clarification (added after the first two answers): A good answer to this question could either consist of a description of a method together with substantial heuristic arguments in support of its suitability for the given purpose, or it could give substantial heuristic arguments that there is no such method. Mere handwaving arguments in favor of a positive or a negative answer do not answer the question.

On the other hand, the question is only meant to ask whether there are mathematical methods which in practice serve the purpose, just like in practice RSA can be used as a public key cryptosystem. It is not asking for a proof or disproof (of what precisely??), since this would not make sense.

Added after the first 5 answers (excluding deleted one(s)): The answers given so far mostly take the question as a soft question, which it is not. So far, Goldstern's answer comes closest to answering the question in that it proposes a concrete method -- but as it stands, it is still quite a way to go to get to anything practical.

Let me also emphasize that any transmission of data is "communication", including transmissions of publicly available webpages, downloads etc.. So firstly everybody has a lot of communication partners, and secondly efficiency is a very important concern.

Answer 1

Let us assume that everybody uses the same asymmetric encryption system (such as PGP), with keys that are so large that Big Brother cannot crack them.

If Alice wants to send a message to Bob, she encrypts it with Bob's public key and broadcasts it to everybody. All of Alice's friends will use their own private keys to decrypt the message, but only Bob will succeed. Big brother has no way of knowing who was able to read the message. (Unless Big Brother can look over Bob's shoulder, in which case nothing will work.)

Of course this system is a bit expensive, but only by some more or less constant factor. If everybody has 1000 friends, and sends a message per day to each of them, then I have to decode 1 million messages per day, only 1000 of which are for me.

EDIT: Now that the questions explicitly asks for a "practical" solution, here is a (slight?) improvement(?). Alice's messages will be pairs (x,y), where x looks like a large random number and y is the actual encrypted message. Whenever Alice writes to Bob, she could add a P.S. "My next message to you will be labeled with $\langle$_large random number here_$\rangle$. But please continue downloading all my messages, lest Big Brother could gain information about my conversation partners."

Answer 2

Let's assume that the secret service can view all transmitted messages and how they are routed, but has no access to anyone's private computer, since otherwise privacy clearly cannot be guaranteed.

There's still no way to mathematically guarantee privacy in any realistic way. One big problem is traffic analysis: the secret service can try to correlate when you send messages with when other people receive messages (this correlation needs to take place over time; an individual message is certainly not enough by itself, and this can only detect patterns of frequent communication, but that is already a problem). This doesn't even require extensive access to the internals of the network, but just the ability to monitor when users send or receive anything. Encryption will disguise the messages themselves, but not who is communicating.

Perhaps the most obvious way to try to foil traffic analysis is by introducing random delays into the system. If the delays are long enough, then it can make traffic analysis much harder, but delays cause severe problems of their own. (Real-time chat becomes impossible, and even e-mail becomes less useful as the delays grow.) And even with delays, making traffic analysis harder and less useful is not the same as making it impossible.

The only guaranteed way to defeat traffic analysis is to communicate all the time. If there's ever a period in which you do not send any messages, then the secret service will know that any messages received during that time either were sent before you stopped communicating or weren't from you. That's already a small information leak. Of course it might not matter in practice, but this is important if we want a mathematical guarantee. It is difficult to model what someone might guess in practice from small leaks, especially when combined with side information, so at a rigorous level all bets are off once information starts to leak.

So this means that if a group of people want to defeat traffic analysis rigorously, then they must all be communicating nonstop, using dummy messages if they don't have anything real to say. This is not generally considered realistic, and I don't know of any large-scale implementation.

Of course nonstop communication is not enough by itself: you also need a system for routing messages indirectly. If nonstop communication isn't an obstacle, then you can guarantee privacy using mix networks, in which a sequence of trusted servers anonymize and randomly permute messages. If all the servers are compromised, then the system becomes insecure, but otherwise it's OK.

In practice, people see constant communication as too costly for whatever benefit it offers. However, mix networks are a good idea nevertheless. The most widespread implementation is Tor. Tor does not provide mathematically guaranteed privacy, and it can be vulnerable to traffic analysis. However, it still provides far more anonymity than the internet does by default.

Of course then there are all sorts of meta-questions. For example, Tor is not very common among internet users. Does it actually attract attention and signal that Tor users are interesting targets for more careful investigation? I've got no idea.

Mathematics certainly plays an important role in addressing privacy concerns, and there's more it could contribute than it currently does. However, the practical constraints are significant, and privacy issues ultimately transcend any specific mathematical model. Sadly, there's no realistic scenario in which internet users could say "Do what you like, because mathematics guarantees our privacy."

Answer 3

Unconditional sender privacy is a well-known problem; D. Chaum - "The dining cryptographers problem" could be a reasonable starting point.

Having decided on existance, the question remains what price (in terms of communication complexity) could be considered acceptable to name it efficient enough (that is, practical).

"Dining" communication scheme had a impact and was extended in a number of ways, including an option for lost messages: M. Waidner, B. Pfitzmann - The dining cryptographers in the disco: Unconditional sender and recipient untraceability with computationally secure serviceability.

For a practical (depending on a computationally hard problem) solution, "remailer" was designed long ago for email. Papers of Lance Cotrell and Ulf Moeller there could be of interest. This was mentioned by Henry Cohn as "mix network" already.

Answer 4

Think of the handwritten letters for a moment. Suppose Alice wants to secretly communicate with Bob, so she writes the message in a secret language that only Alice and Bob know, puts it in an envelope, and ... writes Bob's address in plain letters on the top of the envelope before mailing it. Big Brother may not be able to read the message, but surely can read the address on the envelope: if Alice would try to encrypt Bob's address she would completely confuse the Post Office and the letter won't get delivered.

It's pretty much the same thing with Internet communications. Cryptography obscures the message, but not the destination: otherwise the routers won't be able to deliver the message. This leads to the negative answer under the assumption that Big Brother watches all the nodes.

However, Big Brother does not have access to all the nodes: quite a few of them are overseas. Therefore Alice can try to secretly communicate with Bob by bouncing her messages off offshore nodes.

Back to our handwritten letter analogy. Alice can put her letter addressed to Bob into another envelope addressed to her Russian friend Ivan and write Ivan's address on the exterior envelope. Ivan receives the letter, takes it out of the exterior envelope, and hands it letter to his friend Alexander. Alexander then forwards Bob the original letter. Assuming that Big Brother has no ears in Moscow and that Internet traffic is heavy enough between Moscow and whichever country Big Brother is watching over, it would be virtually impossible for Big Brother to detect Alice-Bob communications. There are too many letters coming back-and-forth between the countries to guess that the letter Bob receives from Alexander is the same one that Alice sent to Ivan.

This is pretty much how hackers try to conceal their identities, in my layman understanding. This is not always successful though: Big Brother may have ears in Moscow as well...

Answer 5

If Alice encrypts a a lot of messages with Bob's RSA public key, after a while they can be identified as being directed to Bob, since the encrypted value is a number from the multiplicative group $\mathbb Z/N\mathbb Z$ where $N$ is Bob's RSA modulus. By collecting enough of these ciphertexts, Big Brother can notice that they max out around $N$. That is enough to distinguish them from messages addressed to Charlie, who has a different modulus.

There is an old rectangularization trick to get around this (I'm not sure who invented it). Remember that Alice's message to Bob is $C=x^e\mod N$ where $e$ is a public encryption exponent. So Alice simply generates a large random number $R$ (say in the range $1\dots 2^{100}$) and sends $C+RN$ instead of just $C$. This is pretty close to uniformly random in the range of the maximum R. Bob simply mods out by $N$ to get rid of the random addition, before decrypting.

This scheme actually does leak a little bit of information, according to an old paper by Quisqater that I don't remember the title of. But IIRC it is pretty good for practical usage if the number of messages is reasonable.