Simulation extractability of Fiat-Shamir transformation of multi-round protocols


Chaya Ganesh October 22, 2021.


The Fiat–Shamir transformation turns public-coin protocols into signature schemes, non-interactive proof systems, and signatures of knowledge (SoK). We study malleability attacks against Fiat-Shamir transformed multi-round protocols. In this talk, we will look at simulation extractability of two classes of protocols:

  1. Bulletproofs: We show that Bulletproofs (or any other similar multi-round proof system satisfying some form of weak unique response property) achieve simulation-extractability in the algebraic group model.
  2. SRS-based SNARKs: We formally define simulation extractability for protocols in the random oracle model (ROM) which use a structured reference string (SRS). We show sufficient conditions for compiling via the Fiat–Shamir transformation public-coin multi-round interactive protocols with SRS into simulation-extractable NIZK proof systems. We 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 show that three popular universal zero knowledge SNARKs — Plonk, Sonic, and Marlin — are simulation extractable.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Derandomization from Time-Space Tradeoffs
  • Polynomial Time Byzantine Agreement with Optimal Resilience
  • Quantum Pseudoentanglement
  • Demystifying the border of depth-3 algebraic circuits
  • Why we couldn't prove SETH hardness of CVP for even norms, Subset-SUM, and Many more!