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.


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

  • $\begingroup$ Thanks for answering. What is the idea behind the simulator? $\endgroup$
    – Leafar
    Commented Jun 30, 2017 at 13:13
  • $\begingroup$ 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$ . $\endgroup$
    – tylo
    Commented Jun 30, 2017 at 13:42
  • $\begingroup$ My question is, is this simulating the interaction between the prover and the verifier? $\endgroup$
    – Leafar
    Commented Jun 30, 2017 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.