Simulation extractable versions of Groth’s zk-SNARK revisited
Open Access
- 5 September 2023
- journal article
- research article
- Published by Springer Nature in International Journal of Information Security
- Vol. 23 (1) , 431-445
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. $$\textsf{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 $$\textsf{Groth16}$$ to efficiently achieve strong Simulation extractability, which is shown to be a necessary requirement in some applications. In this paper, we revise the Random oracle based variant of $$\textsf{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 (Baghery et al. in CANS 20, volume 12579 of LNCS, Springer, Heidelberg. pp 453-461, 2020), which saved 1 pairing in the verification, and was proven in the generic group model. Our new construction also improves on BG18 in that our proofs are in the algebraic group model with Random Oracles and reduces security to standard computational assumptions in bilinear groups (as opposed to using the full power of the generic group model (GGM)). We implement our proposed simulation extractable zk-SNARK (SE zk-SNARK) along with BG18 in the 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 simulation extractable (SE) schemes in most dimensions and it has very close efficiency to the original $$\textsf{Groth16}$$ .
Keywords
Funding Information
- European Research Council (Advanced Grant ERC-2015-AdG-IMPaCT)
This publication has 23 references indexed in Scilit:
- On the Size of Pairing-Based Non-interactive Arguments2016
- Zerocash: Decentralized Anonymous Payments from Bitcoin2014
- Scalable Zero Knowledge via Cycles of Elliptic Curves2014
- Pinocchio: Nearly Practical Verifiable Computation2013
- Quadratic Span Programs and Succinct NIZKs without PCPs2013
- Short Signatures Without Random Oracles and the SDH Assumption in Bilinear GroupsJournal of Cryptology, 2007
- On Signatures of Knowledge2006
- Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures2006
- Complexity of a determinate algorithm for the discrete logarithmMathematical Notes, 1994
- Non-interactive zero-knowledge and its applications1988