A Unified Framework for Non-Universal SNARKs

Helger Lipmaa

Paper 2021/1700

A Unified Framework for Non-Universal SNARKs

Helger Lipmaa

Abstract

We propose a general framework for non-universal SNARKs. It contains (1) knowledge-sound and non-black-box any-simulation-extractable (ASE), (2) zero-knowledge and subversion-zero knowledge SNARKs for the well-known QAP, SAP, QSP, and QSP constraint languages that all by design have \emph{relatively} simple security proofs. The knowledge-sound zero-knowledge SNARK is similar to Groth's SNARK from EUROCRYPT 2016, except having fewer trapdoors, while the ASE subversion-zero knowledge SNARK relies on few additional conditions. We prove security in a weaker, more realistic version of the algebraic group model. We characterize SAP, SSP, and QSP in terms of QAP; this allows one to use a SNARK for QAP directly for other languages. Our results allow us to construct a family of SNARKs for different languages and with different security properties following the same proof template. Some of the new SNARKs are more efficient than prior ones. In other cases, the new SNARKs cover gaps in the landscape, e.g., there was no previous ASE or Sub-ZK SNARK for SSP or QSP.

Note: The full version of a PKC 2022 paper. It supersedes https://eprint.iacr.org/2019/612, though the latter has some independent results not carried over to the current work.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: NIZK QAP QSP SNARK SAP SSP simulation-extractability subversion zero-knowledge
Contact author(s): helger lipmaa @ gmail com
History: 2021-12-30: received
Short URL: https://ia.cr/2021/1700
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1700,
      author = {Helger Lipmaa},
      title = {A Unified Framework for Non-Universal {SNARKs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1700},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1700}
}