Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
Crudely put: (special) soundness means for a (non-)interactive proof of knowledge that you cannot prove false statements (statements where you don't know the knowledge that you are proving).
Witness-extended emulation is a generalisation of this notion: it means that there exists an emulator (that's allowed to rewind the prover to any state, and to supply the verifier with fresh randomness) that extracts a witness from the (modified) transcript.
It means that the emulator can extract a witness (and thus can forge proofs) from looking at and tampering (to some extend) the prover and verifier.
To see how this is a generalisation of special soundness: the fact that the emulator can extract a witness from the tampered transcript means that this witness is somehow put into the transcript by the prover. This in turn means that, if an emulator exists for the protocol that extracts the witness from a valid transcript, we know the prover had this witness present during proving; i.e., if the protocol has witness-extended emulation, the protocol requires a witness, and we have special soundness.
