International Association for Cryptologic Research

International Association
for Cryptologic Research


Constant-Size zk-SNARKs in ROM from Falsifiable Assumptions

Helger Lipmaa , University of Tartu
Roberto Parisella , Simula UiB
Janno Siim , Simula UiB
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
Abstract: We prove that the seminal KZG polynomial commitment scheme (PCS) is black-box extractable under a simple falsifiable assumption ARSDH. To create an interactive argument, we construct a compiler that combines a black-box extractable non-interactive PCS and a polynomial IOP (PIOP). The compiler incurs a minor cost per every committed polynomial. Applying the Fiat-Shamir transformation, we obtain slightly less efficient variants of well-known PIOP-based zk-SNARKs, such as Plonk, that are knowledge-sound in the ROM under the ARSDH assumption. Importantly, there is no need for idealized group models or knowledge assumptions. This results in the first known zk-SNARKs in the ROM from falsifiable assumptions with both an efficient prover and constant-size argument.
  title={Constant-Size zk-SNARKs in ROM from Falsifiable Assumptions},
  author={Helger Lipmaa and Roberto Parisella and Janno Siim},