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

Computational DH

In plain words

The elliptic-curve version of "from two public halves, recover the shared secret."

The idea: Diffie-Hellman with curve points instead of big numbers: Alice sends aP, Bob sends bP, and each multiplies what they received by their own secret to reach the same point abP. The bet is that seeing aP and bP doesn't let anyone else reach abP.

Why it matters: Keeps elliptic-curve Diffie-Hellman key exchange secret.

The details

On the map: on the curve

Given aP and bP on a curve, compute abP. Easy if ECDLP is easy. It is the assumption behind elliptic-curve Diffie-Hellman key exchange (KE)[1, 2].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Everything that falls with it (8 boxes)

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. Whitfield Diffie and Martin E. Hellman. New Directions in Cryptography. Democratizing Cryptography, 1976. doi:10.1145/3549993.3550007
  2. 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