3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Most cryptographic primitives are secure only against polynomially bound (probabilistic) attackers. $\endgroup$
    – Martin Berger
    Commented Aug 30, 2016 at 19:05

4 Answers 4

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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). $\endgroup$
    – Adam Smith
    Commented Aug 31, 2016 at 15:15
  • $\begingroup$ @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. $\endgroup$
    – João Ribeiro
    Commented Aug 31, 2016 at 16:54
  • $\begingroup$ This is a nice (though not at all surprising) result. $\endgroup$
    – domotorp
    Commented Sep 1, 2016 at 9:01
  • 1
    $\begingroup$ @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. $\endgroup$
    – Adam Smith
    Commented Sep 2, 2016 at 1:42
  • $\begingroup$ @AdamSmith ah, well that takes care of my "natural" objection -- "who said?" -- Shannon did! $\endgroup$
    – Aryeh
    Commented Sep 2, 2016 at 9:13
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
-3
$\begingroup$

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.

Improve this answer
$\endgroup$

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.