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$?


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.

| improve this answer | |
  • $\begingroup$ Thanks for your help. However, why this proof cannot work if $g$ and $h$ are generators of $Z^*_p$. Furthermore, how to use this proof in $Z^*_n$ where $n$ is an RSA modulus? $\endgroup$ – XJ LIN Apr 26 '14 at 6:41
  • $\begingroup$ @XJ LIN to have a zero-knowledge proof of knowledge to be a proof of knowledge you require a knowledge extractor (to prove the special soundness) and if the order of your subgroup you are working in is not prime (you may look here, in this example $(c-c')^{-1}$ may not exits in $Z_{p-1}^*$ but is guaranteed to exist if you work in a prime order $q$ subgroup). For an RSA modulus being the product of two safe primes you can also prove the equality of logarithms (unfortunately, I have no reference at hand). $\endgroup$ – DrLecter Apr 26 '14 at 7:32
  • $\begingroup$ Thank you very much. I have another question: I think that if $P$ computes the response $z = r + x c$ in $Z$, not in $Z_q$, it seems that the problem can be solved. That is, in this case the soundness can also be achieved without losing security. $\endgroup$ – XJ LIN Apr 26 '14 at 10:27
  • $\begingroup$ @XJLIN No that does not change anything. The problem is within the $c$ values. What you could do is to artifically restrict the space from which challenges are chosen such that all pairs of $c$ values have inverses in $Z_{p-1}^*$ (such as using only challenges 0 and 1 - however then your cheating probability in one round is 1/2 and you have to run the protocol sufficiently many times to make the cheating probability small enough). $\endgroup$ – DrLecter Apr 26 '14 at 11:41
  • $\begingroup$ How can I used this proof in $Z^*_n$, where $n$ is an RSA modulus? Could you give some advice? $\endgroup$ – XJ LIN Apr 26 '14 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.