Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / NIZK, QAP, QSP, SNARK, SAP, SSP, simulation-extractability, zero-knowledge

Date: received 31 May 2019

Contact author: helger lipmaa at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190603:070252 (All versions of this report)

Short URL: ia.cr/2019/612


[ Cryptology ePrint archive ]