CS 489/698: Foundations of Modern Cryptography (Fall 2025)


Course Overview:

This course offers a rigorous introduction to the foundational principles and tools of modern cryptography. The emphasis is on the theoretical underpinnings of the field, particularly the use of complexity-theoretic assumptions to prove the security of cryptographic primitives and protocols through formal reductions. Students will gain a solid understanding of core cryptographic concepts—such as encryption, authentication, and secure computation—and learn how to design and analyze cryptographic schemes in a provably secure manner.

For example, imagine you know the prime factorization of a large number N = p × q. In this course, you will learn how cryptography enables protocols that can convincingly prove to someone that N is the product of two primes — without ever revealing what those primes are. Intrigued? This course is for you!


Syllabus: 

-- Symmetric-Key Cryptography: one-way functions, pseudorandom generators/functions and private-key encryption.

-- Hardness Amplification: strong one-way functions/hardcore bits from weak one-way functions/hardcore bits.

-- Commitment Schemes

-- Cryptographic Assumptions: number-theoretic (discrete log, factoring, pairings) and post-quantum secure assumptions (lattices and learning with errors)

-- Signature Schemes

-- Public-Key Encryption

-- Interactive Proof Systems

-- Zero-Knowledge Proofs: how to prove a statement without leaking any information.

-- Introduction to Secure Multi-Party (MPC) Computation.


Relations to CO 487/687

Our course "Foundations of Modern Cryptography"  gives a complexity-based treatment: how to use hardness assumptions (e.g., hardness of factoring) in order to build secure cryptosystems and protocols. A main focus of our course is on reductions: rigorously showing how to reduce purported attacks against a constructed scheme into an attack against the hardness assumption. We will also cover topics (e.g., zero knowledge proofs) that aren't covered in any other courses. In contrast, CO 487/687 focuses on mathematical tools behind cryptography. For example, while we assume the existence of cryptographic groups (e.g., ones satisfying the discrete-log assumption) and use them abstractly and generically in constructions, CO 487/687 studies how such groups are instantiated in practice, and explores the number-theoretic and algebraic reasons behind their assumed security.


Relations to CS 459/698: Privacy, Crypto, Network, Data Security (PCND)

The PCND course is mostly about networks security and the basic tools of of cryptography, as far as needed for networks security. The main difference is that PCND is not about the foundations of cryptographic primitives: it doesn't provide proofs of security and doesn't teach the cryptographic principles that allow one to build complicated cryptographic protocols from simpler primitives. Also, a unique feature of the Foundations of Modern Cryptography course is that it covers fundamental concepts such as zero-knowledge proofs and secure computation.


 Grading Policy

(1) Homework: There will be four assignments, each worth 15% of your final grade, totaling 60% for undergraduate students. For graduate students, this component will account for 40%, each counting 10%, of the final grade. All assignments must be typeset in LaTeX using a template that will be provided later.

(2) Take-Home Exams (2 exams, ~2–3 days each):

(3) Graduate-Student Only Component


Required Background

Any one of CS 245, CS 341, CS 360 or CS 365 or their equivalents. In general, a solid understanding of algorithms and basic computational concepts, such as polynomial-time computation and probabilistic algorithms.


Resources: 

https://www.wisdom.weizmann.ac.il/~oded/foc-book.html





Course Information:

Time: TBA
Location: TBA
Instructor: Mohammad Hajiabadi
Office hours: TBA