Fall 2023

**Lectures**: Tuesday & Thursday, 12:30pm-1:50pm (Room CSE 2154)**Instructor**: Daniele Micciancio (Office Hour: Tuesday 3:30pm-4:30pm, CSE 4214)**TA**: Yizhao Zhang (Office Hour: Friday 10am-11am, CSE B215)**Tools:**- Discussion Board: piazza
- Homework submission: gradescope

If you are enrolled in the class, you should get access to piazza and gradescope automatically through canvas. Other than that, we will not make use of canvas. Homework assignments and other course material will be posted on this webpage.

CSE208 is an **advanced**, **graduate
level** course in cryptography, and assumes a solid background in
cryptography, as provided, for example, by the introductory graduate
cryptography course CSE207. The most important course prerequisite is a
working understanding of the definitional/theoretical security framework
of modern cryptography, i.e., how to rigorously formulate security
requirements, and anlyze candidate cryptographic constructions with
respect to them. Familiarity with a number of common cryptographic
primitives, like public key encryption, digital signatures, hash
functions and commitment schemes is also assumed.

Building on what you have already learned in your introductory crypto course, CSE208 explores more complex primitives and protocols, which typically combine cryptography with some form of general purpose comptuation, like zero knowledge proof systems, functional encryption, forms of verifiable computation, secure two-party and multi-party computation, and fully homomorphic encryption.

In Fall 2023, the course will focus on **Fully Homomorphic
Encryption (FHE)**, i.e., encryption schemes that allow the
evaluation of arbitrary functions on encrypted data.

The course has no textbook. Reading/study material for the course will consist of lecture notes (mostly slides from lecture), research papers and surveys. Anything below the dashed line is material from a previous edition of the course, which you can use as a reference and or take a peek at what we may be doing next. But this quarter the course will a bit different. As we progress through the course, past material will be updated and moved above the line, and new material may be posted.

Lecture notes:

**Course Introduction (slides)****Fully Homomorphic Encryption from the Ground Up**: slides from invited talk at Eurocrypt 2019. See motivations/applications pp.1-9. If you want to watch the whole talk, you can find it hereSupplemental reading: some magazine articles with informal presentation of FHE

**Computing arbitrary functions on encrypted data**(Gentry, CACM 2010 [preface])**Computing Blindfolded: New Developments in Fully Homomorphic Encryption**(Vaikuntanathan, FOCS 2011)**Fully Homomorphic Encryption: Cryptography’s Holy Grail**(Wu, XRDS 2015)

Homework 1: Due Oct 10 (submit on gradescope)

Lecture notes:

**Defining FHE (slides)**Composability and Bootstrapping

**(slides)**. (This is an extract from a longer talk given at the**Simons Institute 10th Annirsary Symposium**and**FHE.org**)Read

**“Fully Composable Homomorphic Encryption (DRAFT)”**for a more detailed presentation of composability and bootstrapping.Supplemental reading: For more information about circular (in)security, see the following papers and references therein

- Circular Security Is Complete for KDM Security (Kitagawa & Matsuda, Asiacrypt 2020)
- Separating Semantic and Circular Security for Symmetric-Key Bit Encryption from the Learning with Errors Assumption (Goyal, Koppula & Waters, Eurocrypt 2017)
- Separating IND-CPA and Circular Security for Unbounded Length Key Cycles (Goyal, Koppula & Waters, PKC 2017)
- Circular Security Separations for Arbitrary Length Cycles from LWE (Koppula & Waters, CRYPTO 2016)
- Three’s Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE (Alamati & Peikert, CRYPTO 2016)

Homework 2: Due Oct 17 (submit on gradescope)

Papers:

**The LWE Problem**(Regev, CCC 2010, invited survey)**How to encrypt with the LPN problem**(Gilbert, Robshaw, Seurin, ICALP 2008)

Homomorphic addition (linearity) and multiplication was covered in blackboard lectures using the gadget product operations. (See class notes on “Gadget LWE”.) The following slides are from the previous year and use somehow different notation, still may be a useful reference.

Papers:

**Homomorphic Encryption: from Private-Key to Public-Key**(R. Rothblum, TCC 2011)**Efficient Fully Homomorphic Encryption from (Standard) LWE**(Brakerski & Vaikuntanathan, FOCS 2011 / SIAM J. Computing 2014)**(Leveled) Fully Homomorphic Encryption without Bootstrapping**(Brakerski, Gentry & Vaikuntanathan - ITCS 2012 / ToCT 2014)**Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP**(Brakerski - Crypto 2012)**Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based**(Gentry, Sahai & Waters, Crypto 2013)

Slides from previous year:

For a good survey/introduction to FHEW/TFHE, see

- Bootstrapping in FHEW-like Cryptosystems (Micciancio & Polyakov, WAHC 2021)

A recent method using BGV/BFV to bootstrap FHEW-like ciphertexts is

- Amortized Functional Bootstrapping in less than 7ms, with ~O(1) polynomial multiplications (Liu & Wang, Asiacrypt 2023)

**Fundamentals of Fully Homomorphic Encryption - A Survey**(Brakerski, in “Providing Sound Foundations for Cryptography”, ACM books, 2019)**Homomorphic Encryption**(Halevi, in “Tutorials on the Foundations of Cryptography”, 2017)