Synopsis

The goal is to introduce cryptography and the main mathematical tools used in cryptography. The main focus will be on public key cryptosystems. Each lecture will aim to illustrate a cryptographic concept and the related mathematics. Each week there will be a cryptographic challenge.

Summary of Lectures

Lecture 1.

Terminology.
Classical cryptographic systems.
Examples.
Exercises + Crypto Challenge #1.

Lecture 2.

Elements of probability theory.
Information theory.
Entropy and mutual information.
Decision functions.
Cryptanalysis of classical cryptosystems.
Exercises + Crypto Challenge #2.

Lecture 3.

Two strong classical ciphers - a study.
Protocols.
Authentication - Privacy - Secrecy
The discrete log problem.
Index calculus.
Public Key Cryptography.
The key distribution and authentication problems.
Cryptographic uses of discrete logs.
Exercises + Crypto Challenge #3.

Lecture 4.

Computational complexity.
Turing machines.
P - NP and cryptographically hard problems.
Number lengths and run time estimates.
P-NP and NP completeness.
RP and BPP.
Arithmetic and the Fast Fourier Transform.
Exercises + Crypto Challenge #4.

Lecture 5.

Public Key Cryptosystems.
The key distribution problem revisitied.
The d'Urfe problem.
Trapdoor one way functions.
Finite fields : some theorems.
RSA.
Exercises + Crypto Challenge #5.

Lecture 6.

Elliptic curve cryptography.
Definition of Abelian varieties and Elliptic curves.
The group law.
The idea of Miller and Koblitz.
A review of finite fields and finite field arithmetic.
Elliptic curves over finite fields.
Exercises + Cryto Challenge #6.

Lecture 7.

The Elliptic curve discrete log problem.
Elliptic curve cryptography.
Examples.
Exercises + Crypto Challenge #7.

Lecture 8.

An introduction to hyperelliptic curve cryptography.
or
Quantum Cryptography
Exercises + Crypto Challenge #8.

Reading list

Complexity and cryptography : An introduction. John Talbot and Domininc Welsh. Cambridge University Press, 2006.

Elliptic Curves : Number theory and cryptography. Lawrence C. Washington. Chapman and Hall, 2003.