Lecture Schedule
Note: You are responsible for the material covered in class as well as the material covered in any assigned readings, unless I specifically say otherwise.
Note that the assigned readings are expected to reinforce (and sometimes supplement) the material covered in class, and many times I will cover things in class that are not in the reading.
Below, [BR] refers to the lecture notes by Bellare and Rogaway, and [Katz] refers to the lecture notes from the last time this course was taught.
Entires above the horizontal line reflect what was actually covered in class. Entries below the horizontal line reflect what I intend to cover in future classes. The syllabus is very tentative, and will change depending on the pace of lectures in class.
- [Aug 31: Lecture 1] Introduction and "Classical" Cryptography
Introduction to the course; motivation.
What does it mean for an encryption scheme to be secure? Do secure encryption schemes exist?
Introduction to probabilistic notation.
An information-theoretic notion of secrecy, and
the one-time pad encryption scheme.
Reading: [BR] - Introduction; [Katz] - Lectures 3 and 4.
- [Sept 2: Lecture 2] Complexity-Based Cryptography and Provable Security
Proof of security for the one-time pad.
Limitations of information-theoretic secrecy, and optimality of the one-time pad.
A computational notion of secure encryption.
Reading: (see previous lecture)
- [Sept 7: Lecture 3] Symmetric-Key Encryption and PRGs
Motivation for provable security. One-way functions. A one-way function based on hardness of factoring.
Pseudorandomness and pseudorandom generators (PRGs).
Reading: [Katz] - Lectures 4, 5, 10.
- [Sept 9: Lecture 4] Symmetric-Key Encryption
Secure encryption from any pseudorandom generator.
Reading: [Katz] - Lecture 10.
- [Sept 14: Lecture 5] Pseudorandom Functions
On constructing a pseudorandom generator from a one-way function.
Chosen-plaintext attacks and a revised definition of security.
The need for randomized encryption. Introduction to pseudorandom fuctions.
Reading: [BR] - Sections 2.1, 2.3, 2.4.1, 2.4.2, 2.4.4, 2.6, Chapter 3; [Katz] - Lecture 13, 14.
- [Sept 16: Class cancelled for Rosh Hashana]
- [Sept 21: Lecture 6] Pseudorandom Functions and Secure Encryption
On the existence of pseudorandom functions.
Block ciphers (DES, AES). Viewing block ciphers as pseudorandom functions.
Symmetric-key encryption using pseudorandom functions.
Reading: [BR] - Chapter 4;
[Katz] - Lectures 15, 16.
- [Sept 23: Lecture 7] Secure Encryption
Symmetric-key encryption using pseudorandom functions.
Secure encryption of long messages, modes of encryption. Pseudorandom permutations. CBC mode and its security.
Constructing pseudorandom permutations from pseudorandom functions.
Reading: [Katz] - Lectures 17, 18.
- [Sept 28: Lecture 8] Pseudorandom permutations. Message Authentication
Constructing pseudorandom permutations from pseudorandom functions.
Motivation for message authentication. Toward a definition of security.
Reading: [BR] - Chapter 6; Sections 5.2, 5.3, and 5.4; [Katz] - Lectures 18, 19, and 22-24.
- [Sept 30: Class cancelled for Sukkot]
- [Oct 5: Lecture 9] Message Authentication
Review for midterm.
Limitations of "perfect" security for message authentication codes.
A computational notion of security. A construction based on pseudorandom functions.
Reading: [BR] - Section 6.2.
- [Oct 7: First midterm]
- [Oct 12: Lecture 10] Message Authentication
Proof of security for the construction based on PRFs. A more practical example: CBC-MAC.
Reading: [BR] - Chapter 6
- [Oct 14: Lecture 11] Message Authentication
Some insecure MACs (examples). More secure MACs: XOR-MAC, Hash-and-MAC.
Collision-resistant hashing.
- [Oct 19: Lecture 12] Message Authentication. (Algorithmic) Number Theory
Proof of security for "hash-and-mac".
Introduction to the public-key setting, and motivation for number theory.
- [Oct 21: Lecture 13] (Algorithmic) Number Theory
Computing efficiently with large integers: addition/subtraction, multiplication/division, modular exponentiation, extended gcd computation. Z_n and Z*_n.
Introduction to groups.
Reading: [BR] - Chapter 7 ("Computational Number Theory"); some notes on algebra.
- [Oct 26: Lecture 14] Number Theory
Characterizing which elements of Z_n have multiplicative inverses. Z*_n,
phi(n), and computing phi(n) for n prime or a product of two primes.
Group exponentiation. The cancellation law in groups. Proof that a^m = 1 in a group G if |G| = m (Fermat's little theorem); extensions. Application to RSA.
Reading: [BR] - Chapter 7 ("Computational Number Theory"); some notes on algebra.
- [Oct 28: Lecture 15] Number Theory
Subgroups; characterizing allowable subgroup orders. Cyclic (sub)groups, generators, the discrete logarithm problem, and viewing exponentiation in a cyclic group as a one-way function. Facts about cyclic groups. Testing for generators; choosing a random generator. Quadratic residues.
Reading: [BR] - Chapter 7 ("Computational Number Theory"); some notes on algebra.
- [Nov 2: Lecture 16] Number Theory
Quadratic residues modulo a prime. Chinese remaindering and applications. Quadratic residues modulo a product of two primes and application to secure public-key encryption.
Reading: [BR] - Chapter 7 ("Computational Number Theory"); some notes on algebra.
- [Nov 4: Lecture 17] Number Theory and Exam Review
Review of homework; review for exam.
Testing primality. Generating random primes. Review of RSA.
Reading: [BR] - Chapter 7 ("Computational Number Theory") and Sections 7.3.1, 7.3.2 of "Number-Theoretic Primitives"; some notes on algebra.
- [Nov 9: Second midterm]
- [Nov 11: Lecture 18] Public-Key Encryption
Introduction to public-key encryption; some basic definitions of security. Impossibility of perfectly-secure public-key encryption; impossibility of deterministic public-key encryption secure against chosen-plaintext attacks.
An encryption scheme based on the hardness of deciding quadratic residuosity.
Reading: [BR] - Sections 8.1, 8.2; [Katz] - lectures 27-29.
- [Nov 16: Lecture 19] Public-Key Encryption
An encryption scheme based on the hardness of deciding quadratic residuosity. Implementing the scheme. The quadratic residuosity assumption.
Reading: [BR] - Section 8.1; [Katz] - lectures 27-29.
- [Nov 18: Lecture 20] Public-Key Encryption
The quadratic residuosity assumption. On the equivalence between security against chosen-plaintext attacks and ciphertext-only attacks in the public-key setting. The Diffie-Hellman assumption; Diffie-Hellman key exchange.
Reading: [BR] - Chapter 7 ("Number-Theoretic Primitives"): Sections 7.1, 7.2.2. Also Chapter 7 ("Computational Number Theory") Section 7.5 and
Sections 8.2.1, 8.3 (you do not need to know the proof given in Section 8.3 since we did not cover it in class); [Katz] - lectures 29, 30, 32 (again, you do not need to know the proof given in lecture 32 since we did not cover it in class)
- [Nov 23: Lecture 21] Public-Key Encryption
The El Gamal encryption scheme. Hybrid encryption. The RSA assumption. Can we construct secure encryption based on the RSA assumption?
Reading: [BR] - Sections 8.4, 8.5 [not 8.5.3] (you do not need to know the proofs); [Katz] - lectures 31-33.
- [Nov 30: Lecture 22] Private Information Retrieval (PIR) (guest lecture by Prof. Gasarch)
Multiple-database PIR schemes with information-theoretic security and sublinear communication.
Reading: detailed notes are available here. See also Prof. Gasarch's extensive PIR links
- [Dec 2: Lecture 23] Public-Key Encryption using RSA; Signature Schemes
Hard-core bits and provably-secure encryption using RSA. The random oracle model and efficient encryption using RSA. Introduction to digital signature schemes.
Reading: [Katz] - Lectures 35, 38, 39; [BR] - Sections 9.1, 9.2
- [Dec 7: Lecture 24] Signature Schemes
Definitions of security for signature schemes. Some insecure suggestions. The Lamport one-time signature scheme. Signing long messages using collision-resistant hashing. Extending Lamport's scheme to sign multiple messages.
Reading: [Katz] - Lectures 35-37; [BR] - Sections 9.2, 9.3.2
- [Dec 9: Lecture 25] Signature Schemes and Exam Review
Extending Lamport's scheme to sign an unbounded number of messages. Efficiency improvements. Signatures in the random oracle model.
Reading: [Katz] - Lectures 35-37, 39; [BR] - Sections 9.2, 9.3.2
- [Dec 17] Final Exam
Given from 1:30 - 3:30 in 1122 CSIC