# Code-Based Cryptography (W5) — read upstream

Week 5 follows the upstream cryptanalysis book chapter on code-based
cryptography. The chapter is comprehensive and will be supplemented in the
lecture with a deeper dive into information-set decoding (ISD) attacks and the
recent NIST standardisation of HQC (March 2025).

| Week | Chapter | Direct link |
|------|---------|-------------|
| **W5** | **Ch 43 — Code-Based Cryptography: McEliece and Goppa Codes** | <https://bnaskrecki.faculty.wmi.amu.edu.pl/crypto/book/part15_code_based_frontiers/ch43_code_based_crypto.html> |

## Coverage map

The upstream chapter covers, in order:

1. Linear codes, syndrome decoding, NP-hardness.
2. Binary Goppa codes, $\mathrm{GF}(2^m)$ arithmetic, Patterson decoding (sketch).
3. Classic McEliece cryptosystem.
4. Niederreiter dual.
5. Information-set decoding attacks (Prange).
6. Six exercises ranging from syndrome-table construction to a Patterson
   implementation challenge.

In the **lecture**, we will additionally cover material **not** in the upstream
chapter:

- **Stern's** and **BJMM**'s improvements to ISD (cost is $2^{0.097n}$ for
  random binary codes, vs Prange's $2^{0.121n}$).
- **BIKE** (Bit-Flipping Key Encapsulation) — a candidate based on QC-MDPC codes
  that reached NIST round 4 alongside HQC.
- **HQC** (Hamming Quasi-Cyclic) — selected by NIST on **11 March 2025** as the
  fifth PQC standard (and the only code-based KEM).
- Practical implications: McEliece public keys are **megabyte-scale** (1–4 MB
  depending on parameters); HQC sits at ~7 KB. Why the gap, and what it means
  for deployment.

## Lab focus

- Toy McEliece on Hamming or small Goppa codes (the upstream chapter provides
  a working class — extend it).
- Brute-force ISD on tiny parameters: implement Prange's algorithm and measure
  its actual running time vs. the Hamming-bound prediction.
- (Stretch goal) Read and run the reference implementation of BIKE or HQC from
  the NIST PQC submission package.