Cryptography

Timetable

Module aim (aims)

Assumptions and Objectives:

To present the basic concepts and algorithms of classical cryptography
and give an introduction to quantum cryptography and quantum cryptoanalysis.

Upon completion of the module and confirmation of achievement, a student should know:
basic cryptolograhic terminology,
methods of the cryptoanalysis of basic ciphers,
how to implement selected symmetric cryptosystems,
how to implement selected public-key cryptosystems,
several digital signature algorithms,
basic quantum key distribution protocols,
basic classical and quantum factorization algorithms, and
how to numerically simulate selected quantum cryptographic systems.

Pre-requisites in terms of knowledge, skills and social competences (where relevant)

Knowledge of the basic concepts and methods of quantum mechanics
is assumed. However, the course is essentially self-contained in
the concepts of the number theory, cryptography, and quantum
information.

Syllabus

week 1:

Introduction to cryptography.
Tasks of cryptography:
1. message confidentiality,
2. message authentication,
3. message integrity,
4. message non-repudiation.

War ciphers:
1. Enigma - Rejewski's bomb and Turing's bomb.
2. Ciphers of the Polish-Soviet war of 1920: Miracle on the Vistula.
3. Ciphers of the Wielkopolska Uprising.
4. Global e-intelligence networks: Echelon, PRISM, MUSCULAR and others.

Cryptanalysis of a simple substitution cipher (i.e., the Poe ciphertext).
Basic cryptographic terms:
Cryptanalysis, decryption, and eavesdropping.
Private keys, public keys, and hash functions.

Simple ciphers:
1. substitution ciphers,
2. transposition ciphers,
3. wandering key ciphers,
4. poly-alphabetic ciphers,
5. one-time pad (Vernam's cipher).
Principles of secure encryption: diffusion and confusion.
Shannon's pastry dough mixing.

week 2:

Introduction to quantum cryptography:
Application of no cloning theorem for secure information transfer.
BB84 protocol for quantum key distribution.
Wiesner's protocol of quantum money.
Optical implementations of the BB84 and Wiesner protocols.
A brief overview of other quantum protocols and algorithms.

weeks 3 and 4:

Elements of number theory in cryptography:
1. Euclid's algorithm.
2. Euler's algorithm of modular exponentiation.
3. Fermat's little theorem.
4. Euler's theorem.
5. Chinese remainder theorem and Gauss's algorithm.
6. Multiplicative groups, cyclic groups, and their generators.
7. Quadratic residues (modular square roots): properties and algorithms, Legendre and Jacobi symbols, and Blum numbers.

week 5:

Asymmetric cryptography (public-key cryptography):
Basic concepts and algorithms.
Mathematical computational problems of cryptographic interest.
Number of keys in symmetric and asymmetric cryptography.
Rivest-Shamir-Adleman (RSA) algorithm.
Naive methods of attack on the RSA cryptosystem.
RSA hypothesis.

week 6:

Shamir's three-step protocol.
A hybrid cryptographic protocol.
Cryptographic control of the arms race during the Cold War.

Simple symmetric and asymmetric message authentication protocols.
Diffie-Hellman key exchange algorithm.
A generalized Diffie-Hellman algorithm for three correspondents.
Knapsack algorithms: Merkle-Hellman algorithm.

week 7:

Message encryption and authentication protocols:
ElGamal's encryption algorithm,
ElGamal's signature algorithm,
Rabin's encryption algorithm,
Rabin's signature algorithm.

week 8:

Probabilistic encryption:
Goldwasser-Micali and Blum-Goldwasser algorithms.

Zero-knowledge proofs of identity:
Fiat-Shamir and Feige-Fiat-Shamir identification protocols.

week 9:

Towards the cryptanalysis of RSA:

Number primality tests:
1. Fermat's test,
2. Euler's test,
3. Agrawal-Kayal-Saxena (AKS) test,
4. elliptic curve primality test,
6. Miller's test.

Classical algorithms for number factorization:
1. Eratosthenes sieve,
2. Monte Carlo method,
3. standard and generalized Fermat's methods,
4. Legendre method of continued fractions,
5. Square sieve method,
6. Comparison of their efficiencies.

Prime numbers:
Mersenne prime numbers.
Great Internet Mersenne Prime Search (GIMPS).
Twin prime numbers.
Lucas-Lehmer test of Mersenne numbers.
Ulam's spiral of prime numbers.

week 10:

The Riemann hypothesis and prime numbers:
Euler's Z function.
Riemann's zeta function.
Millennium Problems.
Zeroes of the Riemann zeta function and the eigenvalues of Hamiltonians.
Bender's PT-symmetric quantum mechanics.
The Riemann problem and superluminal communication.

week 11:

Computational complexity of problems in cryptography:
Deterministic Turing machine and P-type problems (polynomial time algorithms).
Non-deterministic Turing machine and NP-type (non-deterministic polynomial time) problems.
Types of problems: NTIME, NP, NEXPTIME, NSPACE, NPSPACE, and NEXPSPACE.
NP-hard problems.
NP-complete problems.
The hypothesis whether P = NP.
Universal Turing machine.
Quantum Turing machine as a universal quantum computer.
BQP (Bounded-error Quantum Polynomial-time) type problems.

NP-hard problems in cryptography:
McEliece cryptosystem, NTRUEncrypt, and Merkle-Hellman cryptosystem.
Computational complexity of knapsack algorithms.
Is factorization of numbers an NP-complete problem?

week 12:

Quantum algorithms in the cryptanalysis of classical cryptosystems:
Shor's factorization algorithm.
Implementation of Shor's algorithm using NMR spectroscopy.

week 13:

First and second generation quantum technologies.
Quantum annealing for cryptoanalysis.
Implementation of quantum annealing using superconducting qubits.
Algorithm of factorization by Gauss sums (and Schroedinger cats).
Implementation of the Gauss-sum algorithm using NMR spectroscopy.

week 14:

Quantum key distribution protocols:
1. BB84 protocol - a brief reminder.
2. Ekert E91 protocol using entangled states.
3. Bennett B92 protocol using Mach-Zehnder interferometers.
4. Renes R04 protocol.
5. Implementations of BB84 and E91 protocols using a quantum satellite.

week 15:

Post-quantum cryptography, i.e.
classical cryptography resistant to quantum cryptanalysis by Shor's algorithm.
Recommended public key lengths.
RSA challenges and rewards.
McEliece cryptosystem.

Concluding remarks:
The future of public-key cryptography.
The future of quantum cryptography.

Reading list

Basic textbook for classical cryptography:

A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, "Handbook of Applied Cryptography",  CRC Press, 1996.

Supplementary literature on classical cryptography:

B. Schneier, "Applied Cryptography", Wiley, 2010.

Supplementary literature on quantum cryptography:

1. M. A. Nielsen and I.L. Chuang "Quantum Computation and Quantum Information", Cambridge University Press, Cambridge, 2000.
2. N. Gisin, G. Rinordy, W. Tittel, H. Zbinden, "Quantum cryptography", Reviews of Modern Physics, Vol. 74, 2002.
3. C.H. Bennett, G. Brassard, A.K. Ekert, "Quantum cryptography," Science World, December 1992.