The discrete logarithm problem (DLP) is the computational task of finding the integer exponent x given a generator g and the value g^x within a finite cyclic group such as a multiplicative group modulo a prime or the point group of an elliptic curve. It is widely believed to be intractable for classical computers when the group is suitably large, and this presumed hardness underpins much of public-key cryptography. The elliptic-curve variant (ECDLP) offers equivalent security with smaller keys than the finite-field variant.
Overview
- Given a cyclic group G of order n generated by g, and an element h = g^x, the discrete logarithm of h to base g is the exponent x. Computing x is easy to verify but believed hard to find.
- In the multiplicative group of integers modulo a large prime p, the best known classical algorithms (index calculus, number field sieve variants) run in sub-exponential time, requiring large key sizes for security.
- In elliptic-curve groups (ECDLP) no sub-exponential algorithm is known; the best generic attacks (Pollard’s rho, baby-step giant-step) run in time proportional to the square root of the group order, allowing far smaller keys for equivalent security.
Mechanisms
- The hardness asymmetry — easy exponentiation, hard inversion — is a one-way function suitable as a Cryptographic Primitive.
- Key exchange protocols derive shared secrets from the difficulty of inverting g^x without knowing x.
- Signature schemes commit to a secret exponent and prove knowledge of it without revealing it.
- Security parameters are chosen so that the expected attack cost exceeds any feasible computation.
Applications
- Underpins Diffie-Hellman key agreement and its elliptic-curve form.
- Secures Schnorr Signature and ECDSA signing.
- Provides the trapdoor for ElGamal encryption.
- Forms the basis of many threshold and commitment schemes used across Cryptographic Protocol design.