As I understand it, one of the properties required to prove UC-security is simulation extractability. One example is the paper by Kosba et al adapting NIZKs to the UC model, but in their construction the witness is encrypted and the ciphertext appended to the proof, and whoever holds the private key can extract the (confidential) witness. (There's also a separate trapdoor that can forge proofs, but for the forged proofs the extractor is not required to work.)

Is this property required for simulation extractability? Would any UC-secure NIZK system also have a backdoor in it? Or am I misinterpreting what simulation extractability means?

Link to the Kosba et al preprint: http://eprint.iacr.org/2015/1093


Extractability inherently requires that the party who holds the extraction trapdoor can extract the witness. Therefore, it is important that the common reference string (CRS) is set up by a trusted party in the real protocol. However, this requirement for setting up the CRS in a trusted way is not only specific to extractability but also required by other notions such as soundness or zero-knowledge (see, e.g., [1] where the fact that the CRS is not set up by a trusted party is used to attack a protocol). Ultimately, you may observe that this trusted setup requirement is not only specific to zero-knowledge protocols, but applies to every protocol which relies on a CRS.

Regarding the UC-secure NIZK part of the question: Roughly speaking, realising a UC compatible zero-knowledge protocol requires to achieve simulation extractability. Therefore, one also has to take care that the CRS is set up by a trusted party in real instances of the protocol.


[1] http://stevengoldfeder.com/papers/ZKCSP.pdf

  • $\begingroup$ Hm, this is interesting. How do NIZKs such as SCIP - which don't rely on the public parameters being set up by a trusted party - fit in, since they guarantee soundness and zero-knowledge outside of the CRS model? eprint.iacr.org/2018/046 $\endgroup$ – Ian MathWiz Jan 29 '18 at 7:41
  • 1
    $\begingroup$ As far as I can see, the proofs in ePrint 2018/046 are interactive. The notions you were asking about are defined for non-interactive proof systems. Note: Often interactive proofs can be turned into non-interactive ones using the random oracle heuristic (note, however, that this does not hold in general but depends on the concrete interactive proof you are having). Accepting the random oracle assumption may allow to drop the CRS. $\endgroup$ – dade Jan 29 '18 at 8:22
  • 1
    $\begingroup$ You may also be interested to have a look at ePrint 2012/704 which proves certain properties for $\Sigma$ protocols turned into non-interactive proof systems (also simulation extractability). $\endgroup$ – dade Jan 29 '18 at 8:24
  • $\begingroup$ Yeah, I was thinking more about the noninteractive version that used random oracles. I'll have a look at that eprint, but does this mean that an interactive proof that is turned into a noninteractive one this way can have properties that are impossible for a purely noninteractive one? From what you said, it seems the random oracle model can substitute for the CRS model in allowing UC-security. $\endgroup$ – Ian MathWiz Jan 29 '18 at 16:36
  • 1
    $\begingroup$ In this context you might have a look at this paper $\endgroup$ – dade Jan 29 '18 at 17:13

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.