Instructor  Andrew Miller soc1024@illinois.edu  

TA  Kevin Liao  
Location  ECEB 2013  
Lecture Times 
Tuesday and Thursday, 2:00pm 3:20pm 

Office  Andrew: CSL 461  Kevin: CSL 368 
Office Hours 
Andrew: Thursday 3:304:30pm  Kevin: Monday 10:3011:30 
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 preciselystated models of network primitives and computationallyhard 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 overlysimplistic security models. This course will cover many examples of highprofile attacks.
Prerequisites: Either of the following (or consent of instructor):
Week 1: Introduction  

Tuesday, Aug 27  Course introduction, syllabus 
Lecture Notes (slides) 
Thursday, Aug 29  Cryptography for laypeople, journalists, and cypherpunks 
Lecture Notes (slides) Reading (for next time): Pages 1322 (Section 1.1 and Section 1.2) of Pass and Shelat. 
Week 2:  
Tuesday, Sep 4  Group Theory 
TA scribe notes (gitlab) Notes: Appendix C.1 of Goldwasser and Bellare Equivalence Relations [from CS 173] (Section 6.5,6.6) Programming examples with elliptic curve groups (secp256k1.py) 
Thursday, Sep 6  Interactive Proofs 
Lecture notes from last year (pdf) TA scribe notes (gitlab) Reading: Pass & Shelat, 3.1. Computational Indistinguishability, 4.3 ZeroKnowledge Interactions, 4.4 Interactive Protocols, 4.6 ZeroKnowledge Proofs Preview of MP1 
Week 3:  
Sep 11  More Interactive Proofs 
Lecture notes from last year (pdf) TA scribe notes continued from last time (gitlab) Optional complementary notes: [Notes from Susan Hohenberger] [Notes from Ivan Damgard] 
Sep 13  Composing interactive Proofs 
Lecture notes from last year (pdf) MP1 Released! (mp1) 
Week 4:  
Sep 18  Noninteractive proofs 
Lecture notes from last year (pdf) Notes on Forking Lemma from Bellare [pdf] "How Not To Prove Yourself" [eprint] 
Sep 20  One Way Functions 
Lecture notes from last year (pdf) Crypto egg public keys must be posted in Piazza by 11:59pm Notes: Pass & Shelat, 2.2 OneWay Functions, 3.4 HardCore Bits from Any OWF 
Week 5:  
Sep 25  Symmetric Encryption 
Lecture notes from last year (pdf) Notes: Sections 3.5, 3.6, 3.7, 3.9 from Pass and Shelat, also Section 1.3 
Sep 27  Garbled Circuits 
Lecture notes from last year (pdf) Notes: Section 6.2 in Pass and Shelat ***MP1 due*** Release MP2: Garbled Circuits 
Week 6:  
Oct 2  Diffie Hellman problems  Diffie Hellman key agreement 
Oct 4  Oblivious Transfer  The Simplest OT[eprint] 
Week 7:  
Oct 9  Improving Garbled Circuits 
Notes from Sanjam Garg on cutandchoose for garbled circuits (pdf) Michael Rosulek on history of performance improvements to Garbled Circuits (video,slides) 
Oct 11  Public Key Encryption  Pass and Shelat, 2.9 RSA Collection, 3.10 Public Key Encryption, 3.11 ElGamal Public Key Encryption scheme More notes on Chinese Remainder Theorem (notes) **MP2 Due** Release Midterm 
Week 8:  
Oct 16  Faults and Side channels  Project Ideas day Lecture notes (slides) 
Oct 18  Polynomial Interpolation and secret sharing  ***Midterm due*** Release MP3: Multiparty computation Shamirs Secret Sharing Scheme (SSS) [website] MPC Lecture Notes (pdf) Programming With Polynomials (gitlab) 
Week 9:  
Oct 23  Multiparty computation, Beaver Triples 
MPC Lecture Notes (pdf) 
Oct 25  More MPC, begin Oblivious RAM 
MPC Lecture Notes (pdf) ***Midterm revision due*** ***Project Proposals due*** 
Week 10:  
Oct 30  SPECIAL: Cryptocurrencies and Privacy  Lecture notes (slides) 
Nov 1  Lattice Cryptography and Cryptanalysis  ***MP3 Due*** 
Week 11:  
Nov 6  Lattice Cryptanalysis  MP4 Released Using LLLReduction for Solving RSA and Factorization Problems: A Survey 
Nov 8  Broadcast Protocols and BFT  (slides) 
Week 12:  
Nov 13  Passwords I (Kirill Levchenko)  NOTE ROOM CHANGE: ECEB 3002 (suggested reading) 
Nov 15  Passwords II (Joshua Reynolds)  **MP4 due** NOTE ROOM CHANGE: ECEB 3002 Reading:  Rainbow tables (pdf)  Let's talk about PAKE (passwordbased authenticated key exchange) (Matt Green's blog) 
FALL BREAK NOV 17–25  
Week 13:  
Nov 27  Bilinear Groups, Threshold Signatures  Release takehome final 
Nov 29  Succinct ZeroKnowledge Proofs (zkSNARKs)  
Week 14:  
Dec 4  Postquantum Cryptography  
Dec 6  Searchable Encryption  ***Final exam due*** 
Week 15:  
Dec 11  Informal project feedback  
Dec 13  Reading Day, no class  ***Final exam revision due*** 
Finals Week: Dec 14+  
Friday, Dec. 14 
Exam Period: 8:0011:00 a.m. Final Project presentations 
A proposal for each final project must be submitted to and accepted by the instructor by the proposal deadline.