Title: Prover-efficient commit-and-prove zero-knowledge SNARKs

Authors: Helger Lipmaa

Addresses: Institute of Computer Science, University of Tartu, Estonia

Abstract: Succinct non-interactive zero-knowledge arguments of knowledge (Zk-SNARKs) 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.

Keywords: batch verification; commit-and-prove; CaP; common reference string; CRS; non-interactive zero knowledge; NIZK; numerical NP-complete languages; range proof; Subset-Sum; zk-SNARK.

DOI: 10.1504/IJACT.2017.089355

International Journal of Applied Cryptography, 2017 Vol.3 No.4, pp.344 - 362

Received: 23 Feb 2017
Accepted: 29 Mar 2017
Published online: 21 Jan 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article