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; Administrativia, course topics, etc. 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). |