Lectures | Dates | Mon | Literature |
1 | 09/Jan | Introduction and course organization; review of PKE scheme. | [Gal12, Ch. 1] |
2 | 11/Jan | Review of textbook RSA; security notions and attack models; attacks for RSA. |
[Gal12, Ch. 1 and Ch. 24] |
3 | 18/Jan | Attacks on RSA parameters: Wiener attack etc. | [Gal12, Ch. 24] D. Boneh. Twenty years of attacks on the RSA cryptosystem M. Wiener. Cryptanalysis of Short RSA Secret Exponents |
4 | 23/Jan | Attacks on RSA variants: CRT-RSA and attacks. | [Gal12, Ch. 24] D. Boneh. Twenty years of attacks on the RSA cryptosystem |
5 | 25/Jan | Lattices: definition, Gram-Schmidt, determinant, minimum distance. |
[Gal12, Ch. 16] D. Micciancio's Lecture 1 O. Regev's Lecture 1 |
6 | 30/Jan | Lattices: Minkowski's theorems; lattice problems | [Gal12, Ch. 16] D. Micciancio's Lecture 1 O. Regev's Lecture 1 |
7 | 1/Feb | Lattices: LLL algorithm. | [Gal12, Ch. 17] D. Micciancio's Lecture 3 O. Regev's Lecture 2 A. K. Lenstra, H. W. Lenstra, L. Lovász. Factoring polynomials with rational coefficients |
8 | 6/Feb | Coppersmith method and more attacks on RSA parameters |
[Gal12, Ch. 17] D. Micciancio's Lecture 8 O. Regev's Lecture 4 D. Coppersmith. Finding a Small Root of a Univariate Modular Equation |
9 | 8/Feb | Knapsack cryptosystem and lattice attack | A. M. Odlyzko. The Rise and Fall of Knapsack Cryptosystems A. M. Frieze. On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem |
10 | 13/Feb | Composite tests: Fermat, Solovay-Strassen and Millerâ€“Rabin tests. | [CrP05, Ch. 3 (eBook FAU)] |
11 | 15/Feb | Primality tests: Lucas, Pépin, Proth and Pocklington-Brillhart-Lehmer-Selfridge tests. | [CrP05, Ch. 3 (eBook FAU)] C. Pomerance. Primality testing: variations on a theme of Lucas |
12 | 20/Feb | Introduction to elliptic curves | [CrP05, Ch. 7 (eBook FAU)] |
13 | 22/Feb | ECPP primality tests: Goldwasser-Kilian and Atkin-Morain; ECM. | [CrP05, Ch. 7 (eBook FAU)] S. Goldwasser and J. Kilian. Primality Testing Using Elliptic Curves H. W. Lenstra. Factoring integers with elliptic curves |
14 | 27/Feb | AKS primality test | M. Agrawal, N. Kayal and N. Saxena.Primes is in P |
15 | 01/Mar | Integer factorization: trial division, sieving, Fermat's and Pollard's Rho method. | [Gal12, Ch. 14] J. M. Pollard. A Monte Carlo method for factorization R. P. Brent. An improved Monte Carlo factorization algorithm |
16/17 | Spring Break | ||
18 | 13/Mar | Pollard's Rho method for DLP, Oorschot and Wiener's parallelization. | [Gal12, Ch. 14] J. M. Pollard. Monte Carlo Methods for Index Computation (mod p) P. C. van Oorschot and M. J. Wiener. Parallel Collision Search with Cryptanalytic Applications |
19 | 15/Mar | Integer factorization: Pollard's p-1 method, Lenstra's elliptic curve method. | [CrP05, Ch. 7 (eBook FAU)] J. M. Pollard. Theorems of factorization and primality testing H. W. Lenstra. Factoring integers with elliptic curves |
20 | 20/Mar | Integer factorization: analysis of ECM, Dixon's method. | [CrP05, Ch. 7 (eBook FAU)] A. Granville. Smooth numbers: computational number theory and beyond J. D. Dixon. Asymptotically fast factorization of integers C. Pomerance. Analysis and Comparison of Some Integer Factoring Algorithms |
21 | 22/Mar | Integer factorization: quadratic sieve. | [CrP05, Ch. 6 (eBook FAU)] C. Pomerance. Smooth numbers and the quadratic sieve |
22 | 27/Mar | Number field sieve for integer factorization and DLP. | [CrP05, Ch. 6 (eBook FAU)] A. K. Lenstra, H. W. Lenstra, M. S. Manasse and J. M. Pollard. The number field sieve J. P. Buhler, H. W. Lenstra and C. Pomerance. Factoring integers with the number field sieve |
23 | 29/Mar | Parameters for RSA-based schemes; Pohlig-Hellman algorithm and Baby-step Giant-step for DLP. |
[CrP05, Ch. 5 (eBook FAU)] Digital Signature Standard: FIPS PUB 186-4 S. Pohlig and M. Hellman. An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance |
24 | 03/Apr | Pollard's kangaroo method for DLP; Parameters for DLP-based schemes. |
J. M. Pollard. Monte Carlo Methods for Index Computation (mod p) J. M. Pollard. Kangaroos, Monopoly and Discrete Logarithms S. D. Galbraith, J. M. Pollard and R. S. Ruprai. Computing discrete logarithms in an interval NIST Special Publication 800-56A Rev2. Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography |
25 | 05/Apr | Block ciphers: security notions and attack models; brute-force attacks; Diffie and Hellman's meet-in-the-middle for multiple encryption; Hellman's tradeoff attack on block ciphers |
[YL14, Ch. 6] W. Diffie and M. E. Hellman. Exhaustive Cryptanalysis of the NBS Data Encryption Standard M. E. Hellman A cryptanalytic time-memory trade-off |
26 | 10/Apr | Design principles of block ciphers; substitution-permutation network; attacks for reduced-round simple SP-network |
[YL14, Ch. 6] |
27 | 12/Apr | Linear analysis of block ciphers; piling-up lemma; BKW for LPN |
[YL14, Ch. 6] H. M. Heys. A Tutorial on Linear and Differential Cryptanalysis M. Matsui. Linear Cryptanalysis Method for DES Cipher |
28 | 17/Apr | Introduction to quantum computing; quantum key distribution | |
29 | 19/Apr | Quantum algorithms | |