Time: Fri 09:30-13:00
Location: A201
Instructors: Prahladh Harsha and Mrinal Kumar
Homepage: https://www.tifr.res.in/~prahladh/teaching/2025-26/probsystems/

CSS.501.1: Probabilistic Proof Systems and applications to Cryptography

Course outline

This course will be a reading course on probabilistic proof systems with a focus on applications to cryptography.
A tentative list of topics to be covered are as follows.

1. Basics of Interactive Proofs: The sum-check protocol, interactive proof for #SAT, IP=PSPACE, doubly efficient interactive proofs, the GKR protocol.
2. Probabilistically Checkable Proofs: Construction of PCPs from GKR, computationally sound proofs.
3. Zero-Knowledge Proofs: ZKPs for NP, the Fiat-Shamir paradigm, correlation intractable hash functions, soundness of Fiat-Shamir under the standard model, noninteractive ZKPs from LWE.
4. Succinct Non-Interactive Arguments: Succinct non-interactive arguments for Batch NP (BARGs) from LWE, Hash-and-BARG paradigm for constructing SNARGs.
5. Additional Topics: Interactive Oracle Proofs (IOPs), Succinct non-interactive arguments of knowledge (SNARKs) from Polynomial IOPs, Fiat-Shamir via List-Recoverable Codes, Practical attacks on Fiat-Shamir.

References