
Soundness of the Fiat-Shamir Paradigm in the Standard Model, Part 1
Yael T. Kalai lectures on the Fiat-Shamir paradigm, the technique used to convert interactive proof systems into non-interactive ones by replacing a verifier's random challenges with a hash function. This session, part of MIT's 6.5630 Advanced Topics in Cryptography, examines whether that transformation can be proven sound in the standard model rather than the idealized random oracle model. Kalai introduces correlation-intractable (CI) hash functions, the tool needed to instantiate Fiat-Shamir securely, discusses their existence in the random oracle model, and works through a simple counterexample showing the construction can fail in the plain model. The lecture is blackboard-style and technical, aimed at students already familiar with interactive proofs and hash function assumptions, and sets up the deeper constructions covered in later sessions of the course.