Simulation Extractable Versions of Groth’s zk-SNARK Revisited

Oussama Amine; Karim Baghery; Zaira Pindado; Carla Ràfols

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2020/1306

Simulation Extractable Versions of Groth’s zk-SNARK Revisited

Oussama Amine, University of Oslo, Oslo, Norway

Karim Baghery

, COSIC, KU Leuven, Belgium

Zaira Pindado, Dusk, Amsterdam, Netherlands

Carla Ràfols

, Universitat Pompeu Fabra, Barcelona, Spain

Abstract

Zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs) are the most efficient proof systems in terms of proof size and verification. Currently, Groth's scheme from EUROCRYPT 2016, $\textsf{Groth16}$, is the state-of-the-art and is widely deployed in practice. $\mathsf{Groth16}$ is originally proven to achieve knowledge soundness, which does not guarantee the non-malleability of proofs. There has been considerable progress in presenting new zk-SNARKs or modifying $\mathsf{Groth16}$ to efficiently achieve $\textit{strong}$ Simulation Extractability (SE), which is shown to be a necessary requirement in some applications. In this paper, we revise the Random Oracle (RO) based variant of $\mathsf{Groth16}$ proposed by Bowe and Gabizon, BG18, the most efficient one in terms of prover efficiency and CRS size among the candidates, and present a more efficient variant that saves $2$ pairings in the verification and $1$ group element in the proof. This supersedes our preliminary construction, presented in CANS 2020 [BPR20], which saved 1 pairing in the verification, and was proven in the Generic Group Model (GGM). Our new construction also improves on BG18 in that our proofs are in the Algebraic Group Model (AGM) with Random Oracles and reduces security to standard computational assumptions in bilinear groups (as opposed to using the full power of the GGM). We implement our proposed SE zk-SNARK along with BG18 in the $\textsf{Arkworks}$ library and compare the efficiency of our scheme with some related works. Our empirical experiences confirm that our SE zk-SNARK is more efficient than all previous SE schemes in most dimensions and it has very close efficiency to the original $\mathsf{Groth16}$.

Note: A preliminary version of this paper appeared in the Proceedings of the 19th International Conference on Cryptology and Network Security, CANS 2020.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. International Journal of Information Security
Keywords: NIZK zk-SNARK Strong Simulation Extractability Algebraic Group Model Random Oracle Model
Contact author(s): oussamaa @ math uio no
baghery karim @ gmail com
zaira @ dusk network
carla rafols @ upf edu
History: 2023-08-10: last of 3 revisions; 2020-10-20: received; See all versions
Short URL: https://ia.cr/2020/1306
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1306,
      author = {Oussama Amine and Karim Baghery and Zaira Pindado and Carla Ràfols},
      title = {Simulation Extractable Versions of Groth’s zk-SNARK Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1306},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1306}},
      url = {https://eprint.iacr.org/2020/1306}
}