Computational cryptography › Public-key encryption and key exchange › Classical number theory › Finite-field discrete log
Hardness assumption

Discrete log in Fq*

In plain words

Given g and g to the power x, using ordinary big numbers, find x. Believed hard, but it needs much bigger numbers than the elliptic-curve version.

The idea: Pick a big prime p and a base g. Raising g to a secret power x and keeping the remainder after dividing by p is quick even for huge x. Going back from the result to x is the hard direction. Toy example: 5⁶ = 15,625 leaves 8 after dividing by 23. Given only the 8, you'd have to search for the 6. At real sizes, primes of about 900 digits, even the best known methods are hopeless. Your private key is x and your public key is the remainder, so you can publish one without revealing the other.

Why it matters: The original Diffie-Hellman key exchange relies on it.

Powers that jump around
0501001255075100exponent x2ˣ without the remainder: smooth, easy to undo2ˣ leaves 30: which x?
Each blue dot is 2x divided by 101, keeping only the remainder. Without that step (orange) the numbers grow smoothly, and an ordinary logarithm reads x straight back. With it, the results jump around with no visible pattern. (The answer for 30 is x = 94, found here by checking all 100 options. At real sizes that is hopeless.)

The details

On the map: q = p or pᵏ. Best attack: index calculus / (ex)TNFS

Given g and g^x modulo a prime p, find x. Hard for ordinary computers at large sizes, but index-calculus and number-field-sieve algorithms are sub-exponential, so fields need roughly 3072-bit primes for 128-bit security[1], versus 256-bit elliptic curves.

The Logjam attack (2015)[2] broke 512-bit "export-grade" Diffie-Hellman and showed that precomputation against widely shared 1024-bit primes was within reach of nation states. Shor's algorithm breaks it on a quantum computer.

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 (9 boxes)

References

  1. Elaine Barker. Recommendation for key management: part 1 - general. National Institute of Standards and Technology, 2020. doi:10.6028/NIST.SP.800-57pt1r5
  2. David Adrian, Karthikeyan Bhargavan, Zakir Durumeric et al. Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015. doi:10.1145/2810103.2813707