Paper 2023/569

From Polynomial IOP and Commitments to Non-malleable zkSNARKs

Antonio Faonio, EURECOM
Dario Fiore, IMDEA Software
Markulf Kohlweiss, University of Edinburgh
Luigi Russo, EURECOM
Michal Zajac, Nethermind
Abstract

We study sufficient conditions for compiling 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 prove systems, such as Plonk and Marlin. 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 prove systems. Only the proof that KZG satisfies this relaxed simulation extractability property relies on the algebraic group model (AGM) and random oracle (RO). We thus isolate the use of (and thus the reliance on) these strong heuristics.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2023
Keywords
polynomial commitmentsnon-malleabilitysimulation-extractabilityzero-knowledgecommit-and-proveIOP
Contact author(s)
antonio faonio @ eurecom fr
dario fiore @ imdea org
markulf kohlweiss @ ed ac uk
russol @ eurecom fr
michal @ nethermind io
History
2023-10-09: revised
2023-04-22: received
See all versions
Short URL
https://ia.cr/2023/569
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/569,
      author = {Antonio Faonio and Dario Fiore and Markulf Kohlweiss and Luigi Russo and Michal Zajac},
      title = {From Polynomial {IOP} and Commitments to Non-malleable {zkSNARKs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/569},
      year = {2023},
      url = {https://eprint.iacr.org/2023/569}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.