Witness-Extended Emulation I am reading up on Sonic: Zero Knowledge SNARKS from Linear - Sized Universal And Updateable Structured Reference Strings.

An excerpt:


  For soundness, we do not use the standard definition of special soundness because our verifier provides two challenges, but rather the generalized not of witness-extended emulation. 


Can anyone provide both a simple and terse explanation of the term
 "witness-extended emulation"
Witness-extended emulation is a more robust notion of knowledge soundness that avoids subtle problems when the proof of knowledge system is used inside of bigger protocols.

For example, suppose you have a two-party protocol between A and B where at some point A provides a PoK for some statement x. (So the PoK is used as a sub protocol inside this bigger protocol.)

Now, to prove that the protocol is secure you want to build a simulator S that simulates a corrupted A. To do so, it produces a view that is the view of A in the protocol, which includes the transcript of the PoK.
Also we can assume that this simulator needs to extract the witness from the PoK (in almost all cases the simulator needs to do so: intuitively, it seems that otherwise this PoK would be kind of useless).

Thus a naive simulator could:
1) Run with A and act as a verifier so to get a transcript of the PoK
2) If the transcript is valid, run the extractor E.

Now, the problem is that for (standard) knowledge soundness we have that the extractor is an expected polynomial time machine that outputs a valid witness and runs in $poly/(p-k)$ where $p$ is the probability that A outputs a valid proof and $k$ is the knowledge error (very roughly speaking, the probability of convincing the verifier by sending random messages).

The problem is that if we compute the expected running time of the simulator S we have that it is at least $p \cdot poly/(p-k)$, which might not be expected polynomial time!

Luckily, Lindell (https://eprint.iacr.org/2001/107.pdf) showed that if you have knowledge sound then you can get witness-extended emulation. So we don't have to worry about.

To summarize, whenever you want to use your PoK inside a bigger protocol it is more convenient to rely on witness extended-emulation (less troubles with the proof of security). While, if the PoK is used stand-alone then both the notion of security are fine.