CS 444/596 - Cryptography

Fall 2017

Course Overview

This course is an undergraduate/graduate 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 primarily 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

Course Structure and Grading

Evaluation (grading) will be based on homeworks, a midterm exam, and a final exam. Students registered for 596 will additionally be expected to complete a final research project. Sections for 444 and 596 will be evaluated separately, as follows:

Exams

There will be an in-class midterm, tentatively set to October 17, in class. The final exam will be scheduled by the university. The final exam will be comprehensive.

Homeworks

Homework assignments will be posted on Sakai roughly every 1.5 weeks. Students should turn in neatly written or typeset solutions on time in class. Late homeworks will not be accepted.
Each homework will include an extra "challenge" problem that is required for 596 students. Challenge problems will be extra credit for 444 students.

Homework collaboration policy: Students are allowed to collaborate in teams of up to three, 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 a team, indicated the name of your collaborator(s) on the homework you turn in.

Failure to comply with the collaboration policy will be considered an academic integrity violation and reported to University administrators via their online system.

Projects (596 students)

Project information will be announced soon.

Lecture Schedule

A brief summary of each lecture and the associated reading will be posted here.
date lecture topics readings assignments
9/5 (Tues) 1: Introduction
  • what is cryptography? why study it?
  • symmetric encryption syntax
  • classical symmetric encryption
  • principles of modern cryptography
 K&L §1 none
9/7 (Thurs) 2: Provable Security
  • security definitions
  • perfect secrecy
  • alternative definition of perfect secrecy (with equivalence proof)
 K&L §2.1 none
9/12 (Tues) 3: The One-Time Pad
  • experiment-based definitions
  • one-time pad encryption
  • proof that one-time pad is perfectly secret
  • lower bound on keyspace size for perfectly secret encryption
 K&L §2.2, 2.3 HW1 out
9/14 (Thurs) 4: Computational Security
  • definitions of polynomial time and neglible functions
  • computational definition of security against an eavesdropper
  • pseudo-one-time pad construction
  • proofs by reduction
  • pseudorandom generator definition
 K&L §3.1, 3.2 (skip 3.2.2), 3.3 (skip stream ciphers) none
9/19 (Tues) 5: Pseudorandom generators and encryption
  • Proofs by reduction
  • Security proof for the pseudo-one-time-pad
 K&L §3.3.2, 3.3.3 none
9/21 (Thurs) 6: Stronger Security for Encryption and PRFs
  • Definition of security for multiple messages
  • Definition of CPA security
  • CPA security requires randomized encryption
  • Definition of pseudorandom functions (PRFs).
K&L §3.4, 3.5.1 through Example 3.26 HW1 in
9/26 (Tues) 7: CPA-Secure Encryption from PRFs
  • Construction of CPA-secure encryption PRFs
  • Proof by reduction
 K&L §3.5.2 HW2 out
9/28 (Thurs) 8: Encryption for Long Messages; Padding Oracle Attacks
  • Pseudorandom Permutations
  • Modes of Operation: ECB, CBC, CTR
  • PKCS#5 padding and padding oracle attacks against AES-CBC
 K&L §3.5.1 (on PRPs), 3.6.2, 3.7.2 none
10/3 (Tues) 9: Chosen-Ciphertext Attacks; Message Authentication Codes (MACs)
  • Definition of chosen-ciphertext security for encryption
  • Example: CPA-secure construction is not CCA-secure
  • MAC syntax
  • MAC security (unforgeability)
 K&L §3.7.1, 4.1, 4.2 up to "Verification Queries" none
10/5 (Thurs) 10: MACs Constructions
  • A fixed-length MAC from any PRF
  • MACs for long messages (including attacks)
  • MAC security (unforgeability)
 K&L §4.3 HW2 in; HW 3 out
10/10 (Tues) 11: CBC-MAC and Authenticated Encryption
  • CBC-MAC and typical implementation flaws
  • Combining encryption and authentication
  • Issues with Encrypt-and-Mac, Mac-then-Encrypt, Encrypt-then-Mac
 K&L §4.4, 4.5 none
10/12 (Thurs) 12: Cryptographic Hash Functions
  • Definition of collision resistance
  • Birthday attack on hash functions
  • Pollard Rho attack on hash functions
  • Begin Merkle-Damgard construction
 K&L §5.1, 5.4 through 5.4.2. Begin 5.2. none
