CS 65500 - Advanced Cryptography (Spring 2025)
Course Overview
Cryptography enables secure communication and computation in the presence of adversaries. In this course, we will address a fundamental question related to secure and reliable collaboration: How can a group of mutually distrusting parties jointly compute a function over their private data without compromising the confidentiality of that data? To answer this, we will first identify the security properties that are desirable for the scenario at hand. We will then formally define the key primitive that we wish to derive: secure multiparty computation (and its variants). Finally, we will discuss various constructions and rigorously prove that they meet the defined security requirements. Along the way, we will also explore other advanced cryptographic primitives, such as zero-knowledge proofs, fully homomorphic encryption, homomorphic secret sharing, pseudorandom correlation generators, etc. These tools are used in the design of state-of-the-art secure multiparty computation protocols. By the end of this course, you will be equipped to understand cryptography research papers and initiate research in this area.
Basic Information
-
Instructor: Aarushi Goel
Class Time: 3:00 PM - 4:15 PM, Tuesday and Thursday
Class Location: LWSN B134
Office Hours: 11 AM - 12 PM, Tuesday (LWSN 2142D)
Ed Discussion: On Brightspace
Pre-Requisites
CS 35500/55500 (or an equivalent course). We will also assume exposure to basic probability, computational complexity and maturity with mathematical proofs
Grading Policy
10% Class Participation
20% Midterm (in-class on March 6)
25% Final Exam (take-home)
45% Homeworks (best 5 out of 6)
All homeworks must be submitted via Gradescope (on Brightspace).
Late Submission: Homework submitted upto 24 hours late will incur a penalty of 50%. Homework submitted more than 24 hours late will receive no credit.
Collaboration: You are encouraged to collaborate with your classmates on homework problems, however, your final write-up must be your own. Be sure to explicitly acknowledge everyone with whom you collaborated. You may also refer to books or online resources to aid in solving homework problems. However, you must properly credit all such sources in your submission, and under no circumstances should you copy material verbatim.
Academic Dishonesty: In general, any instance of academic dishonesty will result in a significant penalty to your overall course grade and will be referred to the Office of the Dean of Students for further action.
Homework Schedule
| Homework | Release (6:00 PM) | Due (11:59 PM) |
|---|---|---|
| Homework 1 | January 21 | January 30 |
| Homework 2 | February 4 | February 16 |
| Homework 3 | February 18 | February 27 |
| Homework 4 | March 13 | March 26 |
| Homework 5 | April 1 | April 10 |
| Homework 6 | April 15 | April 24 |
Class Schedule
| Date | Topics | Slides | Other References |
|---|---|---|---|
| Jan 14 | Introduction | Lecture 0 | |
| Jan 16 | Basics of Indistinguishability | Lecture 1 | Notes by Leo Reyzin: 1, 2, 3 Notes by Boaz Barak: 1, 2 |
| Jan 21 | Basics of Provable Security | Lecture 2 | Notes by Noah Stephens-Davidowitz: notes Chapter by Mike Rosulek: Chapter 2 |
| Jan 23 | Semi-Honest 2PC and Oblivious Transfer I | Lecture 3 | Chapter by David Evans, Vladimir Kolesnikov and Mike Rosulek: Chapter 2 |
| Jan 28 | Oblivious Transfer II | Lecture 4 | |
| Jan 30 | Semi-Honest GMW I | Lecture 5 | Goldreich-Micali-Wigderson: [GMW87] Chapter by David Evans, Vladimir Kolesnikov and Mike Rosulek: Section 3.2 |
| Feb 4 | Semi-Honest GMW II | Lecture 6 | |
| Feb 6 | Semi-Honest GMW II (Continued) | Lecture 7 (Blackboard) | |
| Feb 11 | Garbled Circuits - I | Lecture 8 | Chapter by David Evans, Vladimir Kolesnikov and Mike Rosulek: Section 3.1 |
| Feb 13 | Garbled Circuits - II | Lecture 9 (Blackboard) | Security Proof of Yao's Protocol: [LinPin04] Lecture Notes by Arpita Patra: notes |
| Feb 18 | Shamir Secret Sharing and Semi-Honest MPC | Lecture 10 | How to Share a Secret: [Shamir79] |
| Feb 20 | Semi-Honest BGW - I | Lecture 11 | Chapter by David Evans, Vladimir Kolesnikov and Mike Rosulek: Section 3.3 Lecture Notes by Yael Kalai: notes |
| Feb 25 | Semi-Honest BGW - II and Multiparty GMW | Lecture 12 | Full Proof of BGW Protocol: [AshLin11] |
| Feb 27 | Reducing Communication in Semi-Honest BGW | Lecture 13 | Packed Secret Sharing: [FraYun92] MPC using Beaver Triples: [Beaver92] |
| Mar 4 | Review Class - I | ||
| Mar 6 | Midterm | ||
| Mar 11 | |||
| Mar 13 | |||
| Mar 25 | |||
| Mar 27 | |||
| Apr 1 | |||
| Apr 3 | |||
| Apr 8 | |||
| Apr 10 | |||
| Apr 15 | |||
| Apr 17 | |||
| Apr 22 | |||
| Apr 24 | |||
| Apr 29 | |||
| May 1 | Review Class - II |
References
Useful Books
A Pragmatic Introduction to Secure Multi-Party Computation by David Evans, Vladimir Kolesnikov and Mike Rosulek
A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup
Introduction to Modern Cryptography, Second Edition by Jonathan Katz and Yehuda Lindell
Foundations of Cryptography: Volume 1, Basic Tools by Oded Goldreich
Foundations of Cryptography: Volume 2, Basic Applications by Oded Goldreich
The Joy of Cryptography by Mike Rosulek
Useful Lecture Notes
A Course in Cryptography by Rafael Pass and Abhi Shelat
Introduction to Cryptography by Jonathan Katz
Lecture Notes on Cryptography by Shafi Goldwasser and Mihir Bellare
Introduction to Modern Cryptography by Mihir Bellare and Phillip Rogaway