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$?
1 Answer
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.
-
$\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 LINApr 26, 2014 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$– DrLecterApr 26, 2014 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 LINApr 26, 2014 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$– DrLecterApr 26, 2014 at 11:41
-
1$\begingroup$ How can I used this proof in $Z^*_n$, where $n$ is an RSA modulus? Could you give some advice? $\endgroup$– XJ LINApr 26, 2014 at 12:43