10/17 (Tues) 13: Hash Functions and MACs
  • Proof for Merkle-Damgard construction
  • Hash-then-MAC
  • MACs from hash funcitons and length extension attacks
 K&L §5.2, 5.3 through 5.3.1. Length extension attacks are mentioned briefly at the start of 5.3.2, and exercise 5.10. none
10/19 (Thurs) 14: Intro to Number Theory
  • Divisiblity and primes
  • GCDs, and expressing GCD as Xa + Yb
  • Modular arithemtic
  • Invertible elements modulo N
 K&L §8.1.1-8.1.3 none
10/24 (Tues) 15: Midterm Exam none
10/26 (Thurs) 16: Intro to Groups
  • Definition of a group and examples
  • Basic results, like cancelation
  • gm=e in any group of order m
  • When fe is a permutation and fd is its inverse.
K&L §8.1.1-8.1.2 none
10/31 (Tues) 17: The Group Z*N and Factoring
  • Definition of Z*N
  • Order of Z*N (phi function)
  • The factoring problem and naive algorithms for it
 K&L §8.1.4, begin 8.2 HW 4 out
11/2 (Thurs) 18: RSA Problem and Public-Key Encryption
  • Computing xe mod N via repeated squaring
  • Definition of the RSA problem
  • Definition of public-key encryption
  • Textbook RSA and why it is insecure
  • CPA security for public-key encryption
  • Randomizing RSA with PKCS#1 v1.5
 K&L §8.2.4, 11.2 through 11.2.1, 11.5 through 11.5.2 none
11/7 (Tues) 19: CCA Public-Key Encryption, Hybrid Encryption, Begin Signatures
  • Definition of CCS security
  • Hybrid encryption and its motivation
  • Definition of digital signatures and their security
 K&L §11.2.3, 11.3, 12.1, 12.2 HW4 in
11/9 (Thurs) 20: RSA Signatures
  • RSA Signature algorithm
  • Attacks on textbook RSA signatures
  • More secure versions with padding
 K&L §12.4.1, see also 12.4.2 for RSA-FDH, but we did not do the proof HW5 out
11/14 (Tues) 21: Cyclic Groups and Quadratic Residues Mod p=2q+1
  • Basic definitions and results about finite cyclic groups
  • The discrete log problem
  • Baby-step-giant-step algorithm
 K&L §8.3.1 -- 8.3.3 none
11/16 (Thurs) 22: ElGamal Encryption
  • Definition of ElGamal
  • Decision Diffie-Hellman assumption (DDH)
  • ElGamal is CPA, assuming DDH
  • DDH is not true in Z*N
 K&L § 11.4.1 HW5 in; HW6 out
11/21 (Tues) 23: The Random Oracle Model
  • Motivation and issues with Random Oracle Model (ROM)
  • Definition of ROM
  • Examples: PRGs and CR hash functions in the ROM
  • Analysis of RSA-FDH in the ROM
 K&L § 5.5, 12.4.2 none
11/28 (Tues) 24: Identity-Based Encryption
  • Motivation for IBE
  • Syntax and CPA security definition for IBE
  • Bilinear pairings and BDDH
  • Boneh-Franklin IBE construction
 Paper , Sections 1,2,3, and 4 up to 4.2 none
11/30 (Thurs) 25: Paillier Encryption
  • Motivation for homomorphic encryption
  • ElGamal is homomorphic
  • More group theory basics: Isomorphisms
  • The group Z*N2 is isomorphic to ZNx Z*N
 K&L § 13.2 none
12/5 (Tues) 26: Paillier Encryption / LWE
  • Finish proof that Z*N2 is isomorphic to ZNx Z*N
  • Paillier encryption and its additive homomorphic property
  • Learning With Errors Problem: Linear algebra background and motivation
 K&L § 13.2; LWE Survey; LWE Lecture Notes HW7 out
12/7 (Thurs) 27: Learning With Errors
  • The Learning With Errors Problem
  • Private-key encryption from LWE
  • Variants of LWE: Oracle LWE, Decision Oracle LWE, SD
  • Public-key encryption from LWE
 LWE Survey; LWE Lecture Notes none
12/12 (Tues) 28: Homomorphic Encryption from LWE
  • Definition of Homomorphic Encryption
  • Simplifying assumptions: Evaluating NAND is enough
  • "Approximate Eigenvalue" LWE encryption where ciphertexts are matrices
  • Bit-decomposition method for controlling noise
 Paper HW7 in