Cryptographic Protocols

Teacher: Sergey Nikolenko

The course is devoted to cryptographic protocols and primitives: RSA, elliptic curve crypto, secret sharing, and zero-knowledge proofs, and algorithms for breaking all of them: factoring and discrete logarithm. See also the course homepage.

1. Introduction. The subject and history of cryptography. Cryptographic attacks. Cryptographic primitives: hash functions, secret key, and public key protocols.

2-3. Secret key cryptography. Block ciphers: ECB, CBC, CFB, and OFB. Message authenticity codes. Secret key cryptography via hash functions.

4. Stream ciphers: synchronous and asynchronous codes, pseudorandom sequences, pn-sequences, LFSRs, linear complexity, non-linear shift registers.

5-6. Euclid's algorithm for polynomials, reconstructing rational functions, learning LFSRs. Reed-Solomon codes.

See Chapter 17 of A Computational Introduction to Number Theory and Algebra

7. Key agreement protocols. Diffie-Hellman. AKEP. Shamir's protocol. Otway–Rees protocol. Kerberos. Needham–Shroeder protocol. X.509. Attacks: man-in-the-middle, reflection, interleaving, misplaced trust. Key distribution. Secret sharing.

8. Factoring. Fermat's method. Kraitchik's method. Smooth numbers, their distribution. Quadratic sieve and its complexity. Solving linear systems: Wiedemann's algorithm.

9. Discrete logarithm. O(sqrt(n))-methods: Pollard's rho and Pollard's lambda. Index calculus: main idea and the first two phases.

10. Index calculus: third phase and complexity bound.

11. Elliptic curves: basic definitions, singular and nonsingular curves, projective plane and projective curves. Resultants.

See, e.g., J.S. Milne, Elliptic Curves.

12. Intersection numbers. Bezout's theorem. The group law on the elliptic curves.

See, e.g., J.S. Milne, Elliptic Curves.

13. Lenstra's ECM algorithm.

14. Quantum computing: basics. Entanglement, interference, parallelism. Deutsch-Jozsa problem. Quantum Fourier transform. Shor's algorithm.

15. Noncommutative cryptography: groups in cryptography, Ko-Lee protocol, Anshel-Anshel-Goldfeld protocol. Braid groups. Attacks: length-based attacks and linearization.