Diffie-Hellman Key Exchange

The Diffie-Hellman key exchange (1976) is a cryptographic protocol that allows two parties to establish a shared secret over a public channel without having previously communicated. Proposed by Whitfield Diffie and Martin Hellman, it solved a problem that had been considered fundamental to the impossibility of secure communication at scale: that any shared secret must be shared in advance through a secure channel, making security circular.

The protocol exploits the computational asymmetry of the discrete logarithm problem: multiplying a number by itself in a group is easy; recovering the exponent from the result is — as far as anyone has proved — computationally hard. Two parties can each choose a private exponent, exchange only the results of exponentiation, and compute a shared secret that neither transmitted. An eavesdropper who observes the exchange must solve the discrete logarithm problem to recover it.

What It Proved and What It Assumed

Diffie-Hellman demonstrated that the Key Distribution Problem could be dissolved rather than solved — that two parties need not share a secret in advance if they share a mathematical structure that is easy to compute in one direction and hard to reverse. This is a conceptual breakthrough of the first order.

But the security proof is conditional: it assumes the discrete logarithm problem is hard. This has not been proved. Shor's Algorithm demonstrates that a quantum computer could solve it efficiently. The foundational promise of Diffie-Hellman — that asymmetry is a permanent feature of these mathematical structures — remains an open question in complexity theory.