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 prover, or are non-adaptive and based on an commitment scheme that does depend 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.
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 Costello Second eprint version (28.09.2014) is thoroughly updated, and includes several new results
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- Commit-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