Consider the following protocol for $P$ and $V$ :

Note: The multiplicative group is $Z_p^*$ and $p$ is prime.

Note: The protocol is for proving that $x \in \langle \alpha \rangle$.

Input to $P$ and $V$ : a prime $p$ and $\alpha, x \in Z_p^∗, k = \log_2(p)$.

Input to $P$ : $y$, so that $\alpha^y = x \bmod p$.


$V$ checks that $\gcd(x, p) = \gcd(\alpha, p) = 1$ and rejects if this is not the case.

$P$ chooses $r$ at random in $[0, p - 2]$, and sends $a = \alpha^r \bmod p$ to $V$.

$V$ chooses $b$ at random in $\{0, 1\}$ and sends $b$ to $P$.

$P$ sends $z = (r + by) \bmod (p-1)$ to $V$.

$V$ checks that $\alpha^z = ax^b \bmod p$. If OK, then accept, otherwise reject.


I've already proven completeness and soundness of the protocol. However, I need to prove that it is zero-knowledge.

To do this, I consider a simulator playing the role of $P$.

I know, I could use the Rewinding Lemma, so I consider a perfect honest-verifier simulator.

I try to follow the ZK proof of the graph isomorphism protocol, however, I'm stuck.

I don't know how to respond if $b=1$, since I cannot assume the simulator knows $y$. The $b=0$ case is easy.

Can someone help me out?

  • $\begingroup$ This is exactly the point of rewinding: handling cases where the simulator cannot answer. $\endgroup$ – fkraiem Feb 10 '17 at 14:45
  • $\begingroup$ Yes, but still, I cannot just ignore each time $b=1$? Then the distributions are not indistinguishable. $\endgroup$ – Shuzheng Feb 10 '17 at 14:46

The simulator does not know $y$, but he does know $x$, and knows in advance which $b$ the verifier will pick. You already know the simulation when $b=0$. In the other case, when the simulator knows that the verifier will ask $b=1$, the simulator chooses $r$ at random and sends $a = \alpha^r/x$ instead of $\alpha^r$ to the verifier. Then, the simulator sends $z = r$. You can easily see that the check will pass: $\alpha^z = \alpha^r = (\alpha^r/x)\cdot x = ax = ax^b$.

EDIT: to complete a bit, the protocol you gave is honest-verifier zero-knowledge, which means that it is zero-knowledge as long as the verifier does not deviate from the specification. In this case, as the simulator is given the random tape of the verifier as input, he knows which $b$ the verifier will choose in advance.

If you want to handle a malicious verifier, to get a fully zero-knowledge protocol, the protocol must be modified, e.g. by asking the verifier to commit to his challenge before the start of the protocol (if you want more details on this point, feel free to ask).

  • $\begingroup$ Doesn't the "Rewinding Lemma" guarantee that the protocol is ZK as long as it is honest verifier ZK? $\endgroup$ – Shuzheng Feb 10 '17 at 15:58
  • $\begingroup$ I do not know exactly what you refer to by "rewinding lemma", but Sigma-protocols (three-move public-coin protocols) are not zero-knowledge, only honest verifier zero knowledge. An additional interaction is necessary to get full zero knowledge. $\endgroup$ – Geoffroy Couteau Feb 10 '17 at 16:03
  • $\begingroup$ This lemma says that for protocols with conversations consisting of messages of the form (a,b,z), it is enough to prove ZK for honest verifier, the it is automatically ZK for any verifier. Maybe my theory litterateur is a little different from yours. Nonetheless, your idea works for my problem. $\endgroup$ – Shuzheng Feb 10 '17 at 16:09
  • $\begingroup$ Do you have a link for this lemma? It looks clearly wrong to me. $\endgroup$ – Geoffroy Couteau Feb 10 '17 at 16:11
  • $\begingroup$ daimi.au.dk/%7Eivan/ComZK08.pdf - then search for "Rewinding lemma" in the PDF. $\endgroup$ – Shuzheng Feb 10 '17 at 16:16

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.