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 SNARK (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) succinct - proofs are short and verifier computation is small; (2) zero-knowledge - proofs do not reveal the witness; (3) 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-NIZK argument 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.
Metadata
- Available format(s)
- Publication info
- Published by the IACR in CRYPTO 2017
- Keywords
- signatures of knowledgeSNARKssimulation soundness
- Contact author(s)
-
mary maller 15 @ ucl ac uk
j groth @ 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
-
CC BY