Overview of the course:

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-Knowledge (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.

Course objectives:

  • 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.

Prerequisites:

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:

Homeworks (50%) and article presentation (50%). Presentations will be 12-minute talks followed by 10 minutes of questions.
Homework (due on Jan. 25, 2023) is available here: [pdf]
The list of papers for final evaluation is available here: [pad]

Prior classes:

  • Nov. 16 - Reminders on complexity: Turing machines, P, NP, NP-completeness, Polynomial Hierarchy, PSPACE ([AB], chapters 1-5)
  • Nov. 17 - Boolean circuits, P/poly, lower bounds, randomized computation, BPP, polynomial identity testing, perfect matching in bipartite graphs, RP, coRP, ZPP ([AB], chapters 6-7)
  • Nov. 23 - Amplification, interactive proofs, deterministic vs probabilistic verifier, IP class, AM class, graph (non)-isomorphism, protocols in IP/AM ([AB], chapters 7-8)
  • Nov. 24 - Set lower bound AM protocol, Chernoff bounds, IP = PSPACE (beginning) ([AB], chapter 8)
  • Nov. 30 - TQBF is PSPACE-complete, PSPACE = NPSPACE, Circuit arithmetization, Sumcheck protocol, IP = PSPACE ([AB], chapter 8)
  • Dec. 1 - Perfect zero-knowledge, GI in PZK, Statistical ZK, computational ZK, pseudorandom generators => commitments, 3-coloring in CZK ([G], chapter 4)
  • Dec. 8 - 3-coloring PoK, Proofs of Knowledge ([G], chapter 4 - [BS], chapter 19)
  • Dec. 9 - Sigma protocols: special soundness and special ZK, splitting lemma, DLog and DDH protocols, AND and OR of sigma protocols [CDS]
  • Dec. 15 - Whitelisting, NIZKs, Impossibility NIZK in the plain model, random oracle model, Fiat-Shamir transform, Schnorr's signature [PS]
  • Dec. 16 - Witness indistinguishability, Common Reference/Random String (CRS) model, 3-round ZK proofs in the CRS model
  • Jan. 4 - Fully-homomorphic encryption from lattices [GSW]
  • Jan. 5 - NIZK in the hidden bits model [FLS]
  • Jan. 11 - NIZK in the hidden bits model [FLS] (end)
  • Jan. 12 - Correlation-Intractable Hash Functions, NIZK from fully-homomorphic encryption [CLW]

References:

  • [AB] - Computational Complexity: A Modern Approach, S. Arora, B. Barak | [free preliminary version]
  • [BS] - A Graduate Course in Applied Cryptography, D. Boneh, V. Shoup | [free preliminary version]
  • [G] - Foundations of Cryptography, O. Goldreich | [free preliminary version]
  • [CDS] - Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, R. Cramer, I. Damgard, B. Schoenmakers - Crypto'94
  • [FLS] - Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions, U. Feige, D. Lapidot, A. Shamir - FOCS'90
  • [PS] - Security Proofs for Signature Schemes, D. Pointcheval, J. Stern - Eurocrypt'96
  • [CLW] - Non-Interactive Zero Knowledge and Correlation Intractability from Circular-Secure FHE, R. Canetti, A. Lombardi, D. Wichs - eprint 2018/1248 - merge into Fiat-Shamir: from practice to theory - STOC'19
  • [GSW] - Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based, C. Gentry, A. Sahai, B. Waters - eprint 2013/340 - Crypto'13