CS 442 - Introduction to Cryptography

Fall 2012

Course Overview

This course is an undergraduate introduction to modern cryptography. We'll dig below the surface of cryptographic primitives and learn how to rigorously evaluate their security. We'll look at symmetric and public-key encryption, message authentication, digital signatures, hash functions, and more advanced topics as time allows. This course will be mathematical in nature, and while the needed background material on probability and number theory will be covered in class, students must be comfortable with working to understand new mathematics.

This course will not teach you everything about how to make your computer secure. We will be looking at cryptography at a theoretical level with a choice of topics that looks toward its practical usage. Interested students should also consider taking CS 419, which gives an introduction to general computer security.

General Information

Instructor: David Cash (david.cash@rutgers.edu, office Hill 411)
Course website: http://www.cse.ucsd.edu/~cdcash/442-fall-12
Required textbook: Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell.
Class meetings: Monday and Thursday 8:40am -- 10:00am in Hill 411
Instructor office hours: Monday 10:00am -- 11:00am in Hill 411 and by appointment

Grading

Final grades in the course will be an average of homework grades (20%), the midterm exam (35%) and comprehensive final exam (45%).

Homeworks

Homework assignments will be posted here roughly every 2 weeks. Students should turn in neatly written or typeset solutions on time. Late homeworks will not be accepted. Students are allowed to collaborate in teams of two, but only in the capacity of discussing the problems. Solutions must be written up individually, without collaboration, in your own words to show your understanding. On each assignment, if you choose to collaborate with someone, indicated the name of your collaborator on the homework you turn in.

Homework 1: Assigned 9/17, Due 9/27 Note: some typos corrected in this version.
Homework 2: Assigned 10/4, Due 10/15
Homework 3: Assigned 10/22, Due 10/29
Homework 4: Assigned 11/26, Due 12/6

Lecture Schedule

A brief summary of each lecture and the associated reading will be posted here.

Thu Sept 6 (Lecture 1): Introduction

Overview of cryptography. Basics of private-key encryption. Classical ciphers and how to break (cryptanalyze) them.
Reading: Sections 1.1, 1.2, 1.3.

Mon Sept 10 (Lecture 2): Provable security overview. Probability review.

Security definitions, hardness assumptions, and security proofs. Uniform distribution, conditional probability, independence.
Reading: Section 1.4. See also appendix A.3.

Thu Sept 13 (Lecture 3): Perfect secrecy and the one-time pad.

Definition of perfect secrecy and an equivalent definition. (Ours are different from the book.) The one-time pad scheme and proof that it is perfectly secret. Limitations of perfect secrecy.
Reading: Sections 2.1-2.3 (note the differences between this definition and ours), 2.5.

Mon Sept 17 (Lecture 4): Computational Security.

Making the one-time pad practical. Polynomial time and negligible funcitons. Computational security of private-key encryption. Pseudorandom generators.
Reading: Sections 3.1.1, 3.1.2, 3.2 (through 3.2.1), 3.3, 3.4 up to Theorem 3.16

Thu Sept 20 (Lecture 5): Computational Security (cont.).

Indistinguishability and semantic security. Generic attack against Pseudorandom generators.
Reading: Sections 3.2.2 and 3.3

Mon Sept 24 (Lecture 6): Encryption and Security Proofs.

Security reductions. Proof that the generalized one-time pad is secure. Security for multiple encryptions. The necessity of randomized or stateful encryption. Some real-world PRGs.
Reading: Sections 3.1.3, 3.4.1, 3.4.2 up to "Secure Multiple Encryptions Using a Stream Cipher".

Thu Sept 27 (Lecture 7): Pseudorandom Functions and Chosen Plaintext Attack Security.

Definitions of pseudorandom functions and security against chosen plaintext attacks, and basic facts about the definitions.
Reading: Sections 3.5 and 3.6.1.

Mon Oct 1: Class canceled.

Thu Oct 4 (Lecture 8): Constructing CPA-Secure Encryption Schemes
- Review definitions. A CPA-secure encryption scheme from any PRF and its security proof.
- Reading: Section 3.6.2.
Mon Oct 8 (Lecture 9): CPA-Secure Encryption Schemes For Long Messages
- Pseudorandom permutations. Modes of operation and their tradeoffs. Begin CCA security.
- Reading: Sections 3.6.3, 3.6.4, begin 3.7.
Thu Oct 11 (Lecture 10): CCA Security and Message Authentication Codes
- CCA Security, CCA attacks and ciphertext malleability. Begin authentication and MACs.
- Reading: Sections 3.7, 4.1, 4.2, 4.3.
Mon Oct 15: Class canceled.

Thu Oct 18 (Lecture 11): Message Authentications Codes
- A MAC for short messages from a PRF. Begin MAC constructions for longer messages. Extra: the CRIME attack on compress-then-encrypt.
- Reading: Sections 4.3, 4.4 through page 121. See also the question and first answer here for a discussion about the principles behind the CRIME attack.
Mon Oct 22 (Lecture 12): MACs for Long Messages
- MAC constructions for longer messages: CBC-MAC. Security for variable-length messages.
- Reading: Sections 4.4, 4.5.
Thu Oct 25 (Lecture 13): Combining Encryption and MACs
- Encrypt-then-Mac, its security, and why variants are insecure.
- Reading: Sections 4.8, 4.9 to page 150. See also this paper about attacks on bad padding implementations.
Mon Oct 29: Class canceled due to Sandy.
Thu Nov 1: Class canceled due to Sandy.
Mon Nov 5: Midterm review.
Thu Nov 8 Midterm.
Mon Nov 12 (Lecture 14): Practical PRP Constructions
- Practical security goals for blockciphers. Subsitution-permutation networks. Attacks on 1 and 2 rounds.
- Reading: Section 5.1.
Thu Nov 15 (Lecture 15): Feistel Networks and DES
- Feistel networks, outline of DES. Theoretical result on Feistel networks. Double/triple encryption and meet in the middle attacks.
- Reading: Sections 5.2-5.4. See also Section 6.6 for the Luby-Rackoff result on 3 and 4 round Feistel.
Mon Nov 19 (Lecture 16): Number Theory I
- Primes, divisbility, modular operations.
- Reading: Sections 7.1.1, 7.1.2, B.1.1, B.2.1, and B.2.3 up to page 507.
Tue Nov 20 (Lecture 17): Number Theory II
- Modular exponentiations and inverses. Groups and the group Z^*_N.
- Reading: Sections 7.1.3, 7.1.4.
Mon Nov 26 (Lecture 18): Assumptions in Number Theory
- Primality testing and generating primes. Factoring and the RSA problem.
- Reading: Section 7.2 except 7.2.2.
Thu Nov 29 (Lecture 19): Public-Key Encryption, Textbook RSA
- The need for public-key encryption (PKE). Security notions for PKE, how they relate to private-key notions and to each other. Textbook RSA encryption and its insecurity.
- Reading: Sections 9.1-9.3, 10.1, 10.2 through page 341, 10.4 to page 357.
Mon Dec 3 (Lecture 20): Secure PKE Schemes
- Padded RSA and a standardized variant. Chosen-ciphertext security and why it is important. The CCA-insecurity of textbook RSA.
- Reading: 10.4.3, 10.6 except for the "El Gamal" note at the end.
Thu Dec 6 (Lecture 21): Digital Signatures
- Digital signature schemes and their security. Textbook RSA and why it is not secure. Hashed RSA.
- Reading: Sections 12.1-12.3.