Overview:

The objective of this unit is to give an overview of the state-of-the-art in fully homomorphic encryption (FHE), one of the most promising application of lattice-based cryptography. FHE allows to safely encrypt data, while permitting anyone to perform arbitrary computations over it. The result of a (homomorphic) computation on encrypted data is an encryption of the actual result of the same computation run over the plain data.

After brief reminders about lattices in cryptography, the course will focus on the recent advances in building fully-homomorphic encryption. We will cover the following:

  • Learning with Errors (LWE) and Ring Learning with Errors (RLWE) problems
  • Public-Key Encryption from (R)LWE
  • Fully Homomorphic Encryption (FHE) from theory to practice: BFV/BGV, GSW, TFHE constructions
  • FHE for Approximate Computations: CKKS
  • Bootstrapping
  • Advanced Security Notions: Circuit-Privacy, IND-CPA-D Security, Threshold FHE
  • Applications: Private-Information Retrieval, Compact Zero-Knowledge Proofs, Threshold Cryptography
We will cover definitions and security models for each notion, and detail constructions and security reductions to the hardness of algorithmic problems that are conjectured hard.

Objectives:

  • Understand cryptographic functionalities: Definitions, security requirements, and limitations.
  • Acquire a toolkit on fully homomorphic computation.
  • Be able to read state-of-the art articles in lattice cryptography, and in particular FHE.

Prerequisites:

There is no requirement for attending this class but it is recommended to have taken an introductory class on cryptography before. Students should also be familiar with complexity theory, probabilities, and algebra.

Evaluation:

50% homework + 50% final exam.
Homework is available here (due date: Jan. 13): [pdf]

Final exam:

The final exam works as follows:

  1. Pick an article from a list of selected papers; the list is available on this [pad]
  2. Write a 3-page report on the article; (due date: Jan. 17)
  3. Oral exam on Jan. 23, 1pm-6pm, in room B2: 15' presentation + 15' questions (details below).
The oral exam will start by a presentation of the selected paper. You will have 15 minutes for your presentation, then will follow 15 minutes for questions. Questions will start by a question about one of the classes, picked at random from a list of questions, then we will ask questions about the article you chose. The schedule will be available a week in advance; in the meantime, please let us know if you have constraints.

List of questions:
  1. Explain how to perform multiplications with CKKS.
  2. Explain the bootstrapping of CKKS.
  3. Describe the GSW scheme.
  4. Describe how to implement plaintext-ciphertext matrix multiplication using BLAS.
  5. Define circuit-privacy and how to obtain it using noise flooding.

Prior classes:

  • Nov. 18 - Introduction to FHE, search/decision learning with errors, hardness of LWE, LPS Encryption, Ring-LWE
  • Nov. 21 - Ring-LWE encryption, additive homomorphism, CKKS encodings
  • Nov. 25 - Homomorphic operations with CKKS, moduli chain
  • Nov. 28 - Bootstrapping CKKS
  • Dec. 2 - GSW
  • Dec. 5 - Transciphering and rate 1 FHE
  • Dec. 9 - JKLS, Plaintext-Ciphertext Matrix-Vector multiplication
  • Dec. 12 - Hermes, Plaintext-Ciphertext Matrix-Matrix multiplication
  • Dec. 16 - Circuit-privacy, PIR, PSI
  • Dec. 19 - Discrete CKKS