Computational cryptography › Public-key encryption and key exchange › Classical number theory › Finite-field discrete log
Hardness assumptionKE: gives key exchangeTD: gives trapdoor functions

Computational DH

In plain words

From g^a and g^b, compute g^ab. That's exactly what an eavesdropper on a Diffie-Hellman exchange would have to do.

The idea: In Diffie-Hellman, Alice publishes g^a and Bob publishes g^b. Each raises the other's number to their own secret power, and both reach (g^b)^a = (g^a)^b = g^(ab). An eavesdropper sees g^a and g^b but has neither a nor b. CDH is the bet that combining two public halves into the shared secret is impossible without one of the private exponents.

Why it matters: Its hardness is what keeps classic Diffie-Hellman keys secret.

The details

On the map: in Fp*

Given g^a and g^b, compute g^(ab). If discrete log is easy, so is this: find a, then compute. Whether the two are equivalent in general is open[1].

CDH being hard is what makes classic Diffie-Hellman key exchange secure (KE)[2].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

About the tags

KE
This assumption gives key exchange on its own, so it needs more than one-way functions and falls if public-key encryption is impossible.
TD
This assumption gives trapdoor functions on its own (computable by anyone, invertible only with a secret), so it falls if trapdoor functions don't exist. Schemes built on it need not use a trapdoor: ElGamal doesn't.

References

  1. Ueli M. Maurer and Stefan Wolf. The Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms. SIAM Journal on Computing, 1999. doi:10.1137/s0097539796302749
  2. Whitfield Diffie and Martin E. Hellman. New Directions in Cryptography. Democratizing Cryptography, 1976. doi:10.1145/3549993.3550007