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

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 20-minute talks followed by 5 minutes of questions.
Homework 1 is available here: [pdf]
Homework 2 is available here: [pdf]
The list of papers for final evaluation is available here: [pad]
The schedule is available on the same [pad]. If it does not work for you, just find someone to switch slots and send us an email cc'ing everyone involved in the permutation.

Prior classes:

  • Sep. 6 - Reminders on complexity: Turing machines, P, NP, NP-completeness, Polynomial Hierarchy, PSPACE ([AB], chapters 1-5) - [scribe - Yan Garito]
  • Sep. 8 - Boolean circuits, P/poly, lower bounds, randomized computation, BPP ([AB], chapters 6-7)
  • Sep. 13 - Amplification, interactive proofs, deterministic vs probabilistic verifier, IP class, AM class, graph (non)-isomorphism, protocols in IP/AM ([AB], chapters 7-8)
  • Sep. 15 - Set lower bound AM protocol, Chernoff bounds, PSPACE = NPSPACE, IP = PSPACE (beginning) ([AB], chapter 8)
  • Sep. 20 - IP = PSPACE (end) ([AB], chapter 8), perfect zero-knowledge, GI in PZK ([G], chapter 4)
  • Sep. 22 - Statistical ZK, computational ZK, pseudorandom generators => commitments, 3-coloring in CZK ([G], chapter 4)
  • Sep. 27 - Proofs of Knowledge, GNI/3-coloring PoK, sigma protocols, Schnorr identification protocol ([G], chapter 4 - [BS], chapter 19)
  • Sep. 29 - Sigma protocols: special soundness and special ZK, splitting lemma, DLog and DDH protocols, AND and OR of sigma protocols [CDS], application to whitelisting, 5-round ZK proofs, Pedersen commitment
  • Oct. 4 - Witness indistinguishability, Common Reference/Random String (CRS) model, 3-round ZK proofs in the CRS model
  • Oct. 6 - Impossibility NIZK in the plain model, random oracle model, Fiat-Shamir transform, Schnorr's signature, forking lemma [PS]
  • Oct. 11 - E-voting, NIZK in the hidden bits model [FLS]
  • Oct. 13 - Correlation-Intractable Hash Functions, NIZK from fully-homomorphic encryption [CLW]
  • Oct. 18 - NIZK in the hidden bits model [FLS] (end)
  • Oct. 20 - Fully-homomorphic encryption from lattices [GSW]

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