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.

Final exam:

The final exam works as follows:

  1. Pick an article from a list of selected papers;
  2. Write a 3-page report on the article;
  3. Oral exam : 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.

Prior classes:

  • Nov. 18 - Introduction to FHE, search/decision learning with errors, hardness of LWE, LPS Encryption, Ring-LWE