It is sometimes required while proving the security of a protocol in the malicious setting that the simulator is able to extract the witness set of the adversary, who tends to be the prover of possessing some knowledge, in the ZKP step of the protocol.
I was having issues understanding how the simulator would be able to extract the witness set without the discretion of the adversary?
If the simulator is able to do so, wouldn't that defeat the purpose that the ZKP is zero knowledge, at least to the simulator?
I also read that the witness extraction by simulator doesn't necessarily have to be probabilistic polynomial time. Can someone please elaborate on this?

  • $\begingroup$ "I also read that the witness extraction by simulator doesn't necessarily have to be probabilistic polynomial time", where did you read this? $\endgroup$ – Changyu Dong Jun 21 '18 at 17:05
  • $\begingroup$ On Page 10 (ending note of point 1) of the proof of Proposition 3.4 of "Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer" by Lindell et al. $\endgroup$ – Mayank Jun 21 '18 at 17:11
  • $\begingroup$ Here is the link (eprint.iacr.org/2010/284.pdf) $\endgroup$ – Mayank Jun 21 '18 at 17:15
  • 1
    $\begingroup$ I think you might have misunderstood it. It says "We remark that the above procedure does not guarantee that S runs in expected polynomial time. Thus, formally S runs the witness-extended emulator of [26] that achieves the above effect". It means that strictly speaking, point 1 is not correct because the running time of S may be worse than expected polynomial time if runs as described (to find out why, read [26]). However, this can be fixed by requiring S to run the witness-extended emulator. $\endgroup$ – Changyu Dong Jun 21 '18 at 19:26
  • $\begingroup$ Thanks for the clarification. Can you please also comment on how the simulator can extract the witness set without the discretion of the prover? Is it what the witness extended emulator does? $\endgroup$ – Mayank Jun 21 '18 at 19:35

Let me try. First, one thing needs to be clear: simulation and real execution are two different things. The simulator can learn something does not mean a verifier in real execution can learn the same thing. Thus the fact that a simulator can extract knowledge does not affect the protocol’s zero-knowledge property (which is about the verifier in the real execution).

Why the simulator (or more accurately the knowledge extractor) can extract the knowledge but the verifier cannot? This is because the simulator has some special ability that the parties in the real world don’t have. One example is “rewinding”: the knowledge extractor can rewind the adversary to a previous state. If you are familiar with the Schnorr protocol, you should know rewinding is used to extract knowledge there. But can a real verifier rewind the prover? No.

Then why the knowledge extractor is given such an ability? It is for the sake of writing security proofs. A secure proof of knowledge protocol means that If the prover convinces the verifier, then it must know and use the witness in the protocol. This is hard to prove in fact. So we allow a knowledge extractor with extra ability to help us so that if the witness is used, the knowledge extractor can extract it from the transcript. Thus if the witness can be extracted, we can be certain the witness is used and the protocol is proof of knowledge.

  • 1
    $\begingroup$ If I am not wrong then we cannot have such a simulation in Universal Composability because a simulator cannot rewind there otherwise the environment will realize it. So, in Universal Composability does the environment gets the extraction of witnesses done, maybe by running multiple protocols with the same random tape? $\endgroup$ – Mayank Jun 21 '18 at 21:55
  • 2
    $\begingroup$ Yes in the UC model rewinding is not allowed. There are other ways of extracting knowledge. For example, in the case of CRS (common reference string), the extractor can have a trapdoor that helps it to extract the witness. $\endgroup$ – Changyu Dong Jun 21 '18 at 22:22

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.