Cryptology ePrint Archive: Report 2019/641

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 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 will be extended with one element from $\mathbb{G}_1$, one element from $\mathbb{G}_2$, plus a bit string that totally will be still less than 200 bytes for 128-bit security. Its verification is dominated with 4 parings which is the most efficient verification among current SE zk-SNARKs.

Category / Keywords: cryptographic protocols / Zero-knowledge proofs, zk-SNARKs, simulation extractability, CRS model

Date: received 2 Jun 2019, last revised 9 Jun 2019

Contact author: karim baghery at ut ee

Available format(s): PDF | BibTeX Citation

Version: 20190609:182047 (All versions of this report)

Short URL: ia.cr/2019/641


[ Cryptology ePrint archive ]