Discrete Logarithm Problem

Modular exponentiation is one candidate for a one way function.

Definition

Given:

• a prime number \(p\)
• a primitive root of \(p\) called the generator \(g\)

Then the below function appears to exhibit one-way properties:

\[f(n) = g^n\ mod\ p\]

This is because

1) For any \(n\) it is computationally efficient to calculate \(f(n)\). Using [[ exponentiation by squaring ]] we get \(O(log(p))\)

2) Given \(y = f(n)\) it appears to be relatively computationally expensive to calculate \(n\). Generally a brute force solution is required to (in the worst case) search the full group space, giving \(O(p)\)

Note that the difference between \(O(log(p))\) and \(O(p)\) is exponential: Assuming a base 2 system, let \(m = log_2(p)\) (ie \(m\) is the bit length of the input), then:

• complexity in the “easy” direction is \(O(m)\)
• complexity in the “hard” direction is \(O(2^m)\)

Therefore by selecting a prime number that is large, this relative efficiency can be made such that it is only feasible to perform the function in one direction

Primitive Roots

Note that choosing \(g\) to be a primitive root of \(p\) means that \(f(n)\) is distributed uniformly over the range for \(0 <= n < p\) For example: 5 would be a primitive root of the prime 17

Proof of Hardness & Quantum Computing

Like all one way functions, there does not exist a formal proof that calculating discrete logarithms on a classical computer is limited to brute-force algorithms. It is only assumed hard because it has remained unsolved for such a long time.

In addition, there exists quantum algorithms (see [[ Shors Algorithm ]]) which solve for discrete logarithms with exponential speedup over classical computers, and would therefore break the asymmetry of the one-way function.

\[O(2^m) \rightarrow O(log(2^m)) = O(m)\]

Practical Applications

This computational complexity is taken advantage of in many cryptographic applications. For example, discrete logs act as the one-way function in Diffie Hellman key exchange, which allows for two parties to obtain a shared secret over an insecure communications channel.