Paper 2020/1306

Simulation Extractable Versions of Groth’s zk-SNARK Revisited

Karim Baghery and Zaira Pindado and Carla Ràfols

Abstract

Among various Non-Interactive Zero-Knowledge (NIZK) arguments, zk-SNARKs are the most efficient in terms of proof size and verification, which are two important criteria for large scale applications. Currently, Groth's construction from Eurocrypt'16, $\mathsf{Groth16}$, is the most efficient and widely deployed one. However, it is proven to achieve only knowledge soundness, which does not prevent attacks from the adversaries who have seen simulated proofs. There has been considerable progress in modifying $\mathsf{Groth16}$ to achieve simulation extractability to guarantee the non-malleability of proofs. We revise the Simulation Extractable version of $\mathsf{Groth16}$ proposed by Bowe and Gabizon in the Random Oracle Model, the most efficient one in terms of prover efficiency and common reference string size among the candidates. We present two variations of their construction which require 4 pairings in the verification, instead of 5. The first one has the same performance as Bowe and Gabizon's in all other parameters. The second one gets rid of the Random Oracle at the cost of a collision-resistant hash function, a single new element in the common reference string, and one exponentiation in the target group for the verifier. Both of our variants are among the most efficient simulation extractable versions of $\mathsf{Groth16}$ in most dimensions.

Note: This is the full version of the CANS'20 paper. The first construction in section 3 is new and appears in this version.