Welcome to the Fall 2019 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 cutting-edge topics in modern cryptography. We will understand how an adversary that breaks advanced protocols can be transformed into an adversary that contradicts a basic assumption such as the hardness of factoring. 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.
This is a seminar course in Cryptography. Students will be expected to read and discuss research papers in the second part of the course. 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: Siebel Center for Comp Sci 1109
Instructor: Dakshita Khurana, dakshita@illinois.edu
Office Hours (updated): Monday 11am - 1 pm, Wednesdays and Fridays by appointment.
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 presentation and your project.
Students will be asked to scribe lecture notes, which will serve as the main resource for this course. Here is a list of additional resources.
Additional Resources: Books
Additional Resources: Lecture Notes
25%: Class Participation and Scribe Notes.
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.
Scribe notes are a complete, polished write-up of a lecture, with references and technical details carefully filled in. Every student should expect to scribe once, either solo or in teams of 2 depending on class size. At the beginning of every lecture, I will ask for volunteers to write the scribe notes for the day. Please do not volunteer if there is a chance that you will drop the course before you submit your scribe notes. Preparing these notes will help you internalize the material at a new level, by thinking through the significance of the material and converting every proof outline discussed in class to a rigorous proof. Please typeset your scribe notes in LaTeX using the template here. You have one week to prepare the scribe notes. More precisely, the scribe notes for a Wednesday lecture are due at 5 pm the following Wednesday, and the scribe notes for a Friday lecture are due at 5 pm the following Friday. Please email me your .pdf file and the source files (.tex and .bib, as well as figure files if any). Please email me your files as a single ZIP archive.
40%: Presentation.
Students will prepare class presentations based on one of the topics listed below. You will be expected to understand the paper in detail, organize your thoughts and provide a 1 hour, high quality, whiteboard presentation to the class, while supplying adequate background. You will be given bonus points for making the presentation interactive/enjoyable, and answering your peers’ questions. You should feel free to work individually or in teams of 2-3, and grades will be calibrated accordingly.
35%: Project.
The purpose of the project is to expose students to research in cryptography, ideally in the same area that the student is presenting. You can pick a project topic of your choice (you can refer to this list for some nice ideas). The project can be a literature survey, or an attempt at original research to answer some open problem in cryptography. Picking a project in an area related to the presentation is strongly encouraged, but not necessary. 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 2-3, 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. Send in scribe notes on time, with fully worked out proofs.
Pick a presentation topic early, and start preparing your presentation early. The presentation and project go hand-in-hand. You should plan to spend several weeks on the paper assigned to you. Spend the first week understanding the background and prior work, the second week understanding technical ideas in the paper assigned to you, the third thinking deeply about the premise of the paper and clarifying any questions, and two more weeks preparing an hour long presentation. This process should generate many questions and ideas that you should explore as part of your project. Research is an unpredictable game, so your project evaluation will primarily take into account the thought and effort you put in and your ideas.
Finally, please meet me on Wednesday/Friday, at least one week before your presentation is due. At this time, I will expect you to have carefully read and understood the paper assigned to you, and prepared your presentation. Please ask my any questions or clarifications about the paper before this meeting. This meeting is designed to be a practice run. You will not be evaluated at this time – I will only provide additional guidelines. The better prepared you are at this point, the more useful this session will be.
Date | Topic | Literature |
---|---|---|
Instructor Lectures | Fundamentals of Cryptography | |
08/28 | Introduction, overview, historical perspective Scribe lecture notes: Lecture 1 |
Boaz Barak’s math background notes |
08/30 | One-way functions, Hard Core Bit - 1 Scribe lecture notes: Lecture 2 |
Chapter 2 , A Note on Negligible Functions |
09/04 | Hard Core Bit - 2, Commitments Scribe lecture notes: Lecture 3 |
Chapter 2 |
09/06 | Pseudorandom Generators (PRGs), Pseudorandom Functions (PRFs) Scribe lecture notes: Lecture 4 (bonus! proof of security of GGM PRF) |
Chapters 3, 5 |
09/11 | Private-Key Encryption, Public-Key Encryption Scribe lecture notes: Lecture 5 |
Chapters 6, 7 |
09/13 | Oblivious Transfer, Secure Computation - I Scribe lecture notes: Lecture 6 |
Katz lecture notes, Part 14 of these notes |
09/18 | Secure Computation - II Scribe lecture notes: Lecture 7 |
Part 14 of these notes , Chapter 13 of this book |
09/20 | Zero Knowledge, Fiat-Shamir for NIZK Scribe lecture notes: Lecture 8 |
Lecture 7 of these notes , Additional reading: Random Oracles are Practical , The Random Oracle Methodology, Revisited |
09/25 | No Class | |
09/27 | No Class, Project Proposal Due | |
Instructor Lectures | Lattices and Post-Quantum Cryptography | |
10/02 | Learning with Errors Scribe lecture notes: Lecture 9 |
Introduction to LWE and PKE from LWE - I and - II See also this talk |
10/04 | Cryptography from LWE, continued. Scribe lecture notes: Lecture 10 |
Public Key Encryption from LWE |
10/09 | Fully Homomorphic Encryption I Scribe lecture notes: Lecture 11 |
GSW Homomorphic Encryption from Learning with Errors , Lecture Notes with some Simplifications |
10/11 | Fully Homomorphic Encryption II Scribe lecture notes: Lecture 12 |
GSW Homomorphic Encryption from Learning with Errors |
Student Presentations | Non-interactive ZK (NIZK) and CCA security | |
10/16 (Sanket) | Post-Quantum NIZK | NIZK and Correlation Intractability from Circular-Secure FHE |
10/18 (Yunqi) | Simulation-Sound NIZK | Simulation Sound NIZKs |
10/23 (Luke + Andrew) | Naor-Yung Cryptosystem | Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks |
10/25 (Jong Chan) | Fujisaki-Okamoto Transformation | Secure Integration of Asymmetric and Symmetric Encryption Schemes |
10/30 (Vipul) | Cramer-Shoup CCA Encryption | Simplified Notes from Boaz Barak |
Student Presentations | Beyond Zero-Knowledge | |
11/01 (Surya) | Distinguisher-Dependent Simulation | Distinguisher-Dependent Simulation and its Applications |
11/06 (Sarah) | Efficient Zero-Knowledge Proofs and Arguments | Efficient Zero-Knowledge Proofs and Arguments |
11/08 (Ruta) | Delegating Computation and No-Signaling Proofs | Delegating Computation via No-Signaling Strategies |
Student Presentations | Applied MPC | |
11/13 (Liza + Tanya + Sanjeev) | Oblivious Transfer Extension | Extending Oblivious Transfers Efficiently |
11/15 (Ye + Nerla + Shreyas) | SPDZ MPC | Multiparty Computation from Somewhat Homomorphic Encryption |
11/20 (Haris + Siheng) | Authenticated Garbling | Authenticated Garbling and Maliciously Secure 2PC |
Student Presentations | Beyond MPC | |
11/22 (No Class) | ||
12/04 (Rucha + Aniket) | Rational MPC | |
12/06 (Sourav + Amit + Tom) | Fairness | |
12/11 | Fun topics. Project reports due, template here. |