Helger Lipmaa's publications

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

Helger Lipmaa. Prover-Efficient Commit-And-Prove Zero-Knowledge SNARKs. In David Pointcheval, Abderrahmane Nitaj and Tajjeeddine Rachidi, editors, Africacrypt 2016, volume 9646 of Lecture Notes in Computer Science, pages 185--206, Fes, Morocco, April 13--15, 2016. Springer, Heidelberg.

File: NA yet

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

Keywords: Commit-and-prove, CRS, NIZK, numerical NP-complete languages, range proof, \textsc{Subset-Sum}, zk-SNARK.


Authors:

Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.