Welcome to the Fall 2022 web page for CS/ECE407: Cryptography

Course Overview.

Cryptography is a powerful toolbox for building secure systems --- not just for private communication, but also for building fault tolerant protocols, for securely outsourcing computation to untrusted services, and more. The goal of this course is to introduce the concepts of modern cryptography, including a combination of theoretical foundations (how do we precisely state security guarantees and assumptions, and rigorously prove theorems about a purported protocol being secure?) and practical techniques (how do we combine secure primitives to make effective systems?). 
This offering of the course is designed to be a challenging theory course. While CS 225 is a strict prerequisite, a good background and comfort in classes such as CS/ECE374 is important. Please email the instructor within the first week if you want to take this course, but have not previously taken CS/ECE 374 and are not enrolled in CS/ECE 374 this semester. Students will also be assumed to be fluent in discrete mathematics and probability. A large component will be problem sets, which are meant to develop problem solving skills. 
No prior cryptography background is assumed, however, students are expected to have mathematical maturity. Prior to taking this course, should be comfortable with writing mathematical proofs and with algorithmic reductions.

Instructor: Dakshita Khurana, dakshita@illinois.edu. Office hours: Wednesday 5 pm - 6 pm in ECE 2013 and Friday 2 pm - 3 pm in SC 4308. Alternatively, please email me to set up an appointment.
TAs: James Hulett, jhulett2@illinois.edu, Amit Agarwal, amita2@illinois.edu. James' office hours: Mondays, 11 am - 12 pm, in Siebel 4124.

Course Credits: 3/4
Time: MWF, 4.00 - 4.50 pm.
Location: ECE Building, room 2013.
Piazza: Please sign up for Piazz
a at piazza.com/illinois/fall2022/c93b, access code 407 to access class discussions and homework.

Note: Students are encouraged to drop by during office hours (or set up, by email, an appointment to meet) within the first 2 weeks. This will help me learn more about your interests and what you hope to learn from this class. I can also help you with a choice of topic for your project.

Students will be asked to scribe lecture notes. These notes will serve as a key resource for this course. We will closely follow the book:

Additional Resources: Books/Lecture Notes.

Grading.

10%: Participation. 
This course is an in-person class. The material will be taught in class and no lecture recordings will be made available. It may be possible to make exceptions for specific students if they reach out in advance about extenuating circumstances. Students should plan on attending lectures in person to understand the material. The class intends to encourage deep, careful thought. I want the lectures be as interactive as possible: you are strongly encouraged to ask questions and offer answers. I will end 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 the prescribed scribe notes and book before the next lecture is recommended to better understand the contents of the course. Finding bugs in scribe notes (and proposing fixes) will earn you participation points. In addition, students that ask insightful questions and offer insightful answers in class, or as part of assignment solutions, or on Piazza will be rewarded with extra credit.

10%: Scribe Notes.
Scribe notes are a complete, polished write-up of a lecture, with references and technical details carefully filled in. These will serve as the primary technical material for this course. Every student should expect to scribe once, typically solo, sometimes 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. Please make a new editable copy of the file on overleaf and make changes there. You have one week to prepare the scribe notes. More precisely, the scribe notes for a Monday lecture are due at 11.59 pm the following Monday, the scribe notes for a Wednesday lecture are due at 11.59 pm the following Wednesday, and notes for a Friday lecture are due at 11.59 pm the following Friday. To submit, please turn on link sharing on overleaf (see instructions) and post the link on piazza in a private piazza post (visible to instructors and TAs), 

50%: Homeworks.
There will be 6 homework assignments, each worth 10%. You will be graded according to the total of your top 5 submissions. Topics will range from cryptanalytic attacks, to implementations of secure cryptographic primitives, and a majority will pertain to writing and understanding mathematically rigorous proofs of security. Homework assignments will be released every alternate Friday, and will be due in 10 days, i.e. on Monday at 1 pm.

30%: Exam (Take-home). 
There will one final take-home exam, with 4-5 questions, that you will have 24 hours to solve. To be successful in the exam, I highly recommend that you attend class, participate and ask questions, and give careful and deep thought to topics discussed in class. 

(ONLY FOR 4 CREDITS) 25% (out of 125%): Project.
The purpose of the project is to expose students to research in cryptography. 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 an 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 (recommended) in teams of 2-3, and spend at 2-3 weeks on the project. Please find the project template here.

