CSS.501.1 | Probabilistic Proof Systems

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

CSS.501.1 | Probabilistic Proof Systems and Applications to Cryptography

Reading Course (January-May 2026)

Lectures

[ tentative schedule | references ]

Feb 13
1. Interactive Proofs and the Sum-Check Protocol
Administrivia; Interactive proofs (IP) - definition and history; sum-check protocol; Interactive proof for #SAT
 [ Kal, Lec. 1 ]
[ Tha, Sec. 3.1, 4.1-4.2 ]
[ LFKN ]
Feb 20
2. Doubly Efficient Interactive Proofs
Doubly efficient IP - definition; Example: counting triangles in a graph; low-degree extension; doubly efficient IP for all bounded depth computations (GKR protocol)
 [ Kal, Lec. 2 ]
[ Tha, Sec. 3.5, 4.3, 4.6 ]
[ GKR ]
Feb 27
3. Analysis of GKR Protocol
Discussion on doubly-effient IP (GKR and RRR protocols); detailed analysis of GKR protocol; IP = PSPACE
 [ Kal, Lec 3 ]
[ Tha, Sec. 4.6 ]
[ GKR; RRR; Gola ]
Mar 06
4. Succinct Arguments
Argument systems; succinct arguments for NP (Kilian); ingredients: PCPs and vector commitments; Merkle-tree constructions: vector commitments from collision-resistant hash functions
 [ Kal, Lec 4-5 ]
[ Tha, Sec. 7.3-7.6, 9.2 ]
[ Kil; Mic ]
Mar 13
5. Fiat-Shamir Heuerstic, ROM and ZK Proofs
Fiat-Shamir Heurestic, Insecurity of FS in the usual model, Random Oracle Model (ROM), Zero Knowledge protocols, ZK protocol for Hamiltonian cycle and discussion of its security under FS, Soundness of FS under ROM for constant-round protocols withe negligible soundness
 [ Kal, Lec 6 ]
[ Tha, Sec 5, 11 ]
[ FS; GK ]
Mar 20
6. NIZKs for NP from circular-secure FHE
Correlation-intractable (CI) hash functions, CI hash functions from fully circular-secure homomorphic encryption, security of Fiat-Shamir with CI hash functions, non-interactive zero-knowledge arguments (NIZKs)
 [ Kal, Lec 7 ]
[ DNRS; Golb; CCHLRRW; HLR ]

Tentative schedule for future lectures

[ lectures | references ]

Mar 27
7. Sigma protocols
Apr 03 No lecture: Good Friday
Apr 10
8. Interactive Oracle Proofs (IOPs) I
Apr 17
9. Interactive Oracle Proofs (IOPs) II
Apr 24
10. Succinct Non-interactive Arguments (SNARGs) I
May 01 No lecture: Buddha Purnima
May 08
11. Succinct Non-interactive Arguments (SNARGs) II

References

[ lectures | tentative schedule ]

[CCHLRRW] Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs. “Fiat-Shamir: from practice to theory”. In Proc. 51st ACM Symp. on Theory of Computing (STOC). pp. 1082–1090. 2019. [ doi | iacr1 | iacr2 ]
[Chi] Alessandro Chiesa. “Foundations and Frontiers of Probabilistic Proofs”. 2023. [ url ]
[DNRS] Cynthia Dwork, Moni Naor, Omer Reingold, and Larry J. Stockmeyer. “Magic Functions”. J. ACM, 50(6). pp. 852–921. 2003. [ doi ]
[FS] Amos Fiat and Adi Shamir. “How to Prove Yourself: Practical Solutions to Identification and Signature Problems”. In Proc. 6th CRYPTO. pp. 186–194. 1986. [ doi ]
[GK] Shafi Goldwasser and Yael Tauman Kalai. “On the (In)security of the Fiat-Shamir Paradigm”. In Proc. 44th IEEE Symp. on Foundations of Comp. Science (FOCS). pp. 102–113. 2003. [ doi | eccc | iacr ]
[GKR] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. “Delegating Computation: Interactive Proofs for Muggles”. J. ACM, 62(4). pp. 27:1–27:64. 2015. [ doi | eccc ]
[Gola] Oded Goldreich. “On Doubly-Efficient Interactive Proof Systems”. Found. Trends Theor. Comput. Sci., 13(3). pp. 158–246. 2018. [ doi | url ]
[Golb] Oded Goldreich. “On Parallel Repetition of Interactive Proof Systems”. In Proc. Computational Complexity and Local Algorithms - On the Interplay Between Randomness and Computation. pp. 119–126. 2025. [ doi | url ]
[HLR] Justin Holmgren, Alex Lombardi, and Ron D. Rothblum. “Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge)”. In Proc. 53rd ACM Symp. on Theory of Computing (STOC). pp. 750–760. 2021. [ doi | eccc | iacr ]
[Kal] Yael Tauman Kalai. “6.5630: Advanced Topics in Cryptography”. 2023. [ url ]
[Kil] Joe Kilian. “A note on efficient zero-knowledge proofs and arguments (extended abstract)”. In Proc. 24th ACM Symp. on Theory of Computing (STOC). pp. 723–732. 1992. [ doi ]
[LFKN] Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. “Algebraic Methods for Interactive Proof Systems”. J. ACM, 39(4). pp. 859–868. 1992. [ doi ]
[Mic] Silvio Micali. “Computationally Sound Proofs”. SIAM J. Comput., 30(4). pp. 1253–1298. 2000. [ doi ]
[RRR] Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. “Constant-Round Interactive Proofs for Delegating Computation”. SIAM J. Comput., 50(3). 2021. [ doi | eccc ]
[Tha] Justin Thaler. “Proofs, Arguments, and Zero-Knowledge”. Found. Trends Priv. Secur., 4(2-4). pp. 117–660. 2022. [ doi | url ]