Abstract: SNARKs are powerful cryptographic primitives that allow a prover to produce a succinct proof of a computation. Two key goals of SNARK research are to minimize the size of the proof and to minimize the time required to generate the proof. In this work, we present new SNARK constructions that push the frontier on both of these goals.
Our first construction, Pari, is a SNARK that achieves the smallest proof size amongst *all* known SNARKs. Specifically, Pari achieves a proof size of just two group elements and two field elements, which, when instantiated with the BLS12-381 curve, totals just 160 bytes, smaller than that of Groth16 [Groth, EUROCRYPT '16] and Polymath [Lipmaa, CRYPTO '24].
Our second construction, Garuda, is a SNARK that reduces proof generation time by supporting, for the first time, arbitrary "custom" gates and *free* linear gates. To demonstrate Garuda's performance, we implement and evaluate it, and show that it provides significant prover-time savings compared to both the state-of-the-art SNARKs (Groth16 and HyperPlonk [EUROCRYPT '22]).
Both constructions rely on a new cryptographic primitive: "equifficient" polynomial commitment schemes that enforce that committed polynomials have the same representation in particular bases. We provide both rigorous security definitions for this primitive as well as efficient constructions for univariate and multilinear polynomials.
Joint work with Michel Dellepere & Pratyush Mishra. Paper: eprint.iacr.org/2024/1245
Bio: Alireza Shirzad is a first-year PhD student at Penn advised by Dr. Pratyush Mishra. He is primarily interested in designing proof systems and SNARKs. Before coming to Penn, He obtained his Master’s degree in Secure communications and Cryptography in 2023 and a bachelor’s degree in Electrical Engineering in 2021 from Sharif University of Technology.