4
$\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.

Improve this question
$\endgroup$
4
  • 4
    $\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, 2019 at 22:45
  • 1
    $\begingroup$ the tutorial is very hard to understand. I need very basic definitions for the terms I asked about $\endgroup$
    – Heba Mohsen
    Feb 26, 2019 at 1:12
  • 1
    $\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, 2019 at 1:21
  • $\begingroup$ This article explains it at a high level, including simulation blog.cryptographyengineering.com/2014/11/27/… $\endgroup$
    – Natanael
    Feb 26, 2019 at 2:27

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Do all zero knowledge security proofs, use a simulator and extractor? Or are there game-based definitions? $\endgroup$
    – WeCanBeFriends
    May 18, 2020 at 21:08
  • $\begingroup$ Oh so if we are trying to show indistinguishability, then we use a simulator based approach. When would I use game-based definitions? (My understanding is naive) I'm trying to figure out when to use one over the other $\endgroup$
    – WeCanBeFriends
    May 19, 2020 at 16:09
  • $\begingroup$ Depends on the context, i.e., the security property one is trying to model. Some security properties can be expressed better through a simulation-based definition (e.g., zero-knowledge) and others through a game-based definition. In some cases these definitions turn out equivalent (e.g., semantic security and IND-CPA game for encryption scheme). But usually, simulation-based definitions are stronger and therefore harder to achieve than game-based ones. There are cases where schemes based on indistinguishability are possible but simulation-based ones are simply not (for example obfuscation). $\endgroup$
    – ckamath
    May 20, 2020 at 15:14
  • $\begingroup$ Your explanation cleared up a lot of confusion."There are cases where schemes based on indistinguishability are possible but simulation-based ones are simply not (for example obfuscation)." Not sure I understand this part. do you mean that there are schemes which can be built using game-based definitions but a simulation-based one is not possible? $\endgroup$
    – WeCanBeFriends
    May 21, 2020 at 14:19
  • $\begingroup$ Yes, for the case of obfuscation (e.g.) it is known that simulation-based definition (called virtual black-box obfuscation) cannot be achieved for general functions but the indistinguishability-based definition (IO) is plausible. The indistinguishability-based notion of zero-knowledge is called witness indistinguishability, and it is known that in certain cases WI is possible but ZK is not. $\endgroup$
    – ckamath
    May 21, 2020 at 15:44

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.