Prove that this protocol based on square roots modulo $n$ is zero knowledge

Question

Consider the following (zero knowledge) protocol based on the hardness of finding square roots modulo $n$. The Prover states that he knows a square root $x$ modulo $n$ of $y$, i.e., $y = x^2 \pmod n$.

1. The Prover randomly chooses $a \in \mathbb{Z_n^\times}$ and sends $r=a^2 \pmod n$ to the Verifier
2. The Verifier randomly chooses $b \in \{0,1\}$ and sends it to the Prover
3. The Prover sends to the Verifier the value $w=x^ba \pmod n$
4. V accepts if $w^2 = y^br$; otherwise the Verifier rejects

This protocol is repeated a sufficiently large number of times in order to convince the Verifier that the Prover really knows $x$. This protocol is sound and complete (if the prover is dishonest, then he is detected with $1/2$ probability each time the protocol is ran.)

How can we prove that this protocol is indeed Zero Knowledge?

Thanks in advance.

Answer 1

Here's the simulator $S$ to replace $P$ for challenge $y = x^2 \mod n$:

• Choose $a$ randomly from $\mathbb{Z}_n$, draw a bit $b'$ uniformly.
• Send $a^2 y^{-b'} \mod n$ to $V$. The inversion is done in $\mathbb{Z}_n$ of course.
• $V$ replies with $b$:
  • If $b = b'$: send $a$ to $V$
  • Otherwise: abort

If $b'$ is drawn uniformly, then it doesn't matter how $b$ is chosen - the simulator always has exactly probability $0.5$ for the case $b = b'$ for a successfull verification.