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.

Towards the end we will also explore other advanced cryptographic primitives, such as zero-knowledge proofs, 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

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

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 14 March 26
Homework 5 April 1 April 11
Homework 6 April 16 April 25

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 Maliciously Secure MPC Lecture 14 Chapter by David Evans, Vladimir Kolesnikov and Mike Rosulek: Section 2.3
Mar 13 Zero-Knowledge Proofs - I Lecture 15 Slides by Mike Rosulek: ZKP for Sudoku and Waldo
Mar 25 Zero-Knowledge Proofs - II Lecture 16
Mar 27 Coin Tossing Lecture 17 Parallel Coin Tossing: [Lin03]
Apr 1 GMW Compiler Lecture 18 Lecture Notes by Ran Canetti: notes
Apr 3 Function Secret Sharing Lecture 19 Survey by Elette Boyle, Niv Gilboa and Yuval Ishai: survey
Apr 8 Pseudorandom Correlation Generator Lecture 20 Compressing Vector OLE: [BCGI18]
Apr 10 Private Set Intersection Lecture 21 (Blackboard) Lecture Notes by Claudio Orlandi, Peter Scholl: notes
Apr 15 MPC from Homomorphic Encryption Lecture 22 MPC from Threshold Homomorphic Encryption: [CDN01]
Apr 17 Private Information Retrieval Lecture 23
Apr 22 Homomorphic Secret Sharing Lecture 24 HSS from DDH: [BGI16]
Apr 24 Obfuscation Lecture 25
Apr 29 Fully Homomorphic Encryption
(Guest lecture by Keewoo Lee)		 Lecture 26 GSW SHE (Notes by Keewoo Lee): notes
May 1 Review Class - II

References

Useful Books

Useful Lecture Notes