Paper 2014/396

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

Helger Lipmaa


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.

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).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. IJACT 3 (4), 2017
Batch verificationcommit-and-proveCRSNIZKnumerical NP-complete languagesrange proofSUBSETSUMzk-SNARK
Contact author(s)
helger lipmaa @ gmail com
2020-04-23: last of 3 revisions
2014-05-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Helger Lipmaa},
      title = {Prover-Efficient Commit-And-Prove Zero-Knowledge SNARKs},
      howpublished = {Cryptology ePrint Archive, Paper 2014/396},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.