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 18th, 2026, except during the weeks of December 22nd to January 2nd (Winter holidays) and on February 11th. 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).

The first half of the course is largely based on the book Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. The book is available online for free, for example at this link. Other lecture notes will be used on some occasions and will be linked to from this page. Below is an outline of the parts of the book that have been used in each of the courses so far.

First course (December 10):

• Definition of Turing machines: Chapter 1 (1.1, 1.2)
• The class P: 1.4 (see also 1.4.2)
• The class NP: 2.1, 2.2, 2.6
• The class PSPACE: 4.1
• Boolean circuits: 6.1, 6.2, 6.3
• The class BPP: 7.1, 7.2, 7.4, 7.5
• Interactive proofs: 8.1

First tutorial link

Second course (December 17):

• Definition IP, IP[k], AM[k], pc-IP: Chapter 8, definitions 8.6 and 8.10
• GNI is in IP: 8.1.3
• GNI is in AM[2]: Chapter 8, Theorems 8.13 & 8.15, and the set lower bound protocol in 8.2.2
• Proof that IP and AM[k] amplify via parallel repetitions: see the “tree view” of AM & IP in Remark 8.11. The full proof of parallel amplification can be found in Appendix C.1 of Modern Cryptography, Probabilistic Proofs and Pseudorandomness by Oded Goldreich. A point of attention: the result was originally claimed in the seminal 1988 paper by Babai and Moran (Arthur-merlin games: a randomized proof system, and a hierarchy of complexity class), but the proof in the paper is incorrect (this is worth knowing as most lecture notes online point to Babai-Moran for the proof).

Second tutorial link

Third course (January 7):

• End of the proof that IP and AM[k] amplify via parallel repetitions: we use the constructive concentration bound by Impagliazzo and Kabanets from the paper Constructive Proofs of Concentration Bounds
• AM[k+2] = AM[k]: we follow the high level approach of Babai and Moran and reuse the amplification result from the previous course.
• Proof that IP=PSPACE: see 8.3 in Arora-Barak. We follow more closely the lecture notes of Jonathan Katz.

The third course's tutorial was devoted to finishing the tutorial sheets of the previous session.

Fourth course (January 14): End of the proof of IP = PSPACE: see the lecture notes of Jonathan Katz.

• Definition of PZK: our treatment of zero-knowledge follows mostly the presentation from Oded Goldreich in the book Foundations of Cryptography, Volume I. In particular, the definition of perfect zero-knowledge is taken from 4.3.1.1 in Oded's book.

The fourth course's tutorial was devoted to the homework.

Fifth course (January 21):

• Proof of GI in PZK.
• Proof of GNI in PZK. The proof we present differs from the usual treatment in the literature, but a related proof can be found, for example, in the lecture notes of Ivan Damgård.
• Definition of SZK and CZK: see Oded's book.
• Zero-knowledge proofs for NP via reduction to 3-coloring or graph Hamiltonicity. The 3-coloring proof is analyzed in Oded's book, while the Hamiltonicity proof can be found for example in the Ivan's lecture notes.

Third tutorial link

Sixth course (January 28):

• ZK proofs for NP via 3-coloring: statement of the protocol and overview of the main points of the proof.
• Arguments of knowledge: definition, class SZKA
• Notion of succinct arguments

Seventh course (February 4): Part of the material for this course is from Justin Thaler's book.

• The PCP theorem
• Collision-resistant hash functions
• Merkle commitments
• Kilian's succinct argument for NP
• Proofs of knowledge: definition (from Oded's book)

Eighth course (February 18):

• Sigma-protocols, Schnorr proofs
• From HVZK to full ZK via commitments
• Generalization: Sigma-protocol for the same discrete logarithm w.r.t. two bases
• The CDS OR-trick
• Reminder on exponential ElGamal
• Application 1 of Sigma-protocols + CDS: an electronic voting protocol with two candidates
• Application 2 (brief overview): straight-line simulation given a common reference string

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.

The homework assignment can be downloaded here.

Due date: Wednesday, January 28, 1 pm. You can hand it in physically (in class) or by email at couteau@irif.fr. Handwritten or LaTeX, whichever you prefer.

Rules:

• The assignment is not mandatory (cf evaluation modalities).
• The homework is long: it is not necessary to finish it (or even most of it) to get a good grade.
• Try to think of it as a good warm-up for the research work of a PhD:
  • I strongly encourage you, to the best of your ability, to attempt to solve the questions with your (collective) brain(s). That is: think about it alone or in groups, but don't try too much to look for the solution in books, lecture notes, or other online resources.
  • After a sufficiently reasonable amount of thinking, if you are stuck, feel free to use any tool at your disposal to solve it: books, lecture notes, online discussions, AI. But use them cleverly: understand the solutions that you find, fill in any missing details, and write it down in your own words.
• In case you feel an information is missing in the homework, you can either email me, or make by yourself a choice of what you think is a reasonable interpretation of the question.

The final exam will take place on Wednesday, March 4, 12:45 pm, in room 1002. It lasts two hours. All documents (printed or handwritten) are allowed. Electronic devices are not allowed.