tl;dr: Notes on the Fiat-Shamir transform and its security.
Related work
The Fiat-Shamir transform1 is a classic technique for making public-coin interactive proofs non-interactive by replacing the verifier’s random challenges with hash function outputs. It was introduced in the context of identification and signature schemes, but it generalizes to (almost?) any multi-round interactive proof.
Canetti et al.2 give a rigorous treatment of the Fiat-Shamir transform, bridging the gap between its widespread practical use and its theoretical foundations. They identify sufficient conditions under which Fiat-Shamir preserves soundness, working in both the random oracle model and the standard model.
Block et al.3 study soundness notions for interactive oracle proofs (IOPs), including round-by-round soundness. They show that $(k_1, \ldots, k_\mu)$-special soundness implies round-by-round soundness, which in turn implies that applying Fiat-Shamir yields a (knowledge?)-sound non-interactive proof.
-
How To Prove Yourself: Practical Solutions to Identification and Signature Problems, by Fiat, Amos and Shamir, Adi, in Advances in Cryptology — CRYPTO’ 86, 1987 ↩
-
Fiat-Shamir: from practice to theory, by Canetti, Ran and Chen, Yilei and Holmgren, Justin and Lombardi, Alex and Rothblum, Guy N. and Rothblum, Ron D. and Wichs, Daniel, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019, [URL] ↩
-
On Soundness Notions for Interactive Oracle Proofs, by Block, Alexander R. and Garreta, Albert and Tiwari, Pratyush Ranjan and Zając, Michał, in Journal of Cryptology, 2024, [URL] ↩