ECE407/CS407: Cryptography, Fall 2021

Instructor Andrew Miller soc1024@illinois.edu
TA Yunqi Li
Location ECEB 3013, also Zoom
Lecture Times
 Monday, Wednesday, Friday 4:00pm- 4:50pm
Lectures are also available online via Echo360.
Office Andrew: CSL 461
Yunqi: Zoom
Office Hours
 Andrew: Thursdays 2:30pm-3:30pm
Yunqi: Wednesday 2:30pm-3:30pm
Piazza https://piazza.com/illinois/fall2021/c93b
Discord: see piazza for 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:

The information in this syllabus is subject to change.

Texts, books, resources

Purchasing textbooks is optional. All the required readings for this course will be accessible online. We will mainly use these two sets of notes: Here are some additional sets of online notes we may draw from:

Calendar

All due dates are 11:59pm central time.

All lecture recordings are available via the media space channel [Mediaspace Channel for ECE/CS 407]
Week 1: Introduction
Monday, Aug 23 Course introduction, syllabus
 Lecture notes (slides)
Wednesday, Aug 25 Cryptography for laypeople, journalists, and cypherpunks Lecture notes (slides)
Friday, Aug 27 Warmup: One Time Pad Lecture notes [pdf]
Reading: Joy Chapter 1: (pdf)
Additional notes:
Chapter 1, Pass and Shelat
Week 2:
Monday, Aug 30 Basics of provable security, confidentiality definitions Scribbles (pdf)
Reading: Joy Chapter 2: (pdf)
Additional notes: Section 1.3 from Pass and Shelat
Wednesday, Sep 1 One way functions, pseudorandomness Scribbles (pdf)
Reading: Joy Chapter 4: (pdf)
Additional notes: Sections 3.5, 3.6, 3.7, 3.9 from Pass and Shelat
Friday, Sep 3 Psuedorandom generators and PRF Lecture Notes: (pdf)
Reading: Joy Chapter 5: (pdf)
Additional notes: Pass & Shelat, 2.2 One-Way Functions, 3.4 Hard-Core Bits from Any OWF
The strange story of "Extended Random"(blog)
Week 3: More symmetric key encryption
Monday, Sep 6 LABOR DAY NO CLASS
Wednesday, Sep 8 Pseudorandom functions and block ciphers Scribbles (pdf)
Reading: Joy Chapter 6 (pdf)
Friday, Sep 10 Garbled Circuits MP1 Release
Lecture notes (slides)
Reading: Pass & Shelat, 6.2 Yao Circuit Evaluation
Week 4: More encryption, Message Authentication
Monday, Sep 13 Chosen Plaintext Attacks Lecture Notes: (pdf)
Reading: Joy Chapter 7 (pdf)
Wednesday, Sep 15 Block Cipher Modes Lecture notes: (pdf)
Reading: Joy Chapter 8 (pdf)
Friday, Sep 17 Chosen Ciphertext attacks Lecture notes: (pdf)
Reading: Joy Chapter 9 (pdf)
Week 5: Interactive Proofs
Monday, Sep 20 Message Authentication Codes Lecture notes: (pdf)
Joy Chapter 10 (pdf)
More notes: Pass and shelat, 5.1, 5.2.
Wednesday, Sep 22 Cyclic Groups Lecture notes: (pdf)
Joy Chapter 14 (pdf)
Friday, Sep 24 More Groups Lecture notes: (pdf)
Zoom recording: (zoom)
Week 6:
Monday, Sep 27 Interactive Zero Knowledge proofs Lecture Notes (pdf)
MP1 due, MP2 (partial) Release
Pass and shelat, 4.3-4.6 (zero-knowledge, interactive protocols, proofs, and zero-knowledge proofs)
Wednesday, Sep 29 More Zero knowledge MP2 (full) Release
Lecture Notes (pdf)
Illustrated Primer on ZK (blog)
Friday, Oct 1 Zero knowledge composition Lecture Notes (pdf)
On Σ-protocols (pdf)
Week 7: More ZKP
Monday, Oct 4 More ZKP, Commitments Lecture Notes (pdf)
Susan Hohenberger's notes (1)
Wednesday, Oct 6 Non-interactive ZK and signatures Susan Hohenberger's notes (2)
Friday, Oct 8 Still more ZKP, Diffie Hellman Key Exchange Lecture notes (pdf)
Week 8:
Monday, Oct 11 Project Day
Wednesday, Oct 13 Review for Midterm
MP2 Due
Friday, Oct 15 MIDTERM synchronous portion
Week 9:
Monday, Oct 18 Polynomials, Secret sharing, MPC Lecture notes (pdf) Midterm take home portion release
Reading: Joy, Chapter 3
Wednesday, Oct 20 More MPC
Friday, Oct 22 Yet more MPC Project proposals due
Week 10:
Monday, Oct 25 Collision resistance Midterm takehome portion due.
Reading: Joy Chapter 11
More notes on MPC (pdf)
MP3 release.
Wednesday, Oct 27 Still more MPC More MPC (pdf)
Friday, Oct 29 Collision resistance, Public Key Encryption Reading: Joy Chapter 15
Lecture notes (pdf)
Week 11:
Monday, Nov 1 E-Voting Lecture notes (pdf)
Wednesday, Nov 3 RSA crypto system Reading: Joy Chapter 13
Lecture notes (pdf)
Friday, Nov 5 Fault attacks on RSA Reading: Boneh Demilo Lipton (pdf)
Stanford Number Theory notes: (web)
Lecture notes (pdf)
Week 12:
Monday, Nov 8 Side channels MP3 due.
Lecture slides: (slides)
Wednesday, Nov 10 Authenticated Data Structures Lecture Notes (slides)
Friday, Nov 12 Authenticated Encryption, Forward Security Project Checkpoints Due
Lectures notes (pdf)
Week 13: More protocols
Monday, Nov 15 Private Information Retrieval MP4 release
Lecture notes: (pdf)
Wednesday, Nov 17 Oblivious RAM Slides from Mark Ryan (pdf)
Friday, Nov 19 CLASS CANCELED happy thanksgiving
Fall Break: November 20-28
Week 14: Lattices, Garbled Circuits Security
Monday, Nov 29 Lattices and Ajtai hash More notes:
Lecture notes: (pdf)
Wednesday, Dec 1 Pairings and Polynomial commitments
Friday, Dec 3 Cut and Choose & Garbled Circuits Security
Week 15:
Monday, Dec 6 Some Ethics and Cryptography MP4 due.
Moral Character of Cryptographic Work (pdf)
Wednesday, Dec 8 Project Presentations Final Exam takehome portion released (1 hour)
Due prior to Final Exam period.
Final Exams
Tuesday Dec. 14 Final exam 7:00pm-10:00pm. in ECEB 3013

Assignments / Machine Problems (4 assignments, worth 11% each, 44% of grade in total)

There will be four machine problems / problem sets throughout the course. The problem sets are meant to exercise your problem solving and proof writing skills, and practice for the exams. The machine problem components will involve some combination of: implementation of protocols discussed in class (constructive machine problems), or 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 (6% of grade)

Each student will need to scribe one lecture for the participation grade. This means you will need to write up in LaTeX a nicely formatted notes document summarizing the technical content of one of the lectures. We will occasionally have participation challenges conducted online, such as posting your public key. This class is meant to foster discussion. We will award bonus points for insightful questions and discussions posted on piazza.

Midterm and Final Exam (25% of grade)

The midterm and final exam (**in class, until further notice**) 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.

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!