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
  • Applications: Private-Information Retrieval, Compact Zero-Knowledge Proofs, Universal Thresholdizer
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 highly recommended to have taken an introductory class on cryptography before. Students should also be familiar with complexity theory, probabilities, and algebra.

Evaluation:

50% homework (programming project + report) + 50% oral exam (presentation of research article with a short report and 1 question on the lectures selected from a list).
Homework is available here (due date: Jan. 12): [pdf]
The list of articles for final evaluation is available here: [pad]

Final exam:

The final exam works as follows:

  1. Pick an article from the list in the [pad];
  2. Write a 3-page report on the article (due date: Jan. 19);
  3. Oral exam on Jan. 25: 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 the list of questions below, then we will ask questions about the article you chose. The schedule is available on the [pad].

List of questions:
  1. Define bootstrapping and explain how it works in general.
  2. Describe the GSW scheme.
  3. Define Private Information Retrieval and a simple solution based on FHE.
  4. Explain the BlindRotate algorithm in DM/CGGI.
  5. Explain how to perform multiplications with CKKS.
  6. Explain Binary CKKS.
  7. Define circuit-privacy and how to obtain it using noise flooding.
  8. Describe a construction of a threshold signature scheme from threshold FHE.

Prior classes:

  • Nov. 20 - Learning with errors, ring-LWE, LPS Encryption
  • Nov. 23 - The BGV scheme
  • Nov. 27 - The GSW scheme
  • Nov. 30 - Transciphering, FiLIP, rate-1 FHE, minimal NIZKs, PIR, PSI
  • Dec. 11 - The DM/CGGI scheme
  • Dec. 14 - The CKKS scheme
  • Dec. 18 - Bootstrapping CKKS
  • Jan. 8 - Conversion between FHE schemes (CHIMERA), Binary CKKS (BLEACH), LWE with binary secrets
  • Jan. 11 - Circuit-privacy, noise flooding, washing machine
  • Jan. 15 - IND-CPA-D security, threshold FHE, attacks and countermeasures
  • Jan. 18 - Universal thresholdizer
  • Jan. 22 - Rényi divergence, threshold signatures