WIKINDX Resources

Block, A. R., Garreta, A., Katz, J., Thaler, J., Tiwari, P. R., & Zajac, M. (2023). Fiat-shamir security of fri and related snarks. Cryptology ePrint Archive, 
Added by: Jack (2023-07-29 03:04)   Last edited by: Jack (2023-07-29 03:05)
Resource type: Journal Article
BibTeX citation key: Block2023
View all bibliographic details
Categories: Not Monero-focused
Creators: Block, Garreta, Katz, Thaler, Tiwari, Zajac
Collection: Cryptology ePrint Archive
Views: 12/274
Attachments   FIAT_SHAMIR_SNARKS.pdf [5/94] URLs
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 𝛿-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 𝛿-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.
WIKINDX 6.5.0 | Total resources: 187 | Username: -- | Bibliography: WIKINDX Master Bibliography | Style: American Psychological Association (APA)