Course Schedule.

This is a tentative schedule and is subject to change. Please keep checking this page for updates to topics and for scribe notes. Much of the content has been borrowed from the Boneh-Shoup textbook and Dan Boneh's course. Please refer to a previous offering of this course, including lecture notes and other material, here.

Date Topic Slides Reading (Boneh-Shoup) Scribe Notes from a previous offering (not vetted)
08/22 Course Overview, Historical Perspective Slides 1 Chapter 1 --
08/24 Perfect Secrecy, One-time Pad Slides 2 Chapter 2 Scribe notes 2
08/26 Pseudorandom Generators, Stream Ciphers Slides 3 Chapter 3 Scribe notes 2
08/29 Block Ciphers I Slides 4 Chapter 4 Scribe notes 3
08/31 Block Ciphers II Slides 5 Chapter 5 Scribe notes 4
09/02 Review 
Homework 1 Released
-- -- --
09/05 No Class (Labor Day) -- -- --
09/07 Message Authentication - 1 Slides 6 Chapter 6 Scribe notes 5
09/09 Message Authentication - 2 Slides 7 Chapter 6 Scribe notes 5
09/12 Collision Resistance Slides 8 Chapter 8 Scribe notes 6
09/14 Authenticated Symmetric Encryption Slides 9 Chapter 9 Scribe notes 7
09/16 Review
Homework 2 Released
-- -- --
09/19 Authenticated Encryption wrapup, Number Theory - 1 Slides 10 Chapter 10 Scribe notes 8Scribe notes 9
09/21 Key Exchange Slides 11 Chapter 10 Scribe notes 9Scribe notes 10
09/23 Public Key Encryption Slides 12 Chapter 10 Scribe notes 10
09/26 CCA Secure Encryption - 1 Slides 13 Chapter 11 Scribe notes 11
09/28 CCA Secure Encryption - 2 Slides 14 Chapter 11 Scribe notes 11
09/30 Review
Homework 3 Released
-- -- --
10/03 Digital Signatures Slides 15 Chapter 13 Scribe notes 12
10/05 Full-Domain Hash Slides 16 Chapter 14  
10/07 Schnorr Signatures and Identification Slides 17 Chapter 19 Scribe notes 13
10/10 Commitments Slides 18 Chapter 19 Scribe notes 13
10/12 Introduction to Zero-Knowledge Slides 19 Chapter 19 --
10/14 Review
Homework 4 Released
-- -- --
10/17 Zero-Knowledge Proofs - 1 Slides 20 Chapter 19 Scribe notes 15
10/19 Zero-Knowlegde Proofs - 2 Slides 21 Chapter 19 Scribe notes 16
10/21 OR Composition, NIZK Slides 22 Chapter 19 Scribe notes 17Scribe notes 18
10/24 No Class      
10/26 More NIZK Slides 23 Additional reading Scribe notes 19
10/28 Review
Homework 5 Released
-- -- --
10/31 Oblivious Transfer - 1 Slides 24 Additional reading Scribe notes 20
11/02 Oblivious Transfer - 2 Slides 25 Chapter 14 here Scribe notes 20
11/04 Computing on Secret-Shared Data Slides 26 Chapter 14 here Scribe notes 21
11/07 Computing on Shared Data, Garbled Circuits - 1 Slides 27 Chapter 14 here Scribe notes 22
11/09 Garbled Circuits - 2 (online instruction) Slides 28 Chapter 14 here Scribe notes 23
11/11 Review
Homework 6 Released
-- -- --
11/14 Ethics in Cryptography - 1 (TA instruction) Slides 29 -- --
11/16 Ethics in Cryptography - 2 (TA instruction) -- -- --
11/18 No Class -- -- --
11/21 Thanksgiving break -- -- --
11/23 Thanksgiving break -- -- --
11/25 Thanksgiving break -- -- --
11/28 Learning with Errors - 1 Slides 30 Introduction to LWE and PKE from LWE - I- II and - III. See also this talk. Scribe notes 24
11/30 Learning with Errors - 2 Slides 31 same as above Scribe notes 25
12/02 Learning with Errors - 3 Slides 32 same as above Scribe notes 25
12/05 Review for Final Exam -- -- --
12/07 No Class (spend time on your take-home exam!) -- -- --