Cryptology ePrint Archive: Report 2017/540

Snarky Signatures: \\ Minimal Signatures of Knowledge from Simulation-Extractable SNARKs

Jens Groth and Mary Maller

Abstract: We construct a pairing-based simulation-extractable succinct non-interactive argument of knowledge (SE-SNARK) that consists of only 3 group elements and has highly efficient verification. By formally linking SE-SNARKs to signatures of knowledge, we then obtain a succinct signature of knowledge consisting of only 3 group elements.

SE-SNARKs enable a prover to give a proof that they know a witness to an instance in a manner which is: (1) \textit{succinct} - proofs are short and verifier computation is small; (2) \textit{zero-knowledge} - proofs do not reveal the witness; (3) \textit{simulation-extractable} - it is only possible to prove instances to which you know a witness, even when you have already seen a number of simulated proofs.

We also prove that any pairing-based signature of knowledge or SE-SNARK must have at least 3 group elements and 2 verification equations. Since our constructions match these lower bounds, we have the smallest size signature of knowledge and the smallest size SE-SNARK possible.

Category / Keywords: Signature of knowledge, SNARK, non-interactive zero-knowledge proof, simulation-extractability

Original Publication (with minor differences): IACR-CRYPTO-2017

Date: received 5 Jun 2017, last revised 18 Apr 2019

Contact author: mary maller 15 at ucl ac uk

Available format(s): PDF | BibTeX Citation

Note: Added details about deriving the relation dependent CRS.

Version: 20190418:163653 (All versions of this report)

Short URL: ia.cr/2017/540


[ Cryptology ePrint archive ]