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
-
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},
url = {https://eprint.iacr.org/2014/396}
}
