3
$\begingroup$

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:

enter image description 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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

Let me repeat it: query Verifier to pick a challenge with otherwise unknown distribution; the rest of algorithm follows.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the reply. So we have the transcript (m1, b, m2) where m1, m2 are the first and second messages. you're saying that we loop so that m1 will match b? but in the protocol itself (the real one, not the simulator) m1 is decided before b is ever known, why would we need to properly choose m1? seems to me like m1 in the original protocol is just random, b is dependent on V and m2 is 50/50. Why can't I use a transcript with a random m1, get b from V and then toss a coin for m2? would the distribution not be identical? $\endgroup$
    – TheFooBarWay
    Jan 13, 2017 at 9:16
  • $\begingroup$ 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. $\endgroup$
    – Vadym Fedyukovych
    Jan 13, 2017 at 20:57

Your Answer

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

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