Post-Quantum Cryptography — UAM Course Companion

Post-Quantum Cryptography — UAM Course Companion#

“The quantum theorem is going to win, no matter what we do. So we’d better find a way to encrypt that doesn’t depend on factoring.” — Peter Shor (paraphrased), 1994

Welcome#

This is the post-quantum half of the course Kryptografia kwantowa i postkwantowa (UAM, Informatyka kwantowa, sem. 6, 2025/26). The first half of the course covered topics 1–8 of the official syllabus — the quantum side, including BB84, E91, Shor’s algorithm (which you implemented in Qiskit), Grover’s search, and the basics of computational complexity. In May and June 2026, Bartosz Naskręcki takes you through topics 9–11: post-quantum cryptography proper.

This companion book is built on top of the larger 60-hour cryptanalysis course book Elements of Cryptanalysis: From Al-Kindi to Post-Quantum Standards available at https://bnaskrecki.faculty.wmi.amu.edu.pl/crypto/. Some weeks reuse chapters from that book directly; others are written fresh in this companion to fill gaps that the original course did not cover in depth.

Leitfaden — How to Read This Book#

The course runs over 8 Tuesdays (May–June 2026), each Tuesday delivering one 90-min lecture (10:00–11:30, sala F-62) and one 90-min lab (11:45–13:15, sala B-019). Total: 15 academic hours of lectures + 15 of labs = 15 × 90-min blocks worth ~22.5 clock hours of contact time. Every “academic hour” is 45 minutes; every block is 2 academic hours.

The eight weeks map onto the post-quantum families as follows:

Week

Topic

Source

W1

PQC landscape, knapsack, Merkle–Hellman

This book — Chapter 46 (new) + exercises

W2

Lattice geometry, LLL, breaking knapsacks

Upstream Ch 40 + LLL tutorial (Ch 49) with 4 applications

W3

LWE → Kyber (ML-KEM, FIPS 203)

Upstream Ch 41 + Regev’s LWE tutorial (Ch 50)

W4

Lattice signatures (Dilithium, Falcon) and attacks

Upstream Ch 42 — Attacks on Lattice-Based Schemes

W5

Code-based crypto: McEliece, BIKE, HQC

Upstream Ch 43 — Code-Based Cryptography

W6

Hash-based signatures: Lamport → SPHINCS+

This book — Chapter 47 (new) + exercises

W7

NTRU, multivariate, isogeny — and their breaks

This book — Chapter 48 (new) + exercises

W8

NIST standards, hybrid TLS, deployment

Upstream Ch 44–45 + project presentations

Reading order: each week, follow the chapter link in the table. The “external” entries in the side navigation simply point you to the upstream cryptanalysis book.

Why a hybrid book?

The cryptanalysis course already contains polished, runnable chapters on lattices (Ch 40–42), McEliece (Ch 43), and the NIST standards (Ch 44–45). Re-implementing them here would duplicate work without adding pedagogical value. The three new chapters in this book fill the gaps the cryptanalysis course did not cover: the Merkle–Hellman warm-up, the full hash-based signature pipeline, and the NTRU / multivariate / isogeny families.

Student projects — ten topics

A separate Student Project Catalogue lists ten self-contained mini-projects (★ to ★★★★), each with description, literature pointers, and the specific code pieces to implement plus what to show on W8. Pick one, send your choice to the instructor before W5, plan a 10-minute presentation with a 2-page write-up for W8.

Practical exercises with hidden solutions

Each new chapter has a sister page Practical Exercises (Ch 46/47/48 → 46 exercises / 47 exercises / 48 exercises). Six exercises per chapter, ranging from one-liner (★) to research project (★★★★★). Each exercise has a partial-code “your turn” cell with TODO gaps, and a fully-commented solution cell hidden behind a “Click to show” button. Try the exercise yourself first; the gaps point at concepts the chapter teaches.

What You Will Learn#

By the end of the course you will be able to:

  • Explain why each NIST PQC standard rests on a different hard problem, and what it would take (classically or quantumly) to break it.

  • Implement toy versions of ML-KEM, Lamport signatures, Merkle trees, NTRU, and small Goppa-code McEliece in pure Python.

  • Run known attacks: LLL on a low-density knapsack, Kannan-embedding on toy LWE, brute-force information-set decoding, and a sketch of the Castryck–Decru break of SIDH.

  • Estimate parameter security using community tools (Albrecht’s lattice-estimator).

  • Deploy a post-quantum hybrid TLS handshake using OpenSSL with the OQS provider, and measure the bandwidth overhead.

  • Argue about migration trade-offs (signature size vs. key size vs. assumption diversity) at the level needed to advise a customer or write a policy memo.

Prerequisites#

You have already covered most of these in the first half of the course or in earlier semesters:

  • Linear algebra — bases, matrices, orthogonalisation, ranks.

  • Modular arithmetic and number theory — Euler’s \(\varphi\), CRT, primes, factoring.

  • Probability — Gaussians, conditional probability, expectation.

  • Computational complexity — P, NP, NP-complete, BQP, hardness reductions.

  • Quantum algorithms — Shor (you implemented it in Qiskit), Grover, QFT.

  • Classical cryptography — RSA, Diffie–Hellman, AES, hash functions.

  • Python programming — comfortable with NumPy and Jupyter.

