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 ofy in baseb. 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 knowx without revealingx 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 verifiert.
2. The other party, the verifier, creates a random number c, the challenge, and sends it to you.
3. You calculates =r + cx and sends 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 ands. The valuet is the exponential of a random number, and so another random number. The values is based onx, and so conceivably you've revealed your secret. But the verifier does not knowr, only a value computed fromr (i.e.t) and the verifier cannot recoverrfromt 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 knowx, but were able to come up with ans 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.

The post How to prove you know a discrete logarithm first appeared on John D. Cook.