
Fiat-Shamir Paradigm and Zero-Knowledge Proofs, Part 1
Yael T. Kalai continues MIT's 6.5630 Advanced Topics in Cryptography with a lecture on removing interaction from zero-knowledge proofs. She proves that the Merkle hash construction is collision resistant, then shows how the Fiat-Shamir paradigm converts interactive protocols into non-interactive ones by replacing a verifier's random challenges with a hash function. The lecture's core work is proving the soundness of the Kilian-Micali protocol in the random oracle model, walking through the argument step by step on the board. This is a technical, proof-heavy session aimed at students who already know the basics of interactive proofs and hash-based commitments, building toward succinct non-interactive arguments. Ninety-three minutes of blackboard cryptography from MIT OpenCourseWare, part of a graduate-level sequence on advanced topics in the field.