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-soundnesspolynomial commitment schemepolynomial IOPwitness-extended emulationzk-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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2024/173}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.