ECE/CS 498AM: Applied Cryptography, Fall 2017

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 2pm-3pm or by appointment
Vincent: Tuesdays 2pm-3pm 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):

The information in this syllabus is subject to change.

Texts, books, resources

Textbooks are optional. Required readings will be accessible online. Here are some useful links:

Calendar

All due dates are 11:59pm central time.
Week 1: Introduction
Tuesday, Aug 29 Course introduction, syllabus
 [Slides]
Thursday, Aug 31 Cryptography for laypeople [Slides]
Reading (for next time): Pages 13-22 (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 Zero-Knowledge Interactions, 4.4 Interactive Protocols, 4.6 Zero-Knowledge 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 Non-interactive 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 One-Way Functions, 3.4 Hard-Core 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 El-Gamal 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 Multi-party 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 take-home final
[lecture notes]
Nov 30 Succinct Zero-Knowledge 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:00-11:00 a.m., Tuesday, December 19 [registrar guidelines]

Machine Problems (44% of grade)

There will be four machine problems throughout the course. Three of the machine problems will involve implementation of protocols discussed in class (constructive machine problems). One of the machine problems will involve breaking a weak cryptography routine (destructive machine problem). We will provide scaffolding/library utilities in the Python programming language (especially for algebraic operations and parsing/format routines, etc.).

Participation Challenges (6% of grade)

Occasionally throughout the course you'll need to respond to some challenge related to the MPs (i.e., generate a key pair and post your public key in Piazza). Points for these tasks will be folded in to the MP.

Midterm and Final Exam (25% of grade)

The midterm and final exam (**take home**) will each consist of written problem sets that focus on conceptual understanding of protocols discussed in class, writing proofs, and deriving/analyzing protocol variations. You will have a chance to revise the *proofs* in the take home exame based on feedback.

Final Project (only for 4 credit option) (25% of grade)*

The final project will be proposed by the student, and will consist of an implementation component and a (expected 3-page) written report. Suggested project ideas include: - Continue the implementation of any of the machine problem assignments. Add additional functionality, improved optimizations, or a more complete and usable integration.

A proposal for each final project must be submitted to and accepted by the instructor by the proposal deadline.

Grading

For the 3 credit version, the final project is not included.

Academic Integrity

https://www.ece.illinois.edu/academics/grad/overview/general-info.asp "The faculty of the Department of Electrical and Computer Engineering expects all students to maintain academic integrity at all times in the classroom and the research laboratory and to conduct their academic work in accordance with the highest ethical standards of the engineering profession. Students are expected to maintain academic integrity by refraining from academic dishonesty, and by refraining from conduct which aids others in academic dishonesty or which leads to suspicion of academic dishonesty. Violations of academic integrity will result in disciplinary actions ranging from failing grades on assignments and courses to probation, suspension or dismissal from the University."
The above information is subject to change. Refresh frequently!