How can we prove that two discrete logarithms are equal?

Question

Suppose there are two elements $a = g^x$ and $b = h^x$, where $g$ and $h$ are generators in $Z^*_p$ and $p$ is a large prime. How can we prove that $a$ and $b$ have the same discrete logarithms with respect to $g$ and $h$ respectively without leaking the knowledge of $x$?

Answer 1

Are you limited to working with $g$ and $h$ being generators of the entire group $\mathbb{Z}_p^*$? In that case you have a problem with knowledge extraction in the proof of knowledge (basically, since you are not working in a field "in the exponent", but in $\mathbb{Z}_{p-1}$, the required multiplicative inverses might not exist).

However, when you work in a large prime order $q$ subgroup of $\mathbb{Z}_p^*$ and $g$ and $h$ are generators of the order $q$ subgroup, you can use a standard honest-verifier zero-knowledge proof of knowledge that you know $x\in \mathbb{Z}_q$ such that $\log_g a = \log_h b$ (i.e., $a$ and $b$ contain the same discrete logarithm w.r.t. $g$ and $h$ respectively) without revealing anything about $x$. This proof is quite standard and based on Schnorr's proof of knowledge of a discrete logarithm.

The idea proof between a prover and a verifier on common input $(p,q,g,h,a,b)$ runs as follows (where $x$ is only known to the prover):

• $P$: choose uniformly at random $r\in \mathbb{Z}_q$ and send $(k,k')=(g^r,h^r)$ to the verifier $V$
• $V$: choose uniformly at a random challenge $c\in \mathbb{Z_q}$ and send $c$ to $P$ (I took the set $\mathbb{Z_q}$ as challenge space, the set size depends on the soundness error you are tolerating)
• $P$: compute the response $z=r+x\cdot c \bmod q$ and send $z$ to $V$
• $V$: Verify whether $g^z=k\cdot a^c$ and $h^z=k'\cdot b^c$ holds and accept if this is true or reject otherwise.

Correctness is easy to verify and special soundness as well as honest-verifier zero-knowledge is also quite straightforward to show.