[Resource Topic] 2019/612: Simulation-Extractable SNARKs Revisited

Welcome to the resource topic for 2019/612

Simulation-Extractable SNARKs Revisited

Authors: Helger Lipmaa


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.

ePrint: https://eprint.iacr.org/2019/612

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .