Paper 2019/612

Simulation-Extractable SNARKs Revisited

Helger Lipmaa

Abstract

The most efficient SNARKs (e.g., Groth, 2016) have a brittle and difficult-to-verify knowledge-soundness proof in the generic model. This makes it nontrivial to modify such SNARKs to, e.g., satisfy simulation-extractability or to implement some other language instead of QAP (Quadratic Arithmetic Program). We propose knowledge-sound and non-black-box strong any-simulation-extractable (SASE) subversion-zero knowledge SNARKs for QAP that is designed to have a relatively simple security proof. The knowledge-sound SNARK is similar to the mentioned SNARK of Groth, except it has fewer trapdoors. To achieve SASE, we add to it a one-time simulation-extractable QA-NIZK for a subspace language. Moreover, we give a simple characterization of languages like SAP, SSP, and QSP in the terms of QAP and show how to modify the SNARK for QAP correspondingly. The only prior published efficient simulation-extractable SNARK was for the somewhat impractical SAP language. We prove soundness under subversion algebraic knowledge assumptions that are a concrete version of the (subversion) algebraic group model.

Note: The second version (from July 13, 2019) differs significantly from the first eprint version from May 31, 2019.The main difference is in the handling of simulation-extractability (SE): the earlier version achieved ASE but not SASE.The current version of this paper achieves SASE by using tags; this changed the SE SNARKs somewhat but their efficiency remains comparable to the SE SNARKs in the earlier version. Due to the use of tags, we stopped using the full power of the generic bilinear group model in the soundness / SE proofs and added a lengthy description of the AGM and tautological knowledge assumptions. The third version (July 23) includes subversion zero knowledge.