Paper 2023/1071

Fiat-Shamir Security of FRI and Related SNARKs

Alexander R. Block, Georgetown University, University of Maryland, College Park
Albert Garreta, Nethermind
Jonathan Katz, University of Maryland, College Park
Justin Thaler, Georgetown University, a16z crypto research
Pratyush Ranjan Tiwari, Johns Hopkins University
Michał Zając, Nethermind

We establish new results on the Fiat-Shamir (FS) security of several protocols that are widely used in practice, and we provide general tools for establishing similar results for others. More precisely, we: (1) prove the FS security of the FRI and batched FRI protocols; (2) analyze a general class of protocols, which we call $\delta$-correlated, that use low-degree proximity testing as a subroutine (this includes many "Plonk-like" protocols (e.g., Plonky2 and Redshift), ethSTARK, RISC Zero, etc.); and (3) prove FS security of the aforementioned "Plonk-like" protocols, and sketch how to prove the same for the others. We obtain our first result by analyzing the round-by-round (RBR) soundness and RBR knowledge soundness of FRI. For the second result, we prove that if a $\delta$-correlated protocol is RBR (knowledge) sound under the assumption that adversaries always send low-degree polynomials, then it is RBR (knowledge) sound in general. Equipped with this tool, we prove our third result by formally showing that "Plonk-like" protocols are RBR (knowledge) sound under the assumption that adversaries always send low-degree polynomials. We then outline analogous arguments for the remainder of the aforementioned protocols. To the best of our knowledge, ours is the first formal analysis of the Fiat-Shamir security of FRI and widely deployed protocols that invoke it.

Note: Added acknowledgement of some concurrent work with ethStark v1.2

Available format(s)
Cryptographic protocols
Publication info
Non-Interactive ProofsFiat-Shamir TransformationSNARKs
Contact author(s)
alexander r block @ gmail com
albert @ nethermind io
jkatz2 @ gmail com
justin thaler @ georgetown edu
pratyush @ cs jhu edu
michal @ nethermind io
2023-08-04: last of 4 revisions
2023-07-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexander R. Block and Albert Garreta and Jonathan Katz and Justin Thaler and Pratyush Ranjan Tiwari and Michał Zając},
      title = {Fiat-Shamir Security of FRI and Related SNARKs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1071},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.