Code-Based Cryptography (W5) — read upstream

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.

Contents