5
$\begingroup$

I'm reading about Zero-Knowledge-Proofs, in particular the argument of building a Simulator in order to prove the zero-knowledge property. As expected, there's something that doesn't click yet.

Since a simulator is using a transcript to 'fool' the verifier, I understand the idea that since the Simulator knows nothing but the transcript, then the verifier can't extract any knowledge besides the statement being challenged.

Now, this doesn't prove that the verifier is not extracting knowledge from the transcript. If the transcript per-se has the knowledge, woudn't be a problem?.

Thinking it differently, if a monkey randomly type a Calculus book... yes, the monkey knows nothing about calculus, but a reading verifier would get real knowledge by reading his work.

Am I missing something?

Improve this question
$\endgroup$
7
  • $\begingroup$ Welcome to Crypto.SE! The definition of Zero-Knowledge $(P, V)$ states that the for every efficient verifier $V'$ there exists a simulator that could create a transcript with the same distribution. In the case of Honest Verifier Zero-Knowledge we only look at the simulator for $V$ $\endgroup$
    – Marc Ilunga
    Apr 30, 2019 at 17:04
  • 1
    $\begingroup$ Thanks for you reply but I don't understand how it answer my question $\endgroup$
    – Coco
    Apr 30, 2019 at 17:32
  • $\begingroup$ The key is that for all verifiers including $V$ we can find a simulator. So $V$ cannot extract the knowledge from the transcript because like any other verifier, she could just generate the transcript herself using her simulator $\endgroup$
    – Marc Ilunga
    Apr 30, 2019 at 17:59
  • 2
    $\begingroup$ The probability of a monkey randomly typing a calculus book is negligible. $\endgroup$
    – fkraiem
    Apr 30, 2019 at 18:00
  • $\begingroup$ @fkraiem , so you mean then that the correct statement is: information leaks with a negigible probability? $\endgroup$
    – Coco
    Apr 30, 2019 at 18:31

1 Answer 1

Reset to default
2
$\begingroup$

..then the verifier can't extract any knowledge besides the statement being challenged.

Please let me amend it to, since a proper transcript (an indistinguishable one) can be generated by a simulator having no secret input at all, then transcript value is questionable for any reasoning about secrets (an easy, non-formal wording). In particular, a Prover can claim did not run (was not a party to) a protocol.

Now, this doesn't prove that the verifier is not extracting knowledge from the transcript.

Knowledge extractor algorithm is a requirement for another property, proof of knowledge.

Thinking it differently, if a monkey randomly type a Calculus book... yes, the monkey knows nothing about calculus, but a reading verifier would get real knowledge by reading his work.

Simulator is required to be efficient (expected polynomial running time), and calculus book is too complex to fit that. I'd suggest a weather forecast instead, like yes/no for rain tomorrow.

Back to book, a fast (efficient) reader would get garbage most of the times, with no chance to distinguish the correct case (proper textbook) better than guess.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So the idea of the simulator is, from the point of view of the verifier, a statistically equal distribution output compared to a real prover, but without having access to the prover. Is this correct? $\endgroup$
    – Coco
    May 3, 2019 at 15:43
  • $\begingroup$ This is the intuition behind zero knowledge and general original definition. Well, almost. Negligible advantage instead of 'equal', in terms of probability difference and an adversarial algorithm trying to guess whether transcript was simulated or recorded. Statistical or computational flavors of zero knowledge. 'Honest verifier' flavor, since you can see the basic case right already. Expected running time of simulator must be polynomial in problem size. One could write a little textbook here to give a full precise answer. $\endgroup$
    – Vadym Fedyukovych
    May 4, 2019 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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