Liens transverses ENS de Lyon

INFO5169 : Interactive and Non-Interactive Proofs in Complexity and Cryptography

Interactive and Non-Interactive Proofs in Complexity and Cryptography

Niveau M2

Discipline(s) Informatique

ECTS 5.00

Période 1e semestre

Localisation Site Monod

Année 2021-2022

 Public externe (ouverts aux auditeurs de cours)

Lundi Après-midi
Mercredi Matin
Horaires du cours
Mon 3.45pm - 5.45pm
Wed 10.15am - 12.15pm
Objectif du cours

The concept of proofs arise in most aspects of mathematics and computer science. The goal of this class is to introduce some powerful notions in cryptography, such as zero-knowledge proofs, which aim to prove a certain statement without disclosure of any information about the proof itself. These notions have found numerous applications in the recent years, such as electronic voting or online transactions.

In this course, we will cover several important results regarding proofs in complexity and in cryptography. We will start from basics in complexity and aim to address some advanced notions in cryptography. The course will introduce the following notions:

  • Reminders on complexity theory: P, NP, BPP, and PSPACE classes
  • Interactive randomized proofs: Arthur and Merlin classes AM, MA, and the IP class
  • Relations between theses classes: AM[k] = AM, IP = PSPACE
  • Reminders on cryptography: pseudorandom generators, commitments, sigma-protocols
  • Zero-knowledge proofs for NP: coin-flipping over the phone and 3-coloring
  • Non-Interactive Zero-Knowledges (NIZK) proofs: definitions, impossibility results, and various models
  • Basics on NIZKs: FLS protocol, hidden-bit model, Fiat-Shamir transform
  • Applications of NIZKs: CCA-secure encryption (Naor-Yung), electronic voting, and more
  • Postquantum NIZKs: Correlation-Intractable Hash Functions, Fully-Homomorphic Encryption
  • And more: Linear PCP, PCP, SNARKs, NIWIs, etc.



  • Understand advanced notions of complexity and cryptography: Definitions, security requirements, relations between them, and their limitations.
  • Learn about the foundations of modern research in proofs in cryptography
  • Be able to read state-of-the art articles on the related topics.

It is highly recommended to have taken an introductory class on complexity theory. Basic knowledge about cryptography could be helpful though we will introduce all notions again.

Evaluation : 50% homeworks + 50% oral presentation of a paper in a selected list of papers (20' talk + 10' questions)

Second session : oral exam

Teachers: Alain Passelègue (ENS Lyon) and Geoffroy Couteau (Paris 7).

1st wave of M2 classes.

From September 6 to November 10.

- Computational complexity, a modern approach, Boaz Barak & Sanjeev Arora

- References for the corresponding papers will be provided during each lecture

Modifié le :
02/07/2021 11:52:36