Can cryptography be used to hide routing information from the router?

Question

If Alice wants to talk to Bob and she has to involve a third party system run by Carol to establish, and possibly maintain, communications, then Carol knows that Alice and Bob communicated with each other.

Chuck sneaks into Carol's exchange, and now knows that Alice and Bob are talking to each other.

Carol decides to start a new exchange with new technology, with the primary purpose of never knowing who is talking to who, and she needs to figure out how to do this.

If Carol runs an exchange that is unlimited communications (meaning no per-transaction billing) then she has no business need to know who talked to who, or for how long, as long as both ends are authenticated to her servers.

So the question is:

Is there a way for Carol to design her new network/exchange/endpoints so that her equipment can route and connect two individuals on that service without knowing who is talking to who?

Obviously the service would need to be handling a lot of traffic, and the traffic would need small random delays so you couldn't simply watch the time that Alice puts in a request to the time another request is output and assume that's her outgoing connection.

But I still don't see a way to handle the actual routing and call connection in a way that prevents anyone from seeing who is communicating to whom.

I'm wondering if there's some cryptographic principle or method that might help with this. So far all my attempts result in one point in the process where both the sender and recipient are known.

Answer 1

The solution is called onion routing; the gist of it is that there are a number of anonymising servers; when Alice wants to send a message to Bob, she picks a random route through a number of the servers; she then repeatedly encrypts the message for each hop, and sends the encrypted message (which states only the first hop in the clear) to the first server.

The first server then decrypts the message, which reveals the second hop. It then sends the message to the second hop (batching it with a number of other messages, so someone cannot correlate incoming and outgoing messages).

The second server, again, decrypts the message, which reveals the third hop; and then batch-forwards it to the third hop.

This continues until we get to the last server, which decrypts the message, which reveals the actual destination (Bob) it then batch-forwards it to B0b.

Bob then decrypts the message, this reveals the message that Alice originally sent.

There are a number of subtle points; these points are well studied in the literature.

Now, because of all the above 'batch-forwarding', this doesn't work for real-time communication; for messages that don't mind some unpredictable delay, it's workable.

Answer 2

Anonymity is indeed hard.

How practical does it have to be? There's a trivial solution which is to broadcast everything. That way Carol can make correlations based on the time of messages but otherwise cannot know the destination of each message. The messages can be filtered by the recipient based on an encrypted destination identity that only they can decrypt.

Wireless communication is intrinsically broadcast in this way. It reveals information about the location of the sender but all that is known about the recipient is that it is presumably within the area where reception is possible.

You cannot escape the need for a router to know the next hop in the chain, so it has to know something about the destination of each message. There's a solution which is to use multiple routers and assume that the risk of compromise is mostly independent on distinct routers, so that it is highly unlikely that all the routers in a chain will all be compromised. The route must be confidential from all routers involved except for each router knowing what the next hop after it is. A concrete implementation is Tor.

You can get useful results with as few as two routers: an incoming router which strips off all information about the sender, and an outgoing router which decrypts the destination. This setup resists a compromise of one of the routers (but breaks down if both are compromised).

In a broadcast scenario, there is some flexibility to reduce the amount of data that must be broadcast at the expense of some anonymity. For example, instead of long messages, broadcast only short messages containing a message unique identifier (encrypted, and unguessable-random), and let recipients download the messages whose identifier they obtain.

Answer 3

This scenario is the motivation of the research domain with the catchy name “functional encryption”. There is a presentation in “Functional Encryption: Definitions and Challenges” by Dan Boneh and Amit Sahai and Brent Waters.

I have a function. A third party can evaluate the function on encrypted data and learn the result in cleartext. This is comes in contrast with any homomorphic encryption scheme in which the result is encrypted and thus useless for the routing scenario you mentioned.

Answer 4

Once they are practical, you may use , homomorphic encryption too ! Since it allows computations over encrypted data. the routes can be encrypted but still the traffic can be routed