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?
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).