Prover-efficient commit-and-prove zero-knowledge snarks
type: Item
instance of: scholarly article
title: Prover-efficient commit-and-prove zero-knowledge snarks
zbMATH Open document ID: 1428.94085
DOI: 10.1504/IJACT.2017.089355
author: Helger Lipmaa
published in: International Journal of Applied Cryptography
publication date: 2018-11-26T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68P25
zbMATH DE Number: 6984955
zbMATH Keywords: batch verification
zbMATH Keywords: commit-and-prove
zbMATH Keywords: CaP
zbMATH Keywords: common reference string
zbMATH Keywords: CRS
zbMATH Keywords: non-interactive zero knowledge
zbMATH Keywords: NIZK
zbMATH Keywords: numerical NP-complete languages
zbMATH Keywords: range proof
zbMATH Keywords: subset-sum
zbMATH Keywords: zk-SNARK
MaRDI profile type: Publication
full work available at URL: ijact.2017.089355
OpenAlex ID: W3203017069
description: scientific article; zbMATH DE number 6984955