The concept of simulator for Zero Knowledge property

Computational indistinguishability

TODO - [] todo

Knowledge vs information

Refererce: Foundations of Cryptography - Basic Tools 4.1.2. Gaining Knowledge, p211

zero knowledge property

For zero knowledge property, simulator is commonly used to prove the property of zero knowledge.

In cryptographic protocols, the simulator always has more power than the real prover. Sometimes the simulator can generate the parts of the transcript in a different order. Sometimes the simulator can "rewind time" -- so the verifier asks a question, and then we rewind time and start the transcript over, knowing what the verifier is going to ask. Sometimes the simulator literally has more computational power than the real prover. Sometimes the simulator has some extra information that the real prover doesn't have (like a trapdoor to some common reference information used in the proof).

Simulator is a rigorous way of formalizing the following idea: the verifier didn't learn anything because "they could have generated the transcript themselves.". In other word, the intuition of the simulator is, from the point of view of the verifier, a statistically negligible equal distribution output compared to a real prover in terms of probability difference, but without having access to the prover. Expected running time of simulator must be polynomial in problem size.

The simulator is an efficient machine that has oracle access to the verifier and given the statement as input, it, in place of prover, simulates the view of the (adversarial) verifier. Since the simulation is possible using only the statement, it can be argued that the verifier learns nothing more (about the witness).

The extractor concerns zero-knowledge proofs of knowledge which are zero-knowledge proofs which additionally guarantee that the prover indeed holds the witness. In particular, the extractor given access to the prover (which it can potentially rewind) can extract this witness for example by rewinding it.

A key role in proving that an interactive system has the property of zero knowledge is played by the Simulator (S), which simulates P but does not have access to the witness. His contribution is as follows: V interacts with S. At some point V will put S in the 'difficult position' of not being able to answer a question, as he does not have access to the witness. In this case we return the V movie to a state before the unpleasant question (rewind) and run the protocol from that point onwards. If V (with continuous rewinds) finally accepts S's proof, the protocol has the status of zero knowledge, as V can not distinguish between a P who knows the witness and an S who pretends. That is, V does not export any additional information from the protocol (since in the second case there is no information to export).

Simulation of proof in place of P interacts with V. We can not distinguish the interactions ⟨S, V⟩ and ⟨P, V⟩. We also allow rewinds: If at some point V 'asks' something he can not answer, S then stop - rewind Zero knowledge if V at some point accepts (even with rewinds).

Why: Cannot distinguish P (having witness) from S (not available). As long as S remains PPT Specifically: A V that extracts information from P will extract the same information from S (where there is nothing to export)

Formal definition of zero-knowledge with Turing machine

A formal definition of zero-knowledge has to use some computational model, the most common one being that of a Turing machine.

Simulator and Knowledge extractor

  • simulator: If the simulator have the ability of cheating without superpower, the protocol can be proved to be unsound
  • extractor: If the extractor can extract the knowledge of Alice entirely by leveraging time rewind in the ideal world, the goal that a Alice without knowledge cannot be knowledge extracted is guaranteed, and the soundness can be proved.

Better look at learning-zkp/zkp-simu.md at master · sec-bit/learning-zkp · GitHub

References

  1. Simulator vs Prover -- Zero Knowledge Property - Cryptography Stack Exchange
  2. provable security - What is purpose of a simulator and extractor in zero knowledge proof protocols? - Cryptography Stack Exchange
  3. Zero-knowledge proof - Wikipedia