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

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

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

BibTeX

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