Instructor  Andrew Miller soc1024@illinois.edu  

TA  Vincent Bindschaedler  
Location  ECEB 3017  
Lecture Times 
Tuesday and Thursday, 12:30pm  1:50pm 

Office  Andrew: CSL 461  Vincent: SC 4309 
Office Hours 
Andrew: Thursdays 2pm3pm or by appointment  Vincent: Tuesdays 2pm3pm or by appointment 
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 an 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 (how do we compose primitives to build complex systems?). At the end of this course, you will know how to apply cryptographic techniques in the design and analysis of secure distributed systems.
Prerequisites: Either of the following (or consent of instructor):
Week 1: Introduction  

Tuesday, Aug 29  Course introduction, syllabus 
[Slides] 
Thursday, Aug 31  Cryptography for laypeople  [Slides] Reading (for next time): Pages 1322 (Section 1.1 and Section 1.2) of Pass and Shelat. 
Week 2:  
Tuesday, Sep 5  Group Theory 
[Lecture Notes] Groups Programming handout [secp256k1.py] Notes: Appendix C.1 of Goldwasser and Bellare Equivalence Relations [from CS 173] (Section 6.5,6.6) 
Thursday, Sep 7  Interactive Proofs 
[Lecture Notes] Notes: Pass & Shelat, 3.1. Computational Indistinguishability, 4.3 ZeroKnowledge Interactions, 4.4 Interactive Protocols, 4.6 ZeroKnowledge Proofs Preview of MP1 [preview] 
Week 3:  
Sep 12  More Interactive Proofs  [Lecture Notes] [Notes from Susan Hohenberger] [Notes from Ivan Damgard] 
Sep 14  Composing interactive Proofs  [Lecture Notes] Release MP1: Zero Knowledge Proofs [gitlab] 
Week 4:  
Sep 19  Noninteractive proofs  [Lecture Notes] Notes on Forking Lemma from Bellare [pdf] "How Not To Prove Yourself" [eprint] 
Sep 21  One Way Functions  [Lecture Notes] Notes: Pass & Shelat, 2.2 OneWay Functions, 3.4 HardCore Bits from Any OWF **Crypto egg public key MUST be posted in Piazza** 
Week 5:  
Sep 26  Symmetric Encryption  [Lecture Notes] Code sample (part of MP2): [util.py] Notes: Sections 3.5, 3.6, 3.7, 3.9 from Pass and Shelat, also Section 1.3 
Sep 28  Garbled Circuits 
[Lecture Notes] [Slides] Notes: Section 6.2 in Pass and Shelat ***MP1 due*** Release MP2: Garbled Circuits [gitlab] 
Week 6:  
Oct 3  Oblivious Transfer  [Slides] The Simplest OT[eprint] 
Oct 5  Oblivious RAM  (Lecture by Vincent Bindschaedler) [slides] 
Week 7:  
Oct 10  Improving Garbled Circuits  [lecture notes] [Video and Slides from Mike Rosulek] 
Oct 12  Public Key Encryption  [lecture notes] Pass and Shelat, 2.9 RSA Collection, 3.10 Public Key Encryption, 3.11 ElGamal Public Key Encryption scheme **MP2 Due** Release Midterm 
Week 8:  
Oct 17  Searchable Encryption  [Slides] 
Oct 19  Attacks on Searchable Encryption  ***Midterm due*** [Slides] Release MP3: Searchable Encryption [gitlab] 
Week 9:  
Oct 24  Faults and Side channels  [Slides] 
Oct 26  Broadcast Protocols and BFT  [Slides] ***Midterm revision due*** ***Project Proposals due*** 
Week 10:  
Oct 31  Polynomial Interpolation and Threshold Cryptography  Shamirs Secret Sharing Scheme (SSS) [website] [Lecture Notes] Programming With Polynomials [gitlab] 
Nov 2  Lattice Cryptography and Cryptanalysis  ***MP3 Due*** Release MP4: Lattice attacks on RSA 
Week 11:  
Nov 7  [class canceled]  For makeup: Attend Nadia Heninger's talk on "How not to generate random numbers"[announcement] 
Nov 9  Multiparty computation  Lecture notes on BGW protocol from Daniele Micciancio [lecture notes] 
Week 12:  
Nov 14  Arithmetic Circuits  [lecture notes] We looked at several R1CS compilers, including (not exhaustively) libsnark, ZoKrates 
Nov 16  Anonymous Credentials, ECash  **MP4 due** [lecture notes] Authenticated Data Structures[slides] 
FALL BREAK NOV 18–26  
Week 13:  
Nov 28  Bilinear Groups  Release takehome final [lecture notes] 
Nov 30  Succinct ZeroKnowledge Proofs (zkSNARKs)  [lecture notes] 
Week 14:  
Dec 5  Hot Topic  
Dec 7  Hot Topic  ***Final exam due*** Andrew's office hours canceled 
Week 15:  
Dec 12  Informal project feedback  Vincent 
Dec 14  Reading Day, no class  ***Final exam revision due*** 
Finals Week: Dec 15+  
Dec 19 
Final project presentations in 3017 ECEB 8:0011:00 a.m., Tuesday, December 19 [registrar guidelines] 
A proposal for each final project must be submitted to and accepted by the instructor by the proposal deadline.