### Simulation Extractability in Groth's zk-SNARK

Shahla Atapoor and Karim Baghery

##### Abstract

A Simulation Extractable (SE) zk-SNARK enables a prover to prove that she knows a witness for an instance in a way that the proof: (1) is succinct and can be verified very efficiently; (2) does not leak information about the witness; (3) is simulation-extractable -an adversary cannot come out with a new valid proof unless it knows a witness, even if it has already seen arbitrary number of simulated proofs. Non-malleable succinct proofs and very efficient verification make SE zk-SNARKs an elegant tool in various privacy-preserving applications such as cryptocurrencies, smart contracts and etc. In Eurocrypt 2016, Groth proposed the most efficient pairing-based zk-SNARK in the CRS model, but its proof is vulnerable to the malleability attacks. In this paper, we show that one can efficiently achieve simulation extractability in Groth's zk-SNARK by some changes in the underlying language using an OR construction. Analysis and implementations show that in practical cases overload has minimal effects on the efficiency of original scheme which currently is the most efficient zk-SNARK. In new construction, proof size is extended with one element from $\mathbb{G}_1$, one element from $\mathbb{G}_2$, plus a bit string that totally is less than 256 bytes for 128-bit security. Its verification is dominated with 4 pairings which is the most efficient verification among current SE zk-SNARKs.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. 3rd International Workshop on Cryptocurrencies and Blockchain Technology - CBT'19
Keywords
Zero-knowledge proofsSNARKssimulation extractabilityCRS model
Contact author(s)
karim baghery @ ut ee
History
2019-08-21: last of 2 revisions
See all versions
Short URL
https://ia.cr/2019/641

CC BY

BibTeX

@misc{cryptoeprint:2019/641,
author = {Shahla Atapoor and Karim Baghery},
title = {Simulation Extractability in Groth's zk-SNARK},
howpublished = {Cryptology ePrint Archive, Paper 2019/641},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/641}},
url = {https://eprint.iacr.org/2019/641}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.