Fiat-Shamir Security of FRI and Related SNARKs

Alexander R. Block; Albert Garreta; Jonathan Katz; Justin Thaler; Pratyush Ranjan Tiwari; Michał Zając

Paper 2023/1071

Fiat-Shamir Security of FRI and Related SNARKs

Alexander R. Block

, Georgetown University, University of Maryland, College Park

Albert Garreta, Nethermind, Basque Center of Applied Mathematics (BCAM)

Jonathan Katz, University of Maryland, College Park

Justin Thaler, Georgetown University, a16z crypto research

Pratyush Ranjan Tiwari, Johns Hopkins University

Michał Zając, Nethermind

Abstract

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 publication details.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in ASIACRYPT 2023
Keywords: Non-Interactive Proofs Fiat-Shamir Transformation SNARKs
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
History: 2024-03-05: last of 7 revisions; 2023-07-09: received; See all versions
Short URL: https://ia.cr/2023/1071
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1071,
      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{https://eprint.iacr.org/2023/1071}},
      url = {https://eprint.iacr.org/2023/1071}
}