Instructor | Andrew Miller soc1024@illinois.edu | |
---|---|---|
TA | Sanket Kanjalkar | |
Location | ECEB 2013 | |
Lecture Times |
Tuesday and Thursday, 11:00am- 12:20pm |
|
Office | Andrew: CSL 461 | Sanket: ECEB 3015 |
Office Hours |
Andrew: Thursday 12:30-1:30pm | Sanket: Wednesday 1:00pm-2:00pm |
Piazza | [piazza link] |
Cryptographic protocols are fundamental techniques for building secure systems, even against powerful attackers. Traditionally, cryptography is concerned with communication channels that lets Alice and Bob send messages, (e.g., “Let’s meet by the bridge at 5pm!”) while preventing an eavesdropper Eve from observing the message or tampering with the contents. Cryptography is already widely deployed, for example the TLS protocol is used every time you visit your bank’s website and see a green “padlock” symbol in your browser. Cryptography can also be used for much more than just secure channels. An emerging trend is the use of “computation over encrypted data.” For example, how can we perform a query over encrypted database?
The goal of this course is to introduce the concepts of modern cryptography, including a combination of both theoretical foundations (how do we precisely state security guarantees and assumptions, and prove that a protocol is designed correctly?) and practical techniques. At the end of this course, you will know how to apply cryptographic techniques in the design and analysis of secure distributed systems. This course is intended for senior undergraduate students with an interest in applying cryptographic techniques to building secure systems, and for graduate students with an interest in cryptography or systems security.
Main themes of the course include: Provable security. This course will introduce the modern theory of cryptography, where we provide rigorous proofs that a protocol is secure in spite of interference from arbitrary malicious adversaries (assuming precisely-stated models of network primitives and computationally-hard problems). Protocols for secure computing. Traditionally, the goal of cryptography is to build a secure communication channel between Alice and Bob. However, recently, the toolbox of practical cryptographic protocols has become much more versatile and powerful. This course will focus on the application and analysis of protocols for diverse applications, such as secure outsourcing of storage and computing over encrypted data. Failures and limitations of cryptography. Many (if not the vast majority of) deployed cryptosystems have been plagued with vulnerabilities, stemming from ad hoc protocol design, incorrect implementations, and overly-simplistic security models. This course will cover many examples of high-profile attacks.
Prerequisites:
Week 1: Introduction | ||
---|---|---|
Tuesday, Aug 27 | Course introduction, syllabus |
(slides) |
Thursday, Aug 29 | Cryptography for laypeople, journalists, and cypherpunks |
(slides) Reading (for next time): Pages 13-22 (Section 1.1 and Section 1.2) of Pass and Shelat. |
Week 2: | ||
Tuesday, Sep 3 | Group Theory |
Lecture notes: (pdf) Groups programming handout (gitlab) Notes: Appendix C.1 of Goldwasser and Bellare Equivalence Relations [from CS 173] (Section 6.5,6.6) |
Thursday, Sep 5 | Interactive Proofs |
Reading: Pass & Shelat, 3.1. Computational Indistinguishability, 4.3 Zero-Knowledge Interactions, 4.4 Interactive Protocols, 4.6 Zero-Knowledge Proofs |
Week 3: | ||
Sep 10 | More Interactive Proofs |
Preview of MP1 (add drop deadline) Optional complementary notes: [Notes from Susan Hohenberger] [Notes from Ivan Damgard] |
Sep 12 | More interactive proofs |
MP1 Release (gitlab) Lecture notes (pdf) |
Week 4: | ||
Sep 17 | Composing interactive Proofs | Lecture Notes (pdf) |
Sep 19 | Non-interactive proofs & Wrap-up ZK Proofs |
Lecture Notes (last year) (pdf) Notes on Forking Lemma from Bellare [pdf] "How Not To Prove Yourself" [eprint] |
Week 5: | ||
Sep 24 | One Way Functions |
Crypto egg public keys must be posted in Piazza by 11:59pm Lecture Notes (pdf) Notes: Pass & Shelat, 2.2 One-Way Functions, 3.4 Hard-Core Bits from Any OWF |
Sep 26 | Symmetric Encryption |
Lecture notes (pdf) Notes: Sections 3.5, 3.6, 3.7, 3.9 from Pass and Shelat, also Section 1.3 Notes: Section 6.2 in Pass and Shelat The strange story of "Extended Random"(blog) |
Week 6: | ||
Oct 1 | Garbled Circuits | **MP1 due** Lecture notes (slides) MP2 released (gitlab) |
Oct 3 | Diffie Hellman problems and Oblivious Transfer | The Simplest OT[eprint] Lecture notes (pdf) |
Week 7: | ||
Oct 8 | Improving Garbled Circuits, and Authentication |
Notes from Sanjam Garg on cut-and-choose for garbled circuits (pdf)
Michael Rosulek on history of performance improvements to Garbled Circuits (video,slides) Lecture notes (pdf) Blog post on Mac-then-Encrypt vs Encrypt-than-Mac (html) |
Oct 10 | Public Key Encryption | Pass and Shelat, 2.9 RSA Collection, 3.10 Public Key Encryption, 3.11 El-Gamal Public Key Encryption scheme More notes on Chinese Remainder Theorem (notes) |
Week 8: | ||
Oct 15 | Faults and Side Channels |
MP2 due Release Midterm |
Oct 17 | Project Ideas day |
Lecture Notes (slides) |
Week 9: | ||
Oct 22 | Polynomial Interpolation and secret sharing, Multi-party computation, Beaver Triples. Chosen ciphertext attacks |
Lecture Notes (pdf) Shamirs Secret Sharing Scheme (SSSS) [website] Blog post about IND-CCA (blog) Midterm due MP3 released |
Oct 24 | More MPC | |
Week 10: | ||
Oct 29 | Yet More MPC |
Project Proposals due (4-credit students only) Midterm Revisions due |
Oct 31 | Lattice Cryptography and Cryptanalysis | Lecture Notes (slides) Collision-Free Hashing from Lattice Problems (Goldrech et al) (pdf) |
Week 11: | ||
Nov 5 | Lattice Cryptanalysis | MP3 due MP4 tentatively released Using LLL-Reduction for Solving RSA and Factorization Problems: A Survey Lattice Attacks on RSA (from Nadia Heninger) (slides) |
Nov 7 | Passwords |
Reading: - Rainbow tables (pdf) - Let's talk about PAKE (password-based authenticated key exchange) (Matt Green's blog) |
Week 12: | ||
Nov 12 | Broadcast Protocols and BFT (Guest Lecture by Ling Ren) | Slides (pptx) |
Nov 14 | Question and Answer with Sanket | |
Week 13: | ||
Nov 18 | Authenticated Data Structures, hash-based signatures, refereed delegation | **MP4 due** Proposal checkpoint update due (4-credit students only) Lecture notes (slides) Lecture notes: (written notes) |
Nov 20 | Bilinear Groups, Threshold Signatures | Lecture notes: (written notes) |
FALL BREAK NOV 23–DEC 1 | ||
Week 14: | ||
Dec 3 | Ethics and Professionalism in Cryptography | Final exam (takehome portion) tentatively released |
Dec 5 | Succinct Zero-Knowledge Proofs (zkSNARKs) & Quantum/Post-quantum Cryptography | |
Week 15: | ||
Dec 10 | Informal project feedback | Final exam (takehom portion) tentatively due |
Dec 12 | Reading day, no class | |
Dec 13 (Friday) |
Exam Period: 8:00-11:00 a.m., Friday, Dec. 13 |
In-class final exam (1 hr) Final Project presentations (2 hrs) Final exam revisions due |
A proposal for each final project must be submitted to and accepted by the instructor by the proposal deadline.