ECE/CS 498AC: Applied Cryptography, Fall 2018

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:30-4:30pm	Kevin: Monday 10:30-11: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 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: Either of the following (or consent of instructor):

- ECE 422 / CS 461 (Introduction to computer security) or equivalent
- ECE 428 / CS 425 (Distributed Systems) or equivalent

Additionally, the following course is helpful but not required:

- ECE 173 / CS 173 (Discrete structures) or equivalent

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:

A course in cryptography. (Pass and shelat) [pdf] [archive]
Lecture Notes in Cryptography (Goldwasser-Bellare) [pdf]
Slides from UIUC CS/ECE598MAN[website]
A Graduate Course in Applied Cryptography (Dan Boneh and Victor Shoup) [pdf]
Introduction to Modern Cryptography (Katz-Lindell)
Serious Cryptography: A Practical Introduction to Modern Encryption (Aumasson)
MPC and Secret-Sharing [website]
Handbook of Applied Cryptography [pdf]
Algorithmic Cryptanalysis (Stinson & Joux) [pdf]
Foundations of Cryptography (Goldreich)
Lecture Notes: Bellare-Rogaway (pdf slides), Waters

Calendar

All due dates are 11:59pm central time.

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 13-22 (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 Zero-Knowledge Interactions, 4.4 Interactive Protocols, 4.6 Zero-Knowledge 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	Non-interactive 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 One-Way Functions, 3.4 Hard-Core 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 cut-and-choose 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 El-Gamal 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	Multi-party 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 LLL-Reduction 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 (password-based authenticated key exchange) (Matt Green's blog)
FALL BREAK NOV 17–25
Week 13:
Nov 27	Bilinear Groups, Threshold Signatures	Release take-home final
Nov 29	Succinct Zero-Knowledge 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:00-11:00 a.m. Final Project presentations

Machine Problems (4 assignments, worth 12.5% each, 44% of grade in total)

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.).

Quizzes and Participation (6% of grade)

Occasionally throughout the course you'll need to respond to some challenge or quiz, usually related to the MPs (i.e., generate a key pair and post your public key in Piazza).

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

The following list is for the 4 credit version. For the 3 credit version, the final project is not included.

50%: Machine problems
- 12.5%: MP1: Zero-Knowledge Proofs
- 12.5%: MP2: Garbled Circuits
- 12.5%: MP3: Multiparty Computation
- 12.5%: MP4: Cryptanalysis
25%: Written homework / take-home exam
- 10%: Midterm
- 15%: Final
25%: Final project (4-credit only)
- 5%: Project Proposal (approved by instructor)
- 10%: Checkpoint (informal report, 5-minute presentation)
- 10%: Final project code, security analysis, and report

Late Policy

Assigned work is due at the dates and times listed above. We strongly recommend that you get started early. Late work will not be accepted after 48 hours past the deadline. Everyone will be given ONE late extension that allows you to turn in an assignment up to 24 hours after the due date without penalty. This extension may be used on either an MP or project. After your extension has been used, subsequent late submissions will be penalized by 10% of the maximum attainable score, plus an additional 10%, every 24 hours until received. Note that this policy and the extension CANNOT be combined; Late work will not be accepted after 48 hours past the due date. The instructors may grant individual extensions, but only under extraordinary circumstances.

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!