# Quadratic residue zero knowledge proof - simulator with identical distribution

I am looking at the zero knowledge proof for quadratic residues and am confused when it comes to showing a simulator that can give a transcript of the proof with the same distribution as the proof output itself.

In all explanations/proofs I have seen online the simulator has an element of iteration in it. For instance, taken from here: Why is that iterative aspect needed? I don't quite understand whose distribution we are trying to show is identical to whose too.

The first message from the prover is random just like it is in the protocol itself, b is a random value in both cases too. The second message from the prover to the verfier is distributed like b. what is this simulator gaining from generating two different messages based on b' and then executing something different based on b?

I've read the paper and other sources too but none seem to directly explain the need for this looping and what exactly it is that we want to be distributed the same way.

Any help is greatly appreciated.

• I suggest you peruse a good, self-contained textbook, instead of online lecture notes which are meant to be used in a classroom setting. – fkraiem Jan 12 '17 at 3:43
• any recommendations? The book I've been following does not mention zero knowledge proofs. – TheFooBarWay Jan 12 '17 at 7:34
• Sorry, recommendations are off-topic here, but there aren't too many crypto theory textbooks to choose from... – fkraiem Jan 12 '17 at 8:31
• My simulator tutorial may help for this. eprint.iacr.org/2016/046.pdf – Yehuda Lindell Jan 12 '17 at 10:40
• Goldreich's book (Foundations of Cryptography, volume 1, chapter 4) talks about zero knowledge. – pg1989 Jun 11 '17 at 23:26

Zero knowledge simulator (not honest verifier zero knowledge) is required to produce simulated session transcript that must be indistinguishable. Challenge of Verifier $b$ is the part of the transcript. For identical distribution, real Verifier is invoked to produce the challenge. First message of the protocol $y$ is passed to the Verifier. Simulator-chosen challenge $b'$ is here to properly compose first message $y$ so that it would fit the verification relation. Simulator is looping until it would guess the challenge of real Verifier.
• Simulated transcript must both verify the relation and be indistinguishable. For a random prover response $m_2$, it will likely not verify the relation. In case of looping until correct $m_2$ is found: it would take too long to pick from that set. – Vadym Fedyukovych Jan 13 '17 at 20:57