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

Note: Added details about deriving the relation dependent CRS.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in CRYPTO 2017
Keywords
Signature of knowledgeSNARKnon-interactive zero-knowledge proofsimulation-extractability
Contact author(s)
mary maller 15 @ ucl ac uk
History
2019-04-18: last of 3 revisions
2017-06-08: received
See all versions
Short URL
https://ia.cr/2017/540
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/540,
      author = {Jens Groth and Mary Maller},
      title = {Snarky Signatures: \\ Minimal Signatures of Knowledge from Simulation-Extractable SNARKs},
      howpublished = {Cryptology ePrint Archive, Paper 2017/540},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/540}},
      url = {https://eprint.iacr.org/2017/540}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.