How to prove you know a discrete logarithm

In a high school math class, the solution to the equation

b^x = y

is the logarithm of x in base b. The implicit context of the equation is the real numbers, and the solution is easy to calculate.

The same problem in the context of finite groups is called the discrete logarithm problem, and it is difficult to solve for large groups. In particular, it is impractical to solve when working modulo a sufficiently large prime number or when working over a sufficiently large elliptic curve [1]. In either context, the exponential b^x can be computed efficiently but its inverse cannot.

Now suppose you want to prove that you know x without revealing x itself. That is, you’d like to construct a zero knowledge proof that you know x. How could you do this?

Here’s one way.

1. You, the prover, create a random number r, compute t = b^r, and send the verifier t.
2. The other party, the verifier, creates a random number c, the challenge, and sends it to you.
3. You calculate s = r + cx and send s to the verifier.
4. The verifier checks whether b^s = t y^c. and believes you if and only if equality holds.

Let’s see why this works.

First of all, what have you revealed to the prover? Two values: t and s. The value t is the exponential of a random number, and so another random number. The value s is based on x, and so conceivably you’ve revealed your secret. But the verifier does not know r, only a value computed from r (i.e. t) and the verifier cannot recover r from t because this would require computing a discrete logarithm.

Next, why should b^s = t y^c? Because

b^s = b^{r + cx} = b^r b^cx = t (b^x)^c = t y^c.

Finally, why should the verifier believe you know x? If you don’t know x, but were able to come up with an s that satisfies the verifier, then you were able to compute the discrete logarithm of t y^c.

Related posts

• Lewis Carroll and zero knowledge proofs
• What is a Pedersen commitment?
• Zero knowledge proof of compositeness

[1] At least without a large-scale quantum computer. Schor’s algorithm could efficiently compute discrete logarithms if only there were a large quantum computer to run it on.