Zero-knowledge proof systems have three properties: soundness, completeness and zero-knowledge. I can't understand the definition of "zero-knowledge". What does "simulate" mean? And what is the difference between "honest-verifier zero-knowledge" and "zero-knowledge"?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ The formal definition of zero-knowledge gives the exact semantics (through the existential quantification of a Turing machine) of what it means to simulate. These definitions can be found in introductory textbooks such as Goldreich's Foundations of Cryptography. $\endgroup$– dionyzizFeb 18, 2018 at 11:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The intuition behind Zero Knowledge is that the Verfifier should not learn something about the secret. That means, that the communication between the Prover and the Verifier ("Transcript") must not reveal any information about the secret. So, there must exist a Simulator, not knowing the secret, that can falsify the transcript between Prover and Verifier. A "real" transcript and a transcript falsified by a Simulator must be indistinguishable. Thus, "simulate" means that the Simulator simulates the communication between a Prover and a Verifier.
Honest Verifier ZK means, that we can expect that the Verifier behaves honestly according to the specified protocol. That is, he does what the protocol specifies. In "normal" ZK, the Verifier can be malicious.
Example: The Graph 3-Color protocol [1]. An honest Verifier chooses a random edge (as the protocol says). A malicious Verifier may choose every time the same edge.
[1] http://www.cs.cornell.edu/courses/cs6830/2011fa/scribes/lecture18.pdf
