Course Schedule

# Weekday Regular Schedule

Group Type Hours Location
01 Lecture Tue 10-13 Orenstein 111
02 Recitation Wed 17-18 Orenstein 111

# Course Plan

Week Date Crypto Subject Mathematics Background Recitation Textbook Reference
1 Oct 20 Popular introduction to Modern Crypto;
Lecture1
The mod operation over integers; The ring $\mathbb{Z}_N$. No recitation. Stinson 1.1.1;
Shoup 2.1-2.4, 3.1-3.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;
Katz-Lindell 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; Katz-Lindell 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; Katz-Lindell 4.1-4.7, 5.4
5 Nov 17, 18 Discrete logarithm problem in $\mathbb{Z}_p$; Diffie-Hellman's key exchange. Lecture 5 SageCode5 Quadratic residues in $\mathbb{Z}_m$. A Diffie-Hellman variant: EKE; Discrete log modulo $p=2^n+1$ is easy. SageCode6 Stinson 5.2.1, 5.4; Katz-Lindell 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, Katz-Lindell 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 Katz-Lindell 7.2, 8.1
8 Dec 8, 9 SSL and PKI: Guest lecture by Prof. Ran Canetti. Slides giving overview of TLS. tls-overview More integer factoring algorithms. Factoring numbers with the quadratic sieve (part 2 of 2).
9 Dec 15, 16 El-Gamal PKC and signature scheme, both based on discrete logs. Lecture 9 Hanukka special (conditions apply): Levitation without meditation. Time-memory tradeoffs. Shank's baby-step giant-step algorithm for discrete log in $\mathbb{Z}_p$. Hellman's TMTO scheme for permutations (note). Stinson 6.1-6.2, 7.1-7.4, Katz-Lindell 8.2, 10.5, 12.1-12.4, 12.7
10 Dec 22, 23 Secret Sharing Schemes ($n$-out-of-$n$ and $t$-out-of-$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$-out-of-$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): Fiat-Shamir 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 Shanks-Tonelli'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).