# Is a theoretically secure key exchange possible?

During a discussion I was wondering if it would be possible to design a theoretically secure key exchange.

In other words: If it is possible to design a key exchange (like Diffie–Hellman) where the communication could not be decrypted by an eavesdropper even if he had a computer with infinite speed and memory.

My question is:

Would this be possible and can this (yes or no) be proven mathematically?

EDIT

After having read some of the answers I want to improve my question a bit:

Is it possible that some sender is sending some information to a receiver over an (insecure) channel not having any common keys nor access to a common source of randomness (or similar) in a way that it is not theoretically possible to "decrypt" the actual information from data transferred over the channel?

After a week of thinking I think I found some proof:

• A is some data of the sender (such as a public/private key pair)
• B is some data of the receiver
• Ds is the data sent by the "sender"
• Dr is the data sent by the "receiver"
• Fn are mathematical functions
• M is the "cleartext message" to be encrypted
• The data sent by the "receiver" depends on the data received from the "sender" and from the private data B: Dr = F1(B,Ds)
• The data sent by the "sender" depends on the data received from the "receiver", private data and the message: Ds = F2(A,M,Dr)
• "Theoretically security" would mean that two different messages M exist which can result in the same data of the set (Dr,Ds); otherwise an attacker could search for all sets (A,B,M) which lead to a given data of (Dr,Ds) - and would know the only possible value of M
• Because of Ds = F2(A,M,Dr) this would mean that different values of the set (A,M) must exist that lead to the same Ds (when Dr is given)
• This would mean that the receiver (not having any additional information about A but the information contained in Ds) would also not be able to decrypt the message

I'm not sure if this proof is correct.

Can anyone tell me if it is correct?

• Most cryptographic primitives are secure only against polynomially bound (probabilistic) attackers. – Martin Berger Aug 30 '16 at 19:05

I believe you are talking about the existence of information-theoretically (unconditionally) secure key agreement schemes. You can prove that such schemes cannot be achieved with only authenticated channels from Alice to Bob and Bob to Alice.

Nevertheless, if Alice, Bob, and Eve are in possession of some sort of correlated randomness, then it may be possible to construct such a scheme.

One such example is when a satellite broadcasts several random bits, and Alice, Bob, and Eve receive the bits through different binary symmetric channels with certain error probabilities. One can prove that, in this case, information-theoretical key agreement is possible, even when Eve's error probability is much lower than Alice's and Bob's.

A classic paper on this topic is "Secret Key Agreement by Public Discussion from Common Information" by Ueli Maurer.

• Perhaps a simpler place to start is Shannon's proof that encryption schemes for k-bit messages require a key of at least k uniformly random bits. You can find one version of this proof in information theory books (e.g., Cover and Thomas) and even more elementary versions in good crypto textbooks (like Katz and Lindell). – Adam Smith Aug 31 '16 at 15:15
• @AdamSmith Shannon's proof is indeed a softer introduction to this type of proofs in cryptography. One should make it clear, though, that while it tells us how much uncertainty there should be in our secret key, it does not tell us anything about how or if we can obtain such a key. – João Ribeiro Aug 31 '16 at 16:54
• This is a nice (though not at all surprising) result. – domotorp Sep 1 '16 at 9:01
• @JoãoRibeiro You are right that Shannon's proof, and the one in Katz-Lindell, applies to noninteractive encryption schemes. One can extend the information-theoretic analysis to interactive protocols (in particular, to key agreement). I am not sure if there is a textbook-quality treatment of this anywhere. Maurer's paper (which you cite in your answer) is certainly a good starting point for further reading. – Adam Smith Sep 2 '16 at 1:42
• @AdamSmith ah, well that takes care of my "natural" objection -- "who said?" -- Shannon did! – Aryeh Sep 2 '16 at 9:13

No. What is a key exchange? Both parties have a private random sequence (that they've generated for themselves) plus possibly some public random sequence (that the eavesdropper can also see). Then they want to communicate so that the other party learns something about the probability distribution of their sequence that the eavesdropper doesn't. But whatever a party says just updates the probability distribution of their random sequence for anyone who sees their message.

Let me elaborate on @domotorp's answer, since a natural first objection might be, "We're talking about secure key exchange -- who said anything about requiring randomness?"

The point is that public-key cryptography requires an asymmetry in the difficulty of computing a function: it's supposed to be hard to compute except if you have a special "key". It's easy to define functions that are hard (or even impossible) to compute for everyone -- there are more such functions than algorithms. It's also easy to define functions that are easy for everyone. It's the asymmetry that requires a lot of ingenuity -- and it fundamentally depends on the computational limitations of the adversary.

While it is possible in theory to construct a theoretically unnreakable cipher, e.g. a one-time pad with pad content not identifiably nonrandom, it is not possible to prove theoretically that the key exchange was secure, because whether there was a covert channel observer that surreptitiously copied the key is an empirical matter.