LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
The Kilian-Micali Protocol, Part 1
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

The Kilian-Micali Protocol, Part 1

105 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
MIT · Advanced Topics in Cryptography · LECTURE 8

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.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 45 m
Compared with MathematicsLonger than 94%
This series

Advanced Topics in Cryptography

Every lecture in order, sized by its length.

  • Earlier lectures
  • This lecture
  • Still to come
Lecture 8 of 169 h 16 m before this · 21 h 39 m in total

More from this course

12 LECTURES
Interactive Proofs and the Sum-Check Protocol, Part 1

Interactive Proofs and the Sum-Check Protocol, Part 1

MIT · 91 MIN
Interactive Proofs and the Sum-Check Protocol, Part 2

Interactive Proofs and the Sum-Check Protocol, Part 2

MIT · 66 MIN
Doubly Efficient Interactive Proofs, Part 1

Doubly Efficient Interactive Proofs, Part 1

MIT · 113 MIN
Doubly Efficient Interactive Proofs, Part 2

Doubly Efficient Interactive Proofs, Part 2

MIT · 43 MIN
Continuation of the GKR Protocol and Corollaries

Continuation of the GKR Protocol and Corollaries

MIT · 82 MIN
PCP via GKR and Interactive Arguments, Part 1

PCP via GKR and Interactive Arguments, Part 1

MIT · 90 MIN
PCP via GKR and Interactive Arguments, Part 2

PCP via GKR and Interactive Arguments, Part 2

MIT · 71 MIN
Fiat-Shamir Paradigm and Zero-Knowledge Proofs, Part 1

Fiat-Shamir Paradigm and Zero-Knowledge Proofs, Part 1

MIT · 93 MIN
Lecture 6: Fiat-Shamir Paradigm and Zero-Knowledge Proofs, Part 2

Lecture 6: Fiat-Shamir Paradigm and Zero-Knowledge Proofs, Part 2

MIT · 69 MIN
Soundness of the Fiat-Shamir Paradigm in the Standard Model, Part 1

Soundness of the Fiat-Shamir Paradigm in the Standard Model, Part 1

MIT · 94 MIN
Soundness of the Fiat-Shamir Paradigm in the Standard Model, Part 2

Soundness of the Fiat-Shamir Paradigm in the Standard Model, Part 2

MIT · 65 MIN
Succinct Non-Interactive Arguments for Batch NP (BARGs) from LWE, Part 1

Succinct Non-Interactive Arguments for Batch NP (BARGs) from LWE, Part 1

MIT · 82 MIN