International Association for Cryptologic Research

International Association
for Cryptologic Research


From Polynomial IOP and Commitments to Non-malleable zkSNARKs

Antonio Faonio , EURECOM
Dario Fiore , IMDEA
Markulf Kohlweiss , University of Edinburgh
Luigi Russo , EURECOM
Michal Zajac , Nethermind
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2023
Abstract: We study sufficient conditions to compile simulation-extractable zkSNARKs from information-theoretic interactive oracle proofs (IOP) using a simulation-extractable commit-and-prove system for its oracles. Specifically, we define simulation extractability for opening and evaluation proofs of polynomial commitment schemes, which we then employ to prove the security of zkSNARKS obtained from polynomial IOP proof systems. To instantiate our methodology, we additionally prove that KZG commitments satisfy our simulation extractability requirement, despite being naturally malleable. To this end, we design a relaxed notion of simulation extractability that matches how KZG commitments are used and optimized in real-world proof systems. The proof that KZG satisfies this relaxed simulation extractability property relies on the algebraic group model and random oracle model.
  title={From Polynomial IOP and Commitments to Non-malleable zkSNARKs},
  author={Antonio Faonio and Dario Fiore and Markulf Kohlweiss and Luigi Russo and Michal Zajac},