Welcome to the Fall 2019 web page for CS598DK: Special Topics in Cryptography!

Course Overview

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.

Course Schedule

The following is a tentative schedule and is subject to change.

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 Cleve's Impossibility of Fair Coin Toss , Section 3 of this paper
12/11 Fun topics. Project reports due, template here.