Vuorovaikutuksesta turvattomuuteen: (laajennetun) Fiat-Shamir-muunnoksen murtaminen

Proof and argument systems are core building blocks of modern cryptography, enabling a prover to convince a verifier that a claimed statement is true. The Fiat-Shamir (FS) transform is a general method for removing interaction from public-coin proof and argument systems by replacing the verifier's random challenges with deterministic hashes of the intermediate protocol transcript. Security analyses in the Random Oracle Model (ROM), together with the absence of attacks on deployed protocols, have provided confidence in the robustness of FS and have made it widely used in practice. However, a series of contrived counterexamples in the standard model show that the security of FS cannot be established in full generality and even practical deployments lack a formal standard-model security proof and rely on the heuristic security provided by the ROM instead. A recent attack by Khovratovich, Rothblum, and Soukhanov (KRS, CRYPTO~2025) on deployed succinct-argument systems based on the protocol of Goldwasser, Kalai, and Rothblum (GKR) makes this threat far more concrete than earlier counterexamples and shake the confidence in FS. The KRS attack exploits structural features of the GKR protocol via diagonalization and applies fairly broadly. In response, Arnon and Yogev (AY, CRYPTO~2025) propose an extended Fiat-Shamir (XFS) transform intended to prevent such attacks. In this thesis we (i) give a simple (contrived) counterexample to XFS, further illustrating the challenges of soundly removing interaction in general, and (ii) study the Fiat-Shamir transform of the SumCheck protocol when instantiated with the arithmetization-friendly hash function Poseidon. Concretely, for (ii) we identify a structured variant of the CICO problem and show that an efficient solver for this problem enables a malicious prover to cheat in the Fiat-Shamir-transformed SumCheck protocol. We further show how the same technique extends to protocols that invoke SumCheck as a subroutine, including GKR and HyperPlonk.