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?
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.