Paper 2021/511

What Makes Fiat--Shamir zkSNARKs (Updatable SRS) Simulation Extractable?

Chaya Ganesh, Hamidreza Khoshakhlagh, Markulf Kohlweiss, Anca Nitulescu, and Michal Zajac

Abstract

We show that three popular universal zero-knowledge SNARKs (Plonk, Sonic, and Marlin) are updatable SRS simulation extractable NIZKs and signatures of knowledge (SoK) out-of-the-box avoiding any compilation overhead. Towards this we generalize results for the Fiat--Shamir (FS) transformation, which turns interactive protocols into signature schemes, non-interactive proof systems, or SoK in the random oracle model (ROM). The security of the transformation relies on rewinding to extract the secret key or the witness, even in the presence of signing queries for signatures and simulation queries for proof systems and SoK, respectively. We build on this line of work and analyze multi-round FS for arguments with a structured reference string (SRS). The combination of ROM and SRS, while redundant in theory, is the model of choice for the most efficient practical systems to date. We also consider the case where the SRS is updatable and define a strong simulation extractability notion that allows for simulated proofs with respect to an SRS to which the adversary can contribute updates. We define three properties (trapdoor-less zero-knowledge, rewinding-based knowledge soundness, and a unique response property) that are sufficient for argument systems based on multi-round FS to be also simulation extractable in this strong sense. We show that Plonk, Sonic, and Marlin satisfy these properties, and conjecture that many other argument systems such as Lunar, Basilisk, and transparent variants of Plonk fall within the reach of our main theorem.

Note: Major update, addition of updatable SRS treatment. New title, abstract, and authors.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
simulation-extractabilityzksnarknizkfiat-shamir transformationupdateable SRS
Contact author(s)
chaya @ iisc ac in
hamidreza @ cs au dk
mkohlwei @ inf ed ac uk
anca @ protocol ai
m p zajac @ gmail com
History
2022-05-09: last of 5 revisions
2021-04-23: received
See all versions
Short URL
https://ia.cr/2021/511
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/511,
      author = {Chaya Ganesh and Hamidreza Khoshakhlagh and Markulf Kohlweiss and Anca Nitulescu and Michal Zajac},
      title = {What Makes Fiat--Shamir zkSNARKs (Updatable SRS) Simulation Extractable?},
      howpublished = {Cryptology ePrint Archive, Paper 2021/511},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/511}},
      url = {https://eprint.iacr.org/2021/511}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.