International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Polymath: Groth16 Is Not The Limit

Authors:
Helger Lipmaa , University of Tartu
Download:
DOI: 10.1007/978-3-031-68403-6_6 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
Abstract: Shortening the argument (three group elements or 1536 / 3072 bits over the BLS12-381/BLS24-509 curves) of the Groth16 zk-SNARK for R1CS is a long-standing open problem. We propose a zk-SNARK Polymath for the Square Arithmetic Programming constraint system using the KZG polynomial commitment scheme. Polymath has a shorter argument (1408 / 1792 bits over the same curves) than Groth16. At 192-bit security, Polymath's argument is nearly half the size, making it highly competitive for high-security future applications. Notably, we handle public inputs in a simple way. We optimized Polymath's prover through an exhaustive parameter search. Polymath's prover does not output G2 elements, aiding in batch verification, SNARK aggregation, and recursion. Polymath's properties make it highly suitable to be the final SNARK in SNARK compositions.
BibTeX
@inproceedings{crypto-2024-34308,
  title={Polymath: Groth16 Is Not The Limit},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68403-6_6},
  author={Helger Lipmaa},
  year=2024
}