The Discrete Logarithm Problem
The Discrete Logarithm Problem is a foundational problem in the field of cryptography and number theory.
The Discrete Logarithm Problem involves finding an integer x given the equation:
g^x ≡ h mod p
where:
g is a known base,
h is a known result,
p is a prime number (or the order of the group in more general settings).
In this sense (and in reference to the idea of a given operations on a sets of elements), the operation:
g^h
refers to applying the operation (in this case the * operation) h number of times. That is:
g^h = g*g*g*g*...*g*g
| - - - - - - - - - - - |
h times
In the case of elliptic curves, we often refer to the same problem, in terms of the + operation, and the idea that:
gh = h+h+h+h+...+h+h
| - - - - - - - - - - - - - |
h times
But the complexity of reversing the operation is still referred to as the Discrete Logarithm Problem.
Context
Group Theory: The problem is defined within the context of cyclic groups, where the operations are performed under modular arithmetic.
Cryptography: The Discrete Logarithm Problem is crucial in the security of cryptographic protocols, particularly in public key cryptography such as Diffie-Hellman key exchange and Elliptic Curve Cryptography (ECC).
Difficulty
The "discrete" part of the name emphasizes that this problem is concerned with integers, unlike its continuous counterpart in real numbers.
The complexity of finding k in the equation kP ≡ Q, for multiplication on an elliptic curve, is what makes it valuable for cryptography; there are no known efficient (polynomial time) algorithms for solving it in general cases, making it a computationally hard problem.
That is, for applications in cryptography, we are on the search for groups within which the Discrete Logarithm Problem (for whichever operation it is defined) is a computationally difficult problem to solve.
Application
Security: The difficulty of the Discrete Logarithm Problem underpins the security of various encryption systems and digital signatures, where the ability to quickly compute power but the difficulty to reverse it (i.e., compute the logarithm) provides cryptographic security.
Further Study
For an interesting, investigation of the algebra behind the Discrete Logarithm Problem, and why it is of interest in Applied Cryptography, please see Leandro Junes' series of videos on the subject:
