Overview

The theory of interactive proofs has been one of the most successful developments in complexity theory since the 80s. The study of how algorithms interact and the complexity classification of what can be computed this way led to beautiful and foundational results in complexity theory, such as the celebrated IP=PSPACE results which shed light on the surprising power of interaction and randomness in proof systems, but also represented the first major example of an equivalence between complexity classes that escaped the relativization barrier, a barrier at which complexity theorists had been stuck for long.

In the 90s, the study of interactive proofs led to the development of zero-knowledge proofs, a concept that transformed cryptography and paved the way to numerous modern applications, including but not restricted to digital signatures, secure computation, anonymous credentials, and other authentication mechanisms, CCA security, and many more. More recently, the study of succinct interactive proofs and arguments has seen an impressive development due to its applications to cryptocurrencies and anonymous transaction systems, and succinct proof systems are routinely implemented and deployed in the real world.

Get a strong background on the mathematical and complexity-theoretic foundations of interactive proofs through some of its major achievements (IP=PSPACE, zero-knowledge proofs for all statements in NP). Explore how these foundational results introduced techniques and methods that enabled the development of modern succinct argument systems (arithmetization, interactive generalizations of PCP-style proof systems). Learn some of the latest developments in the area.

Basic notions of computability theory and complexity theory, basic notions of probability. First-year master's level in standard algebra, algorithms, and cryptology.

2-hour class sessions (with slides or blackboard lessons), followed by 1h of tutorial. Tutorials will typically consist of answering questions and providing corrections for exercises given at the end of the 2-hour class session.

Two of the tutorials will be replaced by a 1h correction of the midterm homework (given to the students after the first half of the course) and by a 1h collaborative focus on some research articles addressing specific points left aside by the course (articles distributed to groups of students in advance).

• Geoffroy Couteau, CNRS Research Scientist at Université Paris Cité, IRIF

The first course is on Wednesday, December 10, 12:45 to 15:45. The course is taught weekly (Wednesdays 12:45 to 15:45) until February 25th, 2026, except during the weeks of December 22nd to January 2nd (Winter holidays). The outline below might change slightly. Each item corresponds to one week (2h of courses + 1h of tutorial).

1. Brief reminders on basic notions of complexity theory: Turing Machines, P, BPP, and NP, PSPACE examples (polynomial identity testing, 3 coloring). Definition of the classes IP, AM, coAM. Examples on each, examples to show IP contains non-trivial complexity classes (GNI - graph non-isomorphism).
2. Structural results about IP: deterministic-IP = NP, non-interactive-IP = MA (widely conjectured equal to NP). GNI is in AM (suggests AM not in NP). AM[constant] = AM[2]. CoNP ⊆ IP. Arithmetization: The arithmetization of a problem and the sumcheck protocol. Proofs of correctness and soundness for the sumcheck protocol.
3. Proof that IP = PSPACE, the arithmetization of true quantified boolean formulas.
4. Zero-Knowledge: definition of honest-verifier zero-knowledge, examples: zero-knowledge for the graph isomorphism problem. Zero-knowledge for all of NP via 3-coloring, using encryption/commitments.
5. Proofs versus arguments, arguments of knowledge, the PCP theorem. CRHF, Merkle commitments, and the Kilian protocol for succinct arguments.
6. Schnorr signature and Schnorr proofs. The notion of special soundness. The Fiat-Shamir heuristic, and the Forking Lemma. Chaum-Pedersen proofs for proving discrete logarithm equality. Generalization to linear group morphisms (Maurer Proofs). Sigma Protocols.
7. Succinct arguments of knowledge: compressed Sigma Protocols, Bulletproofs, and SNARKs.
8. Interactive Oracle Proofs, Polynomial Interactive Oracle proofs, Polynomial commitments. Examples of commitment schemes, via compressed sigma protocols and Fast Reed-Solomon Interactive Proofs (FRI).

Session 1. Partial exam, in the form of homework, given at the end of the 4th course; duration: two weeks. The partial gives rise to feedback from the students after correction. Written exam in the classroom during the exam period at the end of the period. All written documents are authorized. Final grade = max(E, (P+E)/2), where E=exam grade, P=partial grade.

Session 2. At the request of the students concerned. With few exceptions, session 2 is only granted to students who have passed and failed session 1. The format depends on particular cases, and may take the form of a written or oral exam, or another form. Session note 2 replaces session note 1 where applicable.