Welcome to the Spring 2021 web page for CS598DK: Special Topics in Cryptography!
Cryptography, that started as the study of secret communication, has undergone a major revolution in the last few years. It now helps us realize a variety of seemingly impossible tasks: from allowing computations on secret data without revealing the data itself, to offloading computation to untrusted clients while maintaining verifiable results, and even making programs unintelligible while preserving functionality.
This course will cover a selection of such cuttingedge topics in modern cryptography. We will understand how an adversary that breaks advanced protocols can be transformed into an adversary that contradicts basic mathematical assumptions. Our focus will be on understanding key ideas in cryptography research published over the last few years, and identifying new directions and problems for the future.
A major focus of the course will be on postquantum cryptography, based in particular on the learning with errors (LWE) assumption. No prior cryptography background is assumed, however, students are expected to have mathematical maturity. In particular, working knowledge of discrete mathematics and probability is assumed. Familiarity with algorithmic reductions will be useful.
Course Credits: 4
Time: Wednesdays and Fridays, 3.30  4.45 pm
Location: Zoom. Meeting link: here.
Instructor: Dakshita Khurana, dakshita@illinois.edu
Office Hours (updated): Monday 9 am  10 am, Wednesdays and Fridays (after class) by appointment. Zoom link: here.
Important: Please sign up for Piazza for access to course announcements, homeworks, and discussions. Sign up link: here.
Note: Students are encouraged to drop by during office hours (or set up, by email, an appointment to meet) within the first 3 weeks. This will help me learn more about your interests and what you hope to learn from this class, and I can help you with a choice of topic for your project.
We will have lecture notes uploaded on the course webpage, which will serve as the main resource for this course. Here is a list of additional resources.
Similar Course Offerings
Survey on Lattices: By Chris Peikert
Additional Resources: Books and Lecture Notes on Cryptography in General
20%: Class Participation.
The class is intended to be as interactive as possible: you are strongly encouraged to ask questions and offer answers. I will end my lectures with open questions that we will answer interactively during the next class. These questions will be easy to answer if you attend every lecture. Reading prescribed material before the next lecture is recommended to better understand the contents of the course.
40%: Assignments.
You will have 4 written assignments over the course of the semester.
40%: Project.
The purpose of the project is to expose students to research in cryptography. You can pick a project topic of your choice. The project can be a literature survey, or an attempt at original research to answer some open problem in cryptography. I am happy to consult individually with you during office hours or by appointment to provide guidance. You should feel free to work individually, or in teams of 23, and grades will be calibrated accordingly.
How to be Successful in this Course.
Attendance and class participation are important for success in this course. Please do your best to attend every lecture. Active participation in class will take you a long way. If you don't understand something, ask. If you didn't understand, there is a good chance that many others didn't, and you are likely doing everyone a favor. Read in advance of the next class, and be prepared to answer my questions during class.
Lecture Recordings. Class lectures are being recorded and are available for viewing on media space here. Unfortunately these are only available to registered students due to privacy regulations. If you are registered for the course but cannot view these recordings, please send me an email.
The following is a tentative schedule and is subject to change. A good fraction of the content is based on Vinod Vaikuntanathan's course (linked above).
Date  Topic  Notes from Class  Additional Resources  

Boaz Barak's math background notes, A Note on Negligible Functions  
01/27 
Overview, Hardness, SIS and Oneway Functions 
Lecture Notes  1  Scribe notes from a previous offering: Lecture 1, Lecture 2  
01/29 
More on SIS, Collision Resistance 
Lecture Notes  2  These notes. For a proof of the Leftover Hash Lemma, see these notes  I and  II.  
02/03 
LWE, Pseudorandomness 
Scribe notes from a previous offering: Lecture 3, Lecture 4, Lecture 5, Lecture 9, Lecture 10. Introduction to LWE and PKE from LWE  I,  II and  III. See also this talk. 

02/05 
Pseudorandomness, PrivateKey Encryption 
Lecture Notes  4  These Lecture Notes  
02/10 
PrivateKey Encryption 
Lecture Notes  5  These Lecture Notes  
02/12 
PublicKey Encryption 
Lecture Notes  6  These Lecture Notes  
02/19 
Fully Homomorphic Encryption 
Lecture Notes  7 
Scribe notes from a previous offering: Lecture 11 GSW Homomorphic Encryption from Learning with Errors , Lecture Notes with some Simplifications 

02/24 
FHE  II 
Lecture Notes  8 
Scribe notes from a previous offering: Lecture 12 

02/26 
Lattice Trapdoors 
Lecture Notes  9  See these notes Ajtai Trapdoor Sampling , GPV signatures , MicciancioPeikert Trapdoor Sampling 

03/03 
Digital Signatures 
Lecture Notes  10  See these notes, and these for a more detailed proof MicciancioPeikert Trapdoor Sampling, GPV signatures Try this homework to improve your understanding of signature schemes and trapdoors 

03/05 
IdentityBased Encryption  I 
Lecture Notes  11  These notes  
03/10 
IdentityBased Encryption  II 
Lecture Notes  12  These notes  
03/12 
AttributeBased Encryption 
Lecture Notes  13  These notes  
03/17 
ZeroKnowledge  I 
Lecture Notes  14  Lecture notes from a previous offering: Lecture 8  
03/19 
ZeroKnowledge  II 
Lecture Notes  15  Lecture notes from a previous offering: Lecture 8 Additional reading: Lecture 7 of these notes For proofs of knowledge: this paper 

03/26 
Latticebased ZK 
Lecture Notes  16  Daniele Micciancio's list of resources  
03/31 
More ZK 
Lecture Notes  17  Nonblackbox simulation via FHE: This paper and this one  
04/02 
Computing on Encrypted Data  I 
Lecture Notes  18  
04/07 
Computing on Encrypted Data  II 
Lecture Notes  19  
04/09 
MultiKey FHE 
Lecture Notes  20  This paper  
04/14 
Lockable Obfuscation  I (Guest lecture by Rishab Goyal) 
This paper, and this concurrent paper  
04/16 
Lockable Obfuscation  II (Guest lecture by Rishab Goyal) 
Same as the links above  
04/21 
(No class) 

04/23 
Recap: Encryption 
Recap Notes  1  
04/28 
Recap: ZK 
Recap Notes  2  
04/30 
Recap: Lattice Trapdoors + Applications 
Recap Notes  3 