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?
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:
Ais some data of the sender (such as a public/private key pair)
Bis some data of the receiver
Dsis the data sent by the "sender"
Dris the data sent by the "receiver"
Fnare mathematical functions
Mis 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
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
Mexist 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
- 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
- This would mean that the receiver (not having any additional information about
Abut 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?