1
$\begingroup$

I am new to zero knowledge proofs. I read the paper Efficient Protocols for Set Membership and Range Proofs by Jan Camenisch, Rafik Chaabouni and Abhi Shelat.

The author proposed a zero knowledge set membership protocol in page 9. Then, he stated in theorem 1 that the the protocol is a zero-knowledge argument of set membership. Then, he explicitly said "to prove honest-verifier zero-knowledge, we construct a simulator Sim that will simulate all interactions with any honest verifier V. This is all detailed in Page 8 and 9.

What is simulator, and what is purpose of Sim? Is the Sim an adversary? What does "the extractor" mean? If you look at the paper, the simulator in Fig. 2 looks exactly to the proposed protocol in Fig. 1.

$\endgroup$
  • 2
    $\begingroup$ I think you are asking the basics of the simulation proof technique, which is hard to explain in a few sentences. Prof. Lindell's tutorial can be very helpful. $\endgroup$ – Shan Chen Feb 25 at 22:45
  • $\begingroup$ the tutorial is very hard to understand. I need very basic definitions for the terms I asked about $\endgroup$ – Heba Mohsen Feb 26 at 1:12
  • $\begingroup$ Sorry, I don't have time to write very long answers, but does this answer help you to understand what is a simulator? Then, to understand what an extractor does, I think you should first refer to the definition of proof of knowledge. $\endgroup$ – Shan Chen Feb 26 at 1:21
  • $\begingroup$ This article explains it at a high level, including simulation blog.cryptographyengineering.com/2014/11/27/… $\endgroup$ – Natanael Feb 26 at 2:27
1
$\begingroup$

The rigorous way to argue that the verifier learns nothing more than the validity of a statement in by designing a simulator. The simulator is an efficient machine that has oracle access to the verifier and given input the statement it 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.

$\endgroup$

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.