<p>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.</p>

<p>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. </p>

<p>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.</p>

<p>A classic paper on this topic is <a href="ftp://ftp.inf.ethz.ch/pub/crypto/publications/Maurer93a.pdf">"Secret Key Agreement by Public Discussion from Common Information"</a> by Ueli Maurer. </p>

CC BY-SA 3.0
2016-08-31T15:15:19.363Z
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
CC BY-SA 3.0
2016-08-31T16:54:54.710Z
@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
CC BY-SA 3.0
2016-09-01T09:01:57.057Z
This is a nice (though not at all surprising) result.
domotorp
CC BY-SA 3.0
2016-09-02T01:42:58.077Z
@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
CC BY-SA 3.0
2016-09-02T09:13:06.573Z
@AdamSmith ah, well that takes care of my "natural" objection -- "who said?" -- Shannon did!
Aryeh
CC BY-SA 3.0
2016-08-31T09:39:03.153Z
2016-08-31T09:39:03.153Z
João Ribeiro
<p>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.</p>

CC BY-SA 3.0
2016-08-30T20:15:14.713Z
2016-08-30T20:15:14.713Z
domotorp
<p>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?" </p>

<p>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.</p>

CC BY-SA 3.0
2016-08-31T20:37:12.093Z
2016-08-31T20:37:12.093Z
Aryeh
<p>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.</p>

CC BY-SA 3.0
2016-08-31T00:24:09.723Z
2016-08-31T00:24:09.723Z
sysprog
<p>During a discussion I was wondering if it would be possible to design a theoretically secure key exchange.</p>

<p>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.</p>

<p>My question is:</p>

<p>Would this be possible and can this (yes or no) be proven mathematically?</p>

<p><strong>EDIT</strong></p>

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

<p>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?</p>

<p>After a week of thinking I think I found some proof:</p>

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

<p>I'm not sure if this proof is correct.</p>

<p>Can anyone tell me if it is correct?</p>

CC BY-SA 3.0
2016-08-30T19:05:03.033Z
Most cryptographic primitives are secure only against polynomially bound (probabilistic) attackers.
Martin Berger
<cr.crypto-security><key-exchange>
Is a theoretically secure key exchange possible?
Martin Rosenau
# Is a theoretically secure key exchange possible?

(Asked by: username_0 on 2016-08-30)

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?

**Tags:** cr.crypto-security, key-exchange
> **Comments:**
> **username_1**: Most cryptographic primitives are secure only against polynomially bound (probabilistic) attackers.  

---

## 4 answers

### Answer by username_2 on 2016-08-31. Score: 5

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"](ftp://ftp.inf.ethz.ch/pub/crypto/publications/Maurer93a.pdf) by Ueli Maurer.

> **Comments:**
> **username_3**: 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).  
> **username_2**: @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.  
> **username_4**: This is a nice (though not at all surprising) result.  
> **username_3**: @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.  
> **username_5**: @AdamSmith ah, well that takes care of my "natural" objection -- "who said?" -- Shannon did!  

---

### Answer by username_4 on 2016-08-30. Score: 2

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.


---

### Answer by username_5 on 2016-08-31. Score: 1

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.


---

### Answer by username_6 on 2016-08-31. Score: -3

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.


---

