# 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](w1_landscape/ch46_exercises.ipynb) |
| W2   | Lattice geometry, LLL, breaking knapsacks          | Upstream **Ch 40** + [**LLL tutorial (Ch 49) with 4 applications**](w2_lattices/lll_tutorial.ipynb) |
| W3   | LWE → Kyber (ML-KEM, FIPS 203)                     | Upstream **Ch 41** + [**Regev's LWE tutorial (Ch 50)**](w3_lwe/regev_tutorial.ipynb) |
| 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](w6_hash_based/ch47_exercises.ipynb) |
| W7   | NTRU, multivariate, isogeny — and their breaks     | **This book — Chapter 48** (new) + [exercises](w7_other_families/ch48_exercises.ipynb) |
| 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.

```{admonition} Why a hybrid book?
:class: tip
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.
```

```{admonition} Student projects — ten topics
:class: tip
A separate **[Student Project Catalogue](projects/student_projects.ipynb)**
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.
```

```{admonition} Practical exercises with hidden solutions
:class: tip
Each new chapter has a sister page **Practical Exercises** (Ch 46/47/48 →
[46 exercises](w1_landscape/ch46_exercises.ipynb) /
[47 exercises](w6_hash_based/ch47_exercises.ipynb) /
[48 exercises](w7_other_families/ch48_exercises.ipynb)).
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)

```bash
# 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.

```bash
# 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.
```

```{admonition} Sage is optional, not required
:class: warning
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

```bash
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`.