If any item above is genuinely shaky, refer to the corresponding chapter of the upstream cryptanalysis book (Ch 1–39) before the relevant lecture.

Technical Setup#

All new chapters are runnable Jupyter notebooks. They use only NumPy, Matplotlib, SymPy, and the Python standard library (in particular hashlib). No exotic frameworks are required; nothing is downloaded at runtime.

Minimum environment (required for every lab)#

# Create and activate a fresh venv (or use conda)
python3 -m venv pqc-uam
source pqc-uam/bin/activate

# Install the minimum stack
pip install numpy matplotlib sympy jupyter notebook

That’s it for Chapters 46, 47, and 48. The notebooks open with jupyter notebook or jupyter lab.

Optional environment (for selected labs and the project)#

These are needed only for specific lab exercises noted at the start of each week. Install them lazily when you reach the relevant lab.

# W3 lab — reference Kyber / Dilithium implementations
pip install pycryptodome
pip install pqcrypto                # pure-Python reference Kyber/Dilithium

# W4 lab — lattice security estimation
pip install fpylll                  # used inside the lattice-estimator
git clone https://github.com/malb/lattice-estimator
# then: from estimator import LWE; ...

# W5 lab — Goppa code arithmetic over GF(2^m)
# Use Python only; all arithmetic implemented from scratch in Ch 43.

# W6 lab — SPHINCS+ reference implementation (optional)
git clone https://github.com/sphincs/sphincsplus

# W7 lab — Sage-only sections (small isogeny graph visualisation)
# Conda env recommended:
#   conda create -n sage -c conda-forge sage
#   conda activate sage
#   sage -n jupyter

# W8 lab — Hybrid TLS handshake with post-quantum KEMs
# Install OpenSSL >= 3.2 + the oqs-provider:
#   https://github.com/open-quantum-safe/oqs-provider
# This is the only non-Python software dependency in the entire course.

Sage is optional, not required

Most of W7 (Chapter 48) runs in plain Python. Only the small isogeny-graph visualisation in §48.7 benefits from SageMath’s EllipticCurve class. If you do not have Sage installed you can skip that one cell — the rest of the chapter is self-contained.

Building the book locally#

cd book/
pip install jupyter-book>=1.0
jb build .
open _build/html/index.html

Evaluation#

Your final grade for the course is set by the course coordinator. For this half:

  • Lab grade (“Zaliczenie z oceną” per the syllabus) is determined by a small project. Pairs of students pick one PQC scheme from the list below, deliver a toy reference implementation (≤ 500 lines of Python), reproduce one known attack or security argument against it, and present the result in the W8 session.

    Suggested project topics: ML-KEM, ML-DSA, Falcon, Classic McEliece, BIKE, HQC, XMSS, SPHINCS+, NTRU-Prime, CSIDH, SQIsign.

  • Exam is administered jointly at the end of the semester; it covers both halves of the course.

Course Rules#

Course code

04INKS.320.02442.25

Course type

Specjalnościowy, fakultatywny

Programme

Informatyka kwantowa, studia inżynierskie pierwszego stopnia

Semester

2025/2026 (summer), Sem. 6

ECTS

5

Total contact hours

60 (30 wykład + 30 laboratorium)

Our slice

30 contact hours = 15 × 90-min blocks

Faculty

Wydział Fizyki i Astronomii (we are guests from WMI)

Instructor (this half)

dr hab. Bartosz Naskręcki (WMI UAM)

Schedule

Tuesdays, 10:00–11:30 (lecture, sala F-62) and 11:45–13:15 (lab, sala B-019), May–June 2026

Language

English

Key Papers (for our half)#

  1. Ajtai, M. (1996). Generating Hard Instances of Lattice Problems. STOC ‘96.

  2. Regev, O. (2005). On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. STOC ‘05.

  3. McEliece, R. J. (1978). A Public-Key Cryptosystem Based on Algebraic Coding Theory. DSN Progress Report 42-44.

  4. Merkle, R. C. and Hellman, M. E. (1978). Hiding Information and Signatures in Trapdoor Knapsacks. IEEE Trans. Information Theory.

  5. Shamir, A. (1984). A Polynomial-Time Algorithm for Breaking the Basic Merkle–Hellman Cryptosystem. IEEE Trans. Information Theory.

  6. Hoffstein, J., Pipher, J., Silverman, J. H. (1998). NTRU: A Ring-Based Public Key Cryptosystem. ANTS-III.

  7. Castryck, W. and Decru, T. (2023). An Efficient Key Recovery Attack on SIDH. EUROCRYPT 2023.

  8. Beullens, W. (2022). Breaking Rainbow Takes a Weekend on a Laptop. CRYPTO 2022.

  9. Bernstein, D. J. et al. (2019). The SPHINCS⁺ Signature Framework. CCS ‘19.

  10. NIST (2024). FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), FIPS 205 (SLH-DSA). https://csrc.nist.gov/publications/fips.

A complete BibTeX file is in references.bib.

Contents