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 & Sum-Check Protocol (Ratnakar)
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 (Ratnakar)
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 (Ratnakar)
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; Gol1 ]
Mar 06
4. Succinct Arguments (Ratnakar)
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 (Hrishikesh)
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 (Hrishikesh)
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; Gol2; CCHLRRW; HLR ]
Mar 27
7. Soundness of Fiat-Shamir in Standard Model (Ratnakar)
Overview of FS-paradigm in standard model: state-of-the-art, CI hash from standard LWE via a Rate-1 FHE scheme
 [ Sri, Lec 6 ]
[ Lom; PS; HLR ]
Apr 03 No lecture: Good Friday
Apr 10 No lecture: Cancelled
Apr 17
8. Interactive Oracle Proofs I (Ratnakar)
Interactive Oracel Proofs (IOPs), polynomial IOPs, relation to succinct arguments, polynomial IOP for rank-1 CSPs (R1CS-SAT)
 [ Tha, Sec. 10 ]
[ Chi, Lec. 12 ]
[ BCS; RRR ]
Apr 24
9. Interactive Oracle Proofs II (Ratnakar)
Polynomial IOPs for R1CS-SAT, FRI polynomial commitment scheme, succinct IOP for R1CS-SAT
 [ Tha, Sec. 10 ]
[ BGSTZ, Lec. 8 (7 Mar) ]
[ BBHR ]
May 01
10. Proximity gaps for Reed-Solomon Codes (Mrinal)
Reed-Solomon (RS) codes, proximity gap question, proximity gap for RS codes in the unique-decoding regime, application to FRI protocol
 [ BBHR; BCIKS ]

Tentative schedule for future lectures

[ lectures | references ]

May 08
11. LIGERO
[ Tha, Sec. 10.5 ]
[ BGSTZ, Lec. 7 (28 Feb) ]
[ AHIV ]

References

[ lectures | tentative schedule ]

[AHIV] Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. “LIGERO: lightweight sublinear arguments without a trusted setup”. Des. Codes Cryptogr., 91(11). pp. 3379–3424. 2023. [ doi | iacr ]
[BBHR] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. “Fast Reed-Solomon Interactive Oracle Proofs of Proximity”. In Proc. 45th International Colloq. of Automata, Languages and Programming (ICALP). pp. 14:1–14:17. 2018. [ doi | eccc ]
[BCIKS] Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. “Proximity Gaps for Reed-Solomon Codes”. J. ACM, 70(5). pp. 31:1–31:57. 2023. [ doi | eccc | iacr ]
[BCS] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. “Interactive Oracle Proofs”. In Proc. 14th International Theory of Crypt. Conf. (TCC), Part II. pp. 31–60. 2016. [ doi | iacr ]
[BGSTZ] Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, and Yupeng Zhang. “Zero Knowledge Proofs”. 2023. [ url ]
[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 ]
[Gol1] Oded Goldreich. “On Doubly-Efficient Interactive Proof Systems”. Found. Trends Theor. Comput. Sci., 13(3). pp. 158–246. 2018. [ doi | url ]
[Gol2] 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 ]
[Lom] Alex Lombardi. “Fiat-Shamir in the Standard Model: Current state-of-the-art and future challenges [video]”. Proofs Workshop in the Simons Program on 'Cryptography 10 Years Later', July 2025. [ video ]
[Mic] Silvio Micali. “Computationally Sound Proofs”. SIAM J. Comput., 30(4). pp. 1253–1298. 2000. [ doi ]
[PS] Chris Peikert and Sina Shiehian. “Noninteractive Zero Knowledge for NP from (Plain) Learning with Errors”. In Proc. 39th CRYPTO, Part I. pp. 89–114. 2019. [ doi | iacr ]
[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 ]
[Sri] Akshayaram Srinivasan. “CSC2419: Topics in Cryptography - Lattice-based Cryptography”. 2025. [ url ]
[Tha] Justin Thaler. “Proofs, Arguments, and Zero-Knowledge”. Found. Trends Priv. Secur., 4(2-4). pp. 117–660. 2022. [ doi | url ]