Paper 2019/612
Simple Yet Efficient Knowledge-Sound and Non-Black-Box Any-Simulation-Extractable ZK-SNARKs
Helger Lipmaa
Abstract
Motivated by applications like verifiable computation and privacy-preserving cryptocurrencies, many efficient pairing-based SNARKs were recently proposed. However, the most efficient SNARKs like the one by Groth (EUROCRYPT 2016) have a very brittle and difficult-to-verify knowledge-soundness proof in the generic model. Due to that, it is difficult to modify such SNARKs to, e.g., satisfy simulation-extractability or to implement some other language instead of QAP (Quadratic Arithmetic Program). We propose a template for constructing knowledge-sound and non-black-box any-simulation-extractable NBBASE SNARKs for QAP. This template is designed so that the knowledge-soundness and even NBBASE proofs of the new SNARKs are quite simple. The new knowledge-sound SNARK for QAP is very similar to the mentioned SNARK of Groth, except it has fewer trapdoors. To achieve NBBASE, we add to the knowledge-sound SNARK a few well-motivated extra steps, while its security proof is even simpler due to the use of a second verification equation. 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 SAP.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- NIZKQAPQSPSNARKSAPSSPsimulation-extractabilityzero-knowledge
- Contact author(s)
- helger lipmaa @ gmail com
- History
- 2023-05-16: withdrawn
- 2019-06-03: received
- See all versions
- Short URL
- https://ia.cr/2019/612
- License
-
CC BY