Cryptology ePrint Archive: Report 2014/396

Prover-Efficient Commit-And-Prove Zero-Knowledge SNARKs

Helger Lipmaa

Abstract: Zk-SNARKs (succinct non-interactive zero-knowledge arguments of knowledge) are needed in many applications. Unfortunately, all previous zk-SNARKs for interesting languages are either inefficient for the prover, or are non-adaptive and based on a commitment scheme that depends both on the prover's input and on the language, i.e., they are not commit-and-prove (CaP) SNARKs. We propose a proof-friendly extractable commitment scheme, and use it to construct prover-efficient adaptive CaP succinct zk-SNARKs for different languages, that can all reuse committed data. In new zk-SNARKs, the prover computation is dominated by a linear number of cryptographic operations. We use batch-verification to decrease the verifier's computation; importantly, batch-verification can be used also in QAP-based zk-SNARKs.

Category / Keywords: cryptographic protocols / Batch verification, commit-and-prove, CRS, NIZK, numerical NP-complete languages, range proof, SUBSETSUM, zk-SNARK

Original Publication (in the same form): IJACT 3 (4), 2017

Date: received 30 May 2014, last revised 23 Apr 2020

Contact author: helger lipmaa at gmail com

Available format(s): PDF | BibTeX Citation

Note: Third eprint version (16.11.2015) has been reworded in the language of commit-and-prove SNARKs. Includes batch verification, and minimal comparison with CostelloSecond eprint version (28.09.2014) is thoroughly updated, and includes several new results. The conference version (Africacrypt 2016) was updated compared to that. The current eprint version from 23.04.2020 corresponds to the journal version of the paper (IJACT 3 (4), 2017).

Version: 20200423:143238 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]