Course Schedule
Weekday Regular Schedule
Group  Type  Hours  Location 

01  Lecture  Tue 1013  Orenstein 111 
02  Recitation  Wed 1718  Orenstein 111 
Course Plan
Week  Date  Crypto Subject  Mathematics Background  Recitation  Textbook Reference 

1  Oct 20  Popular introduction to Modern Crypto; Administrativia, course topics, etc. Lecture1 
The mod operation over integers; The ring $\mathbb{Z}_N$.  No recitation.  Stinson 1.1.1; Shoup 2.12.4, 3.13.4 
2  Oct 27,28  Pseudo random generators and permutations. Symmetric Stream Ciphers. Lecture2 
Groups and subgroups, rings, fields and finite fields. Lecture2b  Introduction to symbolic math using Sage. Sage code to be used in recitation SageCode1  Stinson 3.7; KatzLindell 3.3, 3.4, 3.6 
3  Nov 3, 4  Symmetric block ciphers: Modes of operation; DES and AES. Lecture3  More finite fields and extension fields. Euler's totient function $\phi$; Euclid GCD algorithm; extended GCD. Lecture3b  Finite field arithmetic and primitive elements, using Sage. SageCode2 Simple Sage code for fitting a polynomial to points in 2D plane SageCode3 
Stinson 3.1, 3.4, 3.5, 6.4; KatzLindell 5.3, 5.5, 7.1 
4  Nov 10, 11  Iterated Ciphers; Message Authentication; Cryptographic Hash Functions. Lecture4  More finite fields and extension fields. Finite field arithmetic and primitive elements Lecture3b  Finding primitive elements in finite fields. SageCode4  Stinson 4.2.1; KatzLindell 4.14.7, 5.4 
5  Nov 17, 18  Discrete logarithm problem in $\mathbb{Z}_p$; DiffieHellman's key exchange. Lecture 5 SageCode5  Quadratic residues in $\mathbb{Z}_m$.  A DiffieHellman variant: EKE; Discrete log modulo $p=2^n+1$ is easy. SageCode6  Stinson 5.2.1, 5.4; KatzLindell 7.3, 9.4, 11.1 
6  Nov 24, 25  Prime numbers and the prime number theorem. Probabilistic Primality (actually Compositeness) Testing. Carmichael numbers. Integer multiplication as a one way function. RSA public key encryption  preliminaries. Lecture 6  The Chinese remainder theorem (CRT)  Primes have short certificates. Factoring $p\cdot q$ given RSA encryption and decryption exponents.  Stinson 5.2, 5.4, 5.3, KatzLindell 7.2, 10.4 
7  Dec 1, 2  RSA public key encryption and some of its properties. Digital signatures. RSA signatures. Lecture 7  Self reducibility of RSA. Factoring numbers with Pollard $\rho$ algorithm. SageCode7  Pollard $\rho$ demonstration. Eratosthenes's sieve. Factoring numbers with the quadratic sieve (part 1 of 2).  Stinson 5.3, 5.5, 5.6 KatzLindell 7.2, 8.1 
8  Dec 8, 9  SSL and PKI: Guest lecture by Prof. Ran Canetti. Slides giving overview of TLS. tlsoverview  More integer factoring algorithms. Factoring numbers with the quadratic sieve (part 2 of 2).  
9  Dec 15, 16  ElGamal PKC and signature scheme, both based on discrete logs. Lecture 9  Hanukka special (conditions apply): Levitation without meditation.  Timememory tradeoffs. Shank's babystep giantstep algorithm for discrete log in $\mathbb{Z}_p$. Hellman's TMTO scheme for permutations (note).  Stinson 6.16.2, 7.17.4, KatzLindell 8.2, 10.5, 12.112.4, 12.7 
10  Dec 22, 23  Secret Sharing Schemes ($n$outof$n$ and $t$outof$n$) ; Threshold Cryptography; Hard Core Bits; Coin Flipping Over the Phone. Lecture 10 (with typos fixed)  Threshold cryptography.  Hellman's TMTO scheme for general functions.  
11  Dec 29, 30  Threshold cryptography: $t$outof$n$ El Gamal encryption. Lecture 11 (revised Jan. 16). Interactive proofs and zero knowledge proofs. Maurice Herlihy's presentation 
Yao's Millionaire problem (presented as an age comparison problem).  
12  Jan 5, 6  Identification (user authentication): FiatShamir scheme. Lecture 12  Knapsack type public key cryptosystems, and their susceptibility to shortest vector attacks. Odlyzko's survey  Solutions to home assignments (#1 and half of #2).  
13  Jan 12, 13  Public key cryptosystems based on high dimensional lattices. Guest lecture by Prof. Oded Regev. Lattices presentation  Finding square roots (and roots of any low degree polynomial) efficiently in any finite field. Michael Rabin's paper  ShanksTonelli's algorithm for square root modulo $p$. Solutions to home assignments (other half of #2). 

14  Jan 19, 20  Review of course material and solutions to exams from previous years.  Solutions to home assignments (#3 and #4). 