
The Kilian-Micali Protocol, Part 1
Yael T. Kalai teaches this session of MIT's 6.5630 Advanced Topics in Cryptography, covering the Kilian-Micali protocol for building interactive arguments. The lecture works through how collision resistant hash functions with local openings combine with probabilistically checkable proofs (PCPs) to produce succinct interactive arguments of knowledge. Kalai develops the construction step by step on the board, tracing how a prover can commit to a PCP via a Merkle-tree-style hash and let a verifier check only a few opened positions rather than the whole proof. As part one of a two part treatment, it lays the groundwork for the security analysis and efficiency claims to follow. The session assumes familiarity with earlier course material on PCPs and hash functions and is aimed at graduate students already versed in complexity theory and cryptographic proof systems.