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

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?

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.

• Thanks for answering. What is the idea behind the simulator? – Leafar Jun 30 '17 at 13:13
• That's quite easy: Pick an element, use the trapdoor function (squaring) and send that as first message, and then adjust the other messages to be able to answer both cases $b=0$ and $b=1$ of the verifiers choice. Alternatively you could also split $a^2y^{-b'}$ into two cases ($a^2$ and $a^2y^{-1}$), there is no need to define them in one formula - as long as the simulator chooses uniformly, he succeeds with probability $0.5$ . – tylo Jun 30 '17 at 13:42
• My question is, is this simulating the interaction between the prover and the verifier? – Leafar Jun 30 '17 at 15:57