Paper 2019/612

Simulation-Extractable SNARKs Revisited

Abstract

The most efficient SNARKs (e.g., Groth, 2016) have a brittle and difficult-to-verify knowledge-soundness proof in the generic model, which 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 tag-based strong any-simulation-extractable ($\tagSASE$) subversion-zero knowledge SNARKs for QAP that by design have a relatively simple security proof. The knowledge-sound SNARK is similar to Groth's SNARK, except having fewer trapdoors. To achieve $\tagSASE$, we add to it a one-time simulation-extractable QA-NIZK for a subspace language. We give a simple characterization of languages like SAP, SSP, and QSP in terms of QAP and show how to modify the SNARKs for QAP correspondingly. The only prior published efficient simulation-extractable SNARK was for the impractical SAP language. We prove soundness and tagSASE under hash-algebraic knowledge (HAK) assumptions that are a concrete version of the hash-algebraic group model. The framework of HAK assumptions is another major contribution of this paper. We also show that one can achieve tagless SASE by using an efficient transformation.

Note: The second eprint 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. In fact, its ASE security proofs contained a subtle error, introduced in the last moment during a submission rush. 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 (AK and SAK) assumptions. The third eprint version (from July 23, 2019) adds subversion-security and many typo fixes. The fourth eprint version (from Feb 8, 2020) has a better explanation of the (H)AK assumption framework. We renamed SAK assumptions to HAK assumptions. We differentiated clearly between the tag-based (as used in most of this paper) and tagless SASE. We clarified why tagSASE is sufficient in applications like UC-security. Nevertheless, we described an efficient transformation from tagSASE SNARKs to tagless SASE SNARKs. We simplified the proof of tagSASE (it does not rely on the hardness of the language anymore.) The new SNARKs are however the same as in the July 23, 2019 version. We also corrected a lot of small typos (and small but non-essential mistakes). ---- 23.04.2023: This eprint is fully subsumed by https://eprint.iacr.org/2021/1700 (and the corresponding PKC 2022) paper that adds new results and corrects some of the mistakes. Please cite the PKC 2022 paper instead. (We will not retract it since this eprint has a number of citation.)