Lecture Schedule
Note: You are responsible only for the material covered in class.
Items marked "reading" are expected to reinforce the material covered in
class, but I will often cover topics in class that are not in the reading.
Sometimes the reading will contain topics that I did not cover in class; in these cases, you are not responsible for the additional material.
This reading material will in general be
Jonathan
Katz's lecture notes from Fall 2002, abbreviated here as "JK", or the
textbook by Stinson. Please also see some additional
suggested readings.
- [Lecture 1, Sept. 2]
Introduction to the course. Motivation. Notation for encryption schemes, and definition of correctness.
Discussion of a "classical" cryptographic scheme: the shift cipher.
Modular arithmetic, groups, rings, and fields.
Reading: Stinson 1.1.1, 1.2.1.
- [Lecture 2, Sept. 4]
Breaking the shift cipher. The substitution cipher and cryptanalysis.
The Vigenere cipher.
Reading: Stinson 1.1.4, 2.1 - 2.3
- [Lecture 3, Sept. 9]
Motivation for provable security. The one-time pad and proof of
security. Full proof of security for the one-time pad.
Proof that the one-time pad is optimal.
More insidious methods of attack and how to "break" the one-time pad.
Where do we go from here?
New definitions of perfect security.
Reading: JK, Lecture 3.
- [Lecture 4, Sept. 11]
Definition of known-ciphertext and chosen-ciphertext attacks.
How to relax the definition of perfect security to get a feasible definition.
The notion of probabilistic polynomial-time (PPT) algorithms: brief look
at uses of randomization (random walks, fingerprinting).
Reading: JK, Lecture 4.
- [Lecture 5, Sept. 16]
Negligible functions. New definition of security using PPT algorithms
and negligible functions. One-way functions and weak one-way functions;
factoring.
Reading: JK, Lecture 4.
- [Lecture 6, Sept. 18]
Canceled due to Hurricane Isabel.
- [Lecture 7, Sept. 23]
Recap of where we are headed for now (one-way functions ->
pseudorandom generators -> feasible encryption). A closer look
at Z_N^*, examples, the Euclidean algorithm, and finding inverses
in Z_N^*. Some basic properties of cyclic groups. The Chinese
Remainder Theorem and some applications to efficient computation.
Reading: JK, Lectures 5 and 7; Stinson 5.2.
- [Lecture 8, Sept. 25]
Quadratic residues: basic properties for Z_p^* when
p is prime, and for Z_N^*, where N is the product of two distinct
odd primes. Introduction to the "squaring" one way function.
Reading: JK, Lecture 7. Also, we saw in class that in
Z_p^* where p is prime, we
can efficiently decide if a given element a is a quadratic residue
or not. If it is, how to efficiently find the square-roots?
See Vasek
Chvatal's page on the Adleman-Manders-Miller algorithm.
- [Lecture 9, Sept. 30]
Squaring not one-way implies factoring is easy; asymptotic vs.
concrete security. The RSA permutation, and connection to factoring.
Reading: JK, Lectures 8 and 9.
- [Lecture 10, Oct. 2]
The discrete-log function. Pseudorandom generators (PRGs);
PRG + one-time pad yields secure encryption.
Reading: JK, Lectures 9 and 10.
- [Lecture 11, Oct. 5]
Examples of non-one way functions and
non-(PRGs); next-bit unpredictability;
hardcore bits; one-way permutation + hard-core bit yields PRG;
statement of Goldreich-Levin theorem; hard-core bit for RSA permutation.
Reading: JK, Lecture 12.
- [Lecture 12, Oct. 9]
Increasing the stretch of a PRG; finishing up PRGs. Coping with
stronger attacks such as chosen plaintext attacks. The weakness of
deterministic encryption schemes, and an example randomized
encryption scheme. Definition of security using a left-or-right
encryption oracle.
Reading: JK, Lectures 11, 13, and 14.
- [Lecture 13, Oct. 14]
Security of the example randomized encryption scheme seen in the
last class; pseudorandom functions (PRFs); statement of the
theorem that PRFs exist iff one-way functions exist; using PRFs to
construct an encryption scheme secure in the sense of
left-or-right indistinguishability.
Reading: JK, Lectures 14, 15 and 16.
- [Lecture 14, Oct. 16]
A brief look at DES; encrypting arbitrary-length messages;
modes of encryption; ECB, CBC, and CFB modes; recap of
private-key encryption concepts studied so far; introduction to
message authentication.
Reading: JK, Lectures 17 and 18.
- [Lecture 15, Oct. 21]
Intuition behind oracle model for MAC; definition of
(t, epsilon)-security; the value of (pseudo-)random functions
in this context; a secure MAC for fixed-length messages.
Reading: JK, Lectures 18 and 19.
- [Lecture 16, Oct. 23]
MAC for variable-length messages; examples of insecure MAC schemes; description of XOR-MAC;
midterm review (OWF, OWP, PRG, PRF in detail, Q&A).
Reading: JK, Lectures 19 and 22.
- [Lecture 17, Oct. 28]
Midterm exam.
- [Lecture 18, Oct. 30]
Introduction to public-key cryptography and comparison with
private-key cryptography; the impossibility of perfect security;
(t,epsilon)-security and its impossibility under deterministic
encryption.
Reading: JK, Lectures 27 and 28.
- [Lecture 19, Nov. 4]
Brief review of a problem 4 from mid-term; review of
quadratic residuosity, Legendre and Jacobi symbols, and their structure
in Z_N^*; a public-key cryptosystem based on the hardness of
quadratic residuosity; proof of security started (to be completed
in next class).
Reading: JK, Lectures 28 and 29.
- [Lecture 20, Nov. 6]
Completing the proof of security from last class;
repeating squaring; the Prime Number Theorem; primality testing --
a first try, and the Miller-Rabin test.
Reading: JK, Lectures 25, 26, and 29.
- [Lecture 21, Nov. 11]
Main theorem about the Miller-Rabin test; recap of
previously-seen public-key cryptosystem; review of
cyclic groups and discrete log; the Diffie-Hellman problems.
Reading: JK, Lectures 26 and 30.
- [Lecture 22, Nov. 13]
DDH easier than CDH; El-Gamal encryption and its connection to
hardness of DDH; breaking DDH in Z_p^*, and El-Gamal encryption in
practice; Lagrange's theorem; begin security of public-key cryptosystems
in the sense of indistinguishability.
Reading: JK, Lectures 30 and 31.
- [Lecture 23, Nov. 18]
Finish indistinguishable encryption; begin hybrid encryption.
Reading: JK, Lectures 32 and 33.
- [Lecture 24, Nov. 20]
Finish hybrid encryption; begin trapdoor permutations.
Reading: JK, Lectures 33 and 34.
- [Lecture 25, Nov. 25]
Finish trapdoor permutations; begin signature schemes.
Reading: JK, Lectures 34 and 35.
- [Lecture 26, Dec. 2]
Definition of security for signature schemes; comparison with
MAC; Lamport's one-time signature scheme.
Reading: JK, Lectures 35 and 36.
- [Lecture 27, Dec. 4]
Proof of security of Lamport's one-time signature scheme;
collision-resistant hash functions and their applications to
signature schemes; introduction to the Random Oracle model.
Reading: JK, Lectures 37, 38, and 39.
- [Lecture 28, Dec. 9]
Review of the course.
Web Accessibility