ZK proof of “element in subgroup” protocol

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

Protocol:

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

Problem:

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?

• This is exactly the point of rewinding: handling cases where the simulator cannot answer. – fkraiem Feb 10 '17 at 14:45
• Yes, but still, I cannot just ignore each time $b=1$? Then the distributions are not indistinguishable. – 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.