In Semester 1, 2021-2022, I will be teaching CS 6190: Structure versus Hardness in Cryptography.
Course Description
In this course we will closely examine the hardness assumptions underlying cryptography. We will study diverse mathematical structures from both the perspective of conjectured hard problems they yield, and of their underlying structure which enables us to build cryptography from them.
In more detail, we will examine (some subset of) the following assumptions from our twin perspectives:
- Computational and Decision Diffie Hellman
- Bilinear Maps
- Quadratic Residuosity
- Learning With Errors (and its ring variant)
- Learning Parity with Noise
- NTRU
- Indistinguishability Obfuscation and variants
- Multilinear Maps
Administrative Information
Lectures are Wednesdays 2:00- 3:30 pm and Thursdays, 3:25-4:40 pm. Lectures are held in virtual mode, and the link is
here.
First class is on Wednesday 4th August, 2 pm.
Pre-requisites.
The main pre-requisite is a love for puzzles and paradoxes! Aside from that, this course requires mathematical maturity, in particular comfortable working knowledge of linear algebra and probability. An introductory course in cryptography, such as CS 6111 (Foundations of Cryptography) is useful but not strictly necessary.
Requirements.
- Assignments : 30%. Assignments will be open ended in nature and collaboration is encouraged.
- Two Scribes (Template here ): 20%
- Class presentation : 20%
- Final Project: 30%
Policies and Grades.
Collaboration is encouraged but you must write up solutions on your own. You must also write the names of all the people you discussed the problem with. In case you find material that will help you in solving some problems, you should mention the source in your writeup. Class participation will also be taken into account when assigning grades.
I expect all students to behave according to the highest ethical standards. Any cheating or dishonesty of any nature will result in failing the class.
Resources.
Recent papers of relevance. There will be some overlap with
this course at Princeton and
this course at UC Berkeley.
Topics and References
Some tentative topics and references are below.
- Fully Homomorphic Encryption: For circuits, can be constructed from LWE and (without circular security) from iO. For Turing machines, known from extractable witness encryption , for Random Access machines rewindable ORAM and VBB obfuscation.
- Hash Functions and Random Oracles: Random oracles are an idealized primitive that aid in building cryptographic protocols. A recent amazing line of works has shown how to construct hash functions from standard assumptions, that can replace random oracles in several important applications.
- Identity Based Encryption: Was known to be constructible from bilinear maps, quadratic residuosity, Learning With Errors until 2010. In 2017, Garg and Dottling showed that it can be constructed even from the much weaker (or less structured) Decision Diffie Hellman.
- Zero Knowledge: Was known from pairings but for which, a very recent construction by Jain and Jin uses only DDH. Another recent breathrough line of works showed how to construct it from LWE, settling a long standing open problem.
- Deniable Encryption: Known to be constructible from iO with negligible deniability. Recently constructed using FHE with compact ciphertexts but still only polynomial deniability.
- Broadcast Encryption: Known with sublinear CT from bilinear maps and logarithmic (optimal) CT from multilinear maps. Recently logarithmic (optimal) CT obtained from bilinear maps in addition to LWE.
- Traitor Tracing: Recently constructed from LWE.
- Two round MPC: Known from multikey FHE or iO. Recently obtained from pairings and even more recently from minimal assumptions.
Lecture Summaries
| Lecture (Date) |
Topic |
Scribe |
Reference |
Lec 1
(Aug 4) |
Introduction. |
Slides |
None |
Lec 2
(Aug 5) |
Lattices, OWF and Encryption. |
Slides |
Vinod's class notes |
Lec 3
(Aug 11) |
The BGV FHE Scheme. |
Scribe (Simran) |
BGV Paper |
Lec 4
(Aug 12) |
The BGV FHE Scheme (Contd). |
Scribe (Meenakshi) |
Vinod's class notes |
Lec 5
(Aug 18) |
The BGV FHE Scheme: Dimension Switching. |
Scribe (Akhil) |
Vinod's class notes. |
Lec 6
(Aug 19) |
BGV Modulus Switching and bootstrapping |
Scribe (Anuja) |
See Brakerski's scale invariant simplification here. |
Lec 7
(Aug 25) |
The GSW FHE Scheme. |
Scribe (Raghavendra) |
Slides on GSW by Peikert. See Sec 5.1 of this paper for a clean description of the scheme. |
Lec 8
(Aug 26) |
Using Bootstrapping for Deniability. |
No Scribe |
Slides |
Lec 9
(Sept 1) |
Deniable FHE. |
No Scribe |
Slides |
Lec 10
(Sept 2) |
Introduction to iO |
Scribe ( Aadityan) |
Slides by Gentry. Lecture notes on iO. |
Lec 11
(Sept 8) |
Deniable Encryption from iO |
Scribe (Amik) |
Sahai-Waters paper |
Lec 12
(Sept 9) |
Deniable Encryption from iO |
Scribe (Rishi) |
Sahai-Waters paper |
Lec 13
(Sept 16) |
Deniable Encryption from iO |
Scribe (Ratnakar) |
Sahai-Waters paper |
Lec 14
(Sept 22) |
Deniable Encryption from iO |
Scribe (Senjuti) |
Sahai-Waters paper |
Lec 15
(Sept 23) |
Other Applications iO -- Public Key Encryption from Secret Key Encryption |
Scribe (Aditya) |
UCB Lecture notes 1 and 2. |
Lec 16, 17
(Sept 29, 30) |
Other Applications iO |
Scribe (Saswata) |
UCB Lecture notes 1 and 2. |
Lec 18
(Oct 6) |
DL, DDH, Pairings |
Scribe (Anshu) |
ENS de Lyon Lecture notes. |
Lec 19
(Oct 7) |
IBE from Pairings |
Scribe (Satvinder) |
ENS de Lyon Lecture notes. |
Lec 20
(Oct 13) |
IBE from Pairings (Contd) |
Scribe (Somnath) |
ENS de Lyon Lecture notes. |
Lec 21
(Oct 14) |
Broadcast Enc from Pairings and LWE |
No Scribe |
Slides. |
Lec 22
(Oct 21) |
Interactive proofs and Zero Knowledge |
No Scribe |
UCB Lecture Notes. |
Lec 23
(Oct 27) |
Zero Knowledge for NP |
No Scribe |
UCB Lecture Notes. |
Lec 24
(Oct 28) |
Non-Interactive Zero Knowledge |
No Scribe |
UCB Lecture Notes. |
Lec 25, 26, 27, 28
(Nov 10, 11, 17, 18) |
Class Presentations |
No Scribe |
No Reference |