3
$\begingroup$

In the zero knowledge definition of the Groth16 scheme (https://eprint.iacr.org/2016/260.pdf) [Section 2.2], why would the simulator be allowed a trap-door in set up? The trap-door information contains the toxic waste that should be destroyed by the set up. In another word, if the simulator (a.k.a modeling a passive attacker) learns the toxic waste, would it hurt the security of the protocol?

$\endgroup$

1 Answer 1

3
+50
$\begingroup$

The trapdoor is fundamental for arguing zero-knowledge. You can think of it this way: with the trapdoor, the prover could provide a valid proof without knowing the witness, and the proof would be indistinguishable from a real proof. This guarantees that nothing is leaked about the witness by a valid proof, since a similar-looking proof could have been generated without it.

Of course, the trapdoor should not be known by the prover in the real world - that would allow them to cheat.

In traditional NIZK systems such as Groth-Sahai, the trick is that the system parameters can be generated in one of two indistinguishable modes - one with the trapdoor, and one without. In the real-world, we use a setup that guarantees that the parameters are generated in the trapdoor-less mode (actually, we can also use a setup that generates parameters with a trapdoor, but in a way that guarantees that no one knows the trapdoor).

[EDIT - fixing an incorrect answer where I was confusing Groth16 and GrothSahai08, thanks to Wilson for pointing it out]

For Groth-Sahai the trapdoor-less mode is a uniformly random string. An easy way to generate the trapdoor-less parameters is to use a "nothing up my sleeve" method, i.e. a process that ensures that the outcome was not controlled by anyone - e.g. take the result of the last lottery, append a bunch of decimals of $\pi$, and hash the result with SHA2. Anything like that should work.

For SNARKs, however, and in particular for Groth16, things are fundamentally different: we do usually not have any way to make the construction work using a uniform random string*. We still need this trapdoor inside the string for the simulation (when we prove zero-knowledge), but now for soundness, we really have to make sure the prover does not know the trapdoor (and rely on a knowledge-of-exponent assumption to show that if they cheat without knowing the trapdoor, they must know the witness). In this case, the best solution is usually to generate this SRS using a secure distributed protocol with many parties, to "dilute" the trust. This can be costly and is not entirely satisfying, but it's a one time cost, and it is the best we can do (beyond just trusting whoever generated the SRS).

(*) We can do that for some proof systems which have succinct proofs, but non-succinct verifier runtime, such as Bulletproof. Achieving an efficient SNARK that only relies on a random string and has succinct verification is, as far as I know, an open problem.

$\endgroup$
2
  • $\begingroup$ I'm confused about your last paragraph. Isn't the SRS for Groth16 very structured? For example, it contains consecutive powers in the exponent similar to KZG's SRS. How would this be a uniform random string? Unless, Groth16 has a "mode" where it operates solely on a CRS. If so, would you have a reference for this? $\endgroup$
    – Wilson
    Aug 24, 2022 at 17:39
  • $\begingroup$ You are perfectly right: I mis-parsed Groth16 as GrothSahai08. I should update my answer: what I said does not hold for Groth16. $\endgroup$ Aug 25, 2022 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.