Discrete Logarithm Problem

The Discrete Logarithm Problem (DLP) is a fundamental “hard problem” used as the basis for modern public-key cryptography (e.g., Diffie-Hellman Key Exchange, DSA). It relies on the computational asymmetry of modular exponentiation.

• Definition: Given base $g$ and some $h=g^k(\mathrm{mod}p)$ find $k$
• Example: $g=3,h=13,p=23\to k=5$

While computing $h$ from $k$ (exponentiation) is computationally efficient, computing $k$ from $h$ (the discrete logarithm) is believed to be computationally infeasible for sufficiently large and carefully chosen parameters.

Security & Hardness

For DLP to be secure, brute-force or algebraic attacks must be infeasible. This imposes strict requirements on the group structure:

1. Group Selection: The modulus $p$ must be a safe prime ($p=2q+1$ where $q$ is also prime) to prevent attacks like Pohlig-Hellman or Index Calculus.
2. Key Size (Integer Groups): To maintain security against modern computing power, $p$ is typically required to be 2048–3072 bits.

Variant: Elliptic Curve Cryptography (ECC)

The DLP can also be applied to the algebraic structure of points on an Elliptic Curve.

• Advantage: The DLP is significantly “harder” on elliptic curves (no sub-exponential attacks like Index Calculus exist).
• Efficiency: A 256-bit Elliptic Curve key provides roughly equivalent security (128-bit security level) to a 3072-bit integer group key, making ECC far more efficient for storage and performance.

---

Relevant Note(s):