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 20-minute talks followed by 5 minutes of questions.

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)

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