Prover-efficient commit-and-prove zero-knowledge SNARKs. (2017)

• Record Type: Journal Article
• Authors: Lipmaa, Helger
• Is Part Of: International journal of applied cryptography. Volume 3:Number 4(2017)
• Page Start: 344
• Page End: 362
• Publication Date: 2017
• Subjects: 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; Data encryption (Computer science) -- Periodicals; Cryptography -- Periodicals; Computer security -- Periodicals; 652.8
• Languages: English
• ISSNs: 1753-0563

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.