Constant-Size zk-SNARKs in ROM from Falsifiable Assumptions

Helger Lipmaa; Roberto Parisella; Janno Siim

Paper 2024/173

Constant-Size zk-SNARKs in ROM from Falsifiable Assumptions

Helger Lipmaa

, University of Tartu

Roberto Parisella

, Simula UiB

Janno Siim

, Simula UiB

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.

Note: The full version of the Eurocrypt 2024 paper

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in EUROCRYPT 2024
Keywords: Black-box knowledge-soundness polynomial commitment scheme polynomial IOP witness-extended emulation zk-SNARKs
Contact author(s): helger lipmaa @ gmail com
robertoparisella @ hotmail it
jannosiim @ gmail com
History: 2024-02-06: approved; 2024-02-05: received; See all versions
Short URL: https://ia.cr/2024/173
License: CC BY

BibTeX

@misc{cryptoeprint:2024/173,
      author = {Helger Lipmaa and Roberto Parisella and Janno Siim},
      title = {Constant-Size zk-SNARKs in ROM from Falsifiable Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/173},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/173}},
      url = {https://eprint.iacr.org/2024/173}
}