{ "cells": [ { "cell_type": "markdown", "id": "ch46-000", "metadata": {}, "source": [ "# Chapter 46: The Post-Quantum Landscape and the Knapsack Problem\n" ] }, { "cell_type": "markdown", "id": "ch46-001", "metadata": {}, "source": [ "## 46.1 Why Post-Quantum, Why Now\n", "\n", "You have already implemented Shor's algorithm in Qiskit. The exact thing that makes\n", "it pedagogically delightful — that an integer can be factored in polynomial time on\n", "a quantum computer once we have one — is precisely what makes it strategically\n", "catastrophic. RSA, Diffie–Hellman, ECDH, ECDSA, EdDSA: every public-key primitive\n", "in widespread use today rests on the hardness of either integer factorisation or\n", "discrete logarithm in some abelian group. Shor's algorithm dispatches the entire\n", "list in one stroke.\n", "\n", "```{admonition} What \"post-quantum\" means\n", ":class: important\n", "A **post-quantum** (or \"quantum-resistant\", or \"quantum-secure\") cryptosystem is a\n", "cryptosystem that runs on classical hardware (so we can deploy it today on commodity\n", "CPUs) but is believed to remain secure against an adversary who has a fault-tolerant\n", "quantum computer. The phrase is *not* synonymous with \"quantum cryptography\", which\n", "refers to schemes like BB84 that *use* quantum hardware as part of the protocol.\n", "```\n", "\n", "The urgency is not \"wait for the quantum computer to arrive\". The urgency is the\n", "**harvest-now-decrypt-later** threat: any encrypted traffic captured today and\n", "stored — by a state actor, a service provider, an opportunistic eavesdropper —\n", "can be decrypted in the future once a sufficiently large quantum computer exists.\n", "For data with a long confidentiality lifetime (medical records, diplomatic cables,\n", "intellectual property), the migration deadline is not the day the quantum computer\n", "boots; it is some number of years *before* that day, equal to the data's required\n", "secrecy lifetime.\n", "\n", "The US National Security Agency's CNSA 2.0 guidance (2022, updated 2024) sets\n", "**software/firmware signing** to PQC by 2025, **TLS/IPsec** by 2030, and **full\n", "transition** by 2033. The EU agencies (BSI, ANSSI, ENISA) advocate hybrid\n", "deployments as a transitional defence-in-depth measure.\n" ] }, { "cell_type": "markdown", "id": "ch46-002", "metadata": {}, "source": [ "## 46.2 The Five Post-Quantum Families\n", "\n", "The candidate post-quantum cryptosystems group into a small number of families,\n", "each based on a different believed-hard problem. Section 10 of our course\n", "syllabus enumerates six; in practice the symmetric family is barely affected by\n", "quantum attack (Grover halves the effective key length, no more), so the focus\n", "falls on five public-key families:\n", "\n", "| Family | Hard problem | Standardised? |\n", "|---|---|---|\n", "| **Lattice-based** | LWE / Module-LWE / NTRU | ML-KEM (FIPS 203), ML-DSA (FIPS 204), Falcon/FN-DSA (draft FIPS 206) |\n", "| **Code-based** | Decoding random linear codes (NP-hard) | Classic McEliece (4th-round), HQC (selected 2025) |\n", "| **Hash-based** | Collision/preimage resistance of a hash function | SLH-DSA (FIPS 205), XMSS/LMS (RFC 8391/8554) |\n", "| **Multivariate** | Solving systems of polynomial equations over a finite field (MQ) | None standardised; Rainbow broken in 2022 |\n", "| **Isogeny-based** | Walking the supersingular isogeny graph | None standardised; SIDH/SIKE broken in 2022 |\n", "\n", "Two important properties cut across the table:\n", "\n", "- **Diversity of assumption.** ML-KEM and ML-DSA both rest on Module-LWE. If a\n", " surprise breakthrough were to break Module-LWE, the bulk of the deployed PQC\n", " ecosystem would fall in one stroke. NIST has therefore deliberately\n", " standardised at least one scheme from a different family in each role: HQC\n", " (code-based) as an alternative KEM to ML-KEM; SLH-DSA (hash-based) as an\n", " alternative signature to ML-DSA. **Crypto-agility** is the policy that\n", " preserves this diversity in deployment.\n", "- **The \"frontier\" families are fragile.** Both multivariate and isogeny-based\n", " cryptography saw their flagship schemes broken in 2022 (Rainbow by Ward\n", " Beullens; SIDH/SIKE by Castryck and Decru). The mathematics underlying these\n", " families is younger and the cryptanalytic community smaller; we cover them\n", " in Chapter 48 partly because they remain interesting research directions\n", " and partly because their breaks illustrate, vividly, what it looks like\n", " when a lattice-or-code candidate eventually does fall.\n", "\n", "```{admonition} Table you should have memorised by W8\n", ":class: tip\n", "For each NIST standard: which family, which hard problem, what role\n", "(KEM vs signature), and one sentence on the size cost vs classical (X25519\n", "or Ed25519). It will save you on the exam.\n", "```\n" ] }, { "cell_type": "markdown", "id": "ch46-003", "metadata": {}, "source": [ "## 46.3 The NIST PQC Competition — A Brief History\n", "\n", "| Year | Event |\n", "|------|-------|\n", "| 2016 | NIST issues the call for PQC proposals. |\n", "| 2017 | 69 first-round submissions. |\n", "| 2019 | 26 second-round candidates. |\n", "| 2020 | 7 finalists + 8 alternates announced. |\n", "| 2022 | First selections: **CRYSTALS-Kyber** (KEM), **CRYSTALS-Dilithium** (signature), **Falcon** (signature), **SPHINCS+** (signature). |\n", "| 2024 | Standards published as **FIPS 203 (ML-KEM)**, **FIPS 204 (ML-DSA)**, **FIPS 205 (SLH-DSA)**. |\n", "| 2025 (March) | **HQC** selected as fifth standard (code-based KEM). |\n", "| 2025/2026 | **Falcon** standardisation as **FN-DSA / FIPS 206** still in progress. |\n", "\n", "Two of the original second-round candidates were broken during the competition,\n", "illustrating the value of public review:\n", "\n", "- **Rainbow** (multivariate signature) — broken by Beullens at CRYPTO 2022,\n", " reducing the published security level to \"weekend on a laptop\" for the\n", " proposed parameters.\n", "- **SIKE** (isogeny KEM, alternate candidate) — broken by Castryck and Decru\n", " in the summer of 2022, also reducing security to \"minutes on a laptop\"\n", " for SIKEp434.\n", "\n", "These breaks did not invalidate the families they came from (other multivariate\n", "constructions and other isogeny constructions like CSIDH, SQIsign remain\n", "candidates for future research), but they did remove the standardisation\n", "candidates and cool enthusiasm for the families. We discuss both in Chapter 48.\n" ] }, { "cell_type": "markdown", "id": "ch46-004", "metadata": {}, "source": [ "## 46.4 The Subset-Sum / 0-1 Knapsack Problem\n", "\n", "To get a concrete feel for \"NP-hard underpins a public-key cryptosystem\", we\n", "spend the rest of this chapter on the historically first attempt: the\n", "**Merkle–Hellman knapsack cryptosystem** (1978).\n", "\n", "```{admonition} Definition — Subset-Sum / 0-1 Knapsack\n", ":class: important\n", "Given a set of positive integers $a_1, \\ldots, a_n$ and a target sum $S$, find\n", "$\\bx = (x_1, \\ldots, x_n) \\in \\{0,1\\}^n$ such that\n", "\n", "$$\n", "\\sum_{i=1}^{n} x_i \\, a_i = S.\n", "$$\n", "```\n", "\n", "The decision version of this problem is **NP-complete** (Karp 1972). At first\n", "glance, then, building public-key encryption out of it looks irresistible: pick a\n", "public sequence $a_1, \\ldots, a_n$, encode a plaintext bitstring $\\bx$ as the\n", "ciphertext $S = \\sum x_i a_i$, and the decryption problem inherits NP-hardness.\n", "\n", "The catch — and Merkle and Hellman knew this — is that NP-hardness is a\n", "*worst-case* statement. We need *every* random instance of our scheme to be hard,\n", "not just some adversarial one. And as we shall see, a careful trapdoor that makes\n", "decryption easy for the legitimate recipient also makes the public sequence\n", "*non-random* in a way that cryptanalysts can exploit.\n" ] }, { "cell_type": "markdown", "id": "ch46-005", "metadata": {}, "source": [ "## 46.5 Superincreasing Knapsacks Are Easy\n", "\n", "```{admonition} Definition — Superincreasing Sequence\n", ":class: important\n", "A sequence $w_1, w_2, \\ldots, w_n$ of positive integers is **superincreasing** if\n", "\n", "$$\n", "w_k > \\sum_{i=1}^{k-1} w_i \\quad \\text{for every } k = 2, 3, \\ldots, n.\n", "$$\n", "```\n", "\n", "For a superincreasing sequence the subset-sum problem is solved by a **greedy**\n", "algorithm in $O(n)$ time: starting from the largest $w_n$ and working down,\n", "include $w_k$ in the subset whenever $w_k \\le S$ (and then subtract $w_k$ from\n", "$S$). This works because everything below $w_k$ together cannot reach $w_k$.\n", "\n", "This is the trapdoor. The legitimate recipient holds a superincreasing sequence\n", "$w_1, \\ldots, w_n$ as their **secret key** and decrypts in $O(n)$. The public\n", "key is a *disguised* version of the sequence that no longer looks\n", "superincreasing.\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "ch46-006", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:12.444866Z", "iopub.status.busy": "2026-05-12T08:46:12.444775Z", "iopub.status.idle": "2026-05-12T08:46:12.641706Z", "shell.execute_reply": "2026-05-12T08:46:12.641199Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Superincreasing sequence w = [2, 3, 8, 17, 31, 65, 130, 258]\n", "Plaintext bits x = [1, 0, 1, 1, 0, 0, 1, 0]\n", "Ciphertext sum S = 157\n", "Recovered bits x = [1, 0, 1, 1, 0, 0, 1, 0]\n" ] } ], "source": [ "import numpy as np\n", "\n", "def is_superincreasing(w):\n", " w = list(w)\n", " s = 0\n", " for wi in w:\n", " if wi <= s:\n", " return False\n", " s += wi\n", " return True\n", "\n", "def greedy_subset_sum(w, S):\n", " '''Solve subset-sum greedily for a superincreasing sequence.\n", "\n", " Returns the bit vector x in {0,1}^n with sum_i x_i*w[i] == S, or None.\n", " '''\n", " n = len(w)\n", " x = [0] * n\n", " remaining = S\n", " for k in range(n - 1, -1, -1):\n", " if w[k] <= remaining:\n", " x[k] = 1\n", " remaining -= w[k]\n", " return x if remaining == 0 else None\n", "\n", "\n", "# Demonstration: a superincreasing sequence, encryption-by-summing,\n", "# decryption-by-greedy.\n", "rng = np.random.default_rng(20260503)\n", "w = [2]\n", "for _ in range(7):\n", " w.append(int(sum(w) + rng.integers(1, 5)))\n", "print('Superincreasing sequence w =', w)\n", "assert is_superincreasing(w)\n", "\n", "x = [int(b) for b in '10110010']\n", "S = sum(xi * wi for xi, wi in zip(x, w))\n", "print('Plaintext bits x =', x)\n", "print('Ciphertext sum S =', S)\n", "x_recovered = greedy_subset_sum(w, S)\n", "print('Recovered bits x =', x_recovered)\n", "assert x_recovered == x\n" ] }, { "cell_type": "markdown", "id": "ch46-007", "metadata": {}, "source": [ "## 46.6 The Merkle–Hellman Trapdoor\n", "\n", "```{admonition} The Merkle–Hellman trick\n", ":class: important\n", "**Setup.** Pick a superincreasing sequence $w_1, \\ldots, w_n$ (the secret key).\n", "Pick a modulus $m > \\sum w_i$ and a multiplier $r$ coprime to $m$.\n", "\n", "**Public key.** Publish $a_i = r \\, w_i \\bmod m$ for $i = 1, \\ldots, n$. The\n", "sequence $a_1, \\ldots, a_n$ no longer looks superincreasing — it looks random\n", "modulo $m$.\n", "\n", "**Encryption.** A sender encodes a plaintext bit-vector $\\bx \\in \\{0,1\\}^n$\n", "as $S = \\sum_i x_i a_i$ (an ordinary integer, not modular).\n", "\n", "**Decryption.** The recipient computes $S' = r^{-1} S \\bmod m = \\sum_i x_i w_i\n", "\\bmod m$. Because $\\sum w_i < m$ and the actual $\\sum x_i w_i \\le \\sum w_i$\n", "fits below the modulus, $S'$ equals $\\sum x_i w_i$ as an integer. Now solve\n", "the *easy* superincreasing subset-sum to recover $\\bx$.\n", "```\n", "\n", "Notice how clean this is. The trapdoor — the multiplier-and-modulus\n", "disguise — is invertible if and only if you know $r$. To everyone else, the\n", "public sequence $(a_i)$ looks like a hard knapsack instance; only the\n", "recipient can convert it back to the easy one.\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "ch46-008", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:12.642951Z", "iopub.status.busy": "2026-05-12T08:46:12.642830Z", "iopub.status.idle": "2026-05-12T08:46:12.646545Z", "shell.execute_reply": "2026-05-12T08:46:12.646243Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Public key a = [335, 402, 102, 338, 140, 347, 761, 753]\n", "Secret key w = [5, 6, 18, 38, 68, 137, 275, 555]\n", " modulus m = 1104\n", " multipl. r = 67\n", "Ciphertext S = 2589\n", "Recovered bits = [1, 1, 0, 1, 0, 0, 1, 1]\n" ] } ], "source": [ "def modinv(a, m):\n", " '''Compute the modular inverse of a mod m using extended Euclid.'''\n", " g, x, _ = extended_gcd(a, m)\n", " if g != 1:\n", " raise ValueError(f'{a} has no inverse mod {m}')\n", " return x % m\n", "\n", "def extended_gcd(a, b):\n", " if b == 0:\n", " return a, 1, 0\n", " g, x1, y1 = extended_gcd(b, a % b)\n", " return g, y1, x1 - (a // b) * y1\n", "\n", "\n", "def merkle_hellman_keygen(n=8, seed=20260503):\n", " # `random.randrange` handles arbitrary-precision Python ints, so this\n", " # keygen works for any n (numpy's Generator caps at int64 ranges).\n", " import random as _r\n", " rnd = _r.Random(seed)\n", " # 1. Superincreasing secret sequence\n", " w = [rnd.randrange(2, 10)]\n", " for _ in range(n - 1):\n", " w.append(sum(w) + rnd.randrange(1, 10))\n", " # 2. Modulus m > sum(w_i), then a multiplier r coprime to m\n", " m = sum(w) + rnd.randrange(1, 100)\n", " while True:\n", " r = rnd.randrange(2, m)\n", " try:\n", " r_inv = modinv(r, m)\n", " break\n", " except ValueError:\n", " continue\n", " # 3. Public key a_i = r*w_i mod m\n", " a = [(r * wi) % m for wi in w]\n", " sk = {'w': w, 'm': m, 'r': r, 'r_inv': r_inv}\n", " pk = a\n", " return pk, sk\n", "\n", "def merkle_hellman_encrypt(pk, x):\n", " return sum(xi * ai for xi, ai in zip(x, pk))\n", "\n", "def merkle_hellman_decrypt(sk, S):\n", " Sp = (sk['r_inv'] * S) % sk['m']\n", " return greedy_subset_sum(sk['w'], Sp)\n", "\n", "\n", "pk, sk = merkle_hellman_keygen(n=8)\n", "print('Public key a =', pk)\n", "print('Secret key w =', sk['w'])\n", "print(' modulus m =', sk['m'])\n", "print(' multipl. r =', sk['r'])\n", "\n", "plaintext = [int(b) for b in '11010011']\n", "S = merkle_hellman_encrypt(pk, plaintext)\n", "print('Ciphertext S =', S)\n", "recovered = merkle_hellman_decrypt(sk, S)\n", "print('Recovered bits =', recovered)\n", "assert recovered == plaintext\n" ] }, { "cell_type": "markdown", "id": "ch46-009", "metadata": {}, "source": [ "### 46.6.1 Density and the W2 Lab Key\n", "\n", "The **density** of a knapsack instance $(a_1, \\ldots, a_n)$ is\n", "\n", "$$\n", "d \\;=\\; \\frac{n}{\\log_2 \\max_i a_i}.\n", "$$\n", "\n", "The Lagarias–Odlyzko (1985) attack and its Coster–Joux–LaMacchia–Odlyzko–Schnorr–\n", "Stern (1992) refinement break low-density instances ($d \\lesssim 0.94$) in\n", "polynomial time using lattice reduction. The cell below produces a low-density\n", "$n=32$ Merkle–Hellman public key suitable for the **W2 lab**: in W2 we will read\n", "this key back, build the Lagarias–Odlyzko lattice (Ex 40.4 of the upstream\n", "cryptanalysis chapter), and run LLL to recover the plaintext bit-vector.\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "ch46-010", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:12.647677Z", "iopub.status.busy": "2026-05-12T08:46:12.647602Z", "iopub.status.idle": "2026-05-12T08:46:12.651151Z", "shell.execute_reply": "2026-05-12T08:46:12.650854Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n = 8 max(a_i) ≈ 2^ 10.4 density = 0.767\n", "n = 16 max(a_i) ≈ 2^ 18.4 density = 0.869\n", "n = 32 max(a_i) ≈ 2^ 34.0 density = 0.942\n", "n = 64 max(a_i) ≈ 2^ 65.9 density = 0.971\n", "\n", "W2 lab key: n = 32, ~127-bit a_i, density = 0.250\n", "\n", "--- pk_w1.json (first 240 chars) ---\n", "{\"n\": 32, \"public_key\": [224387419562186596285440052009478462915, 288002407853184006134993028873468930260, 261862428319306777470369984933668012439, 138565005805237772219412842712369566393, 295867515989035635031290651886833907548, 2706524549 ...\n" ] } ], "source": [ "import math, json\n", "\n", "def density(public_key):\n", " return len(public_key) / math.log2(max(public_key))\n", "\n", "# Show how density falls as n grows under the default keygen.\n", "for n in (8, 16, 32, 64):\n", " pk_n, _ = merkle_hellman_keygen(n=n, seed=20260503 + n)\n", " print(f'n = {n:3d} max(a_i) ≈ 2^{math.log2(max(pk_n)):5.1f} density = {density(pk_n):.3f}')\n", "\n", "# Now build a deliberately low-density key for the W2 LLL lab: use a much larger\n", "# multiplier modulus so the public a_i become wide integers.\n", "def merkle_hellman_keygen_lowdensity(n=32, target_bits=128, seed=20260601):\n", " import random as _r\n", " rnd = _r.Random(seed)\n", " w = [rnd.randrange(2, 10)]\n", " for _ in range(n - 1):\n", " w.append(sum(w) + rnd.randrange(1, 10))\n", " m = (1 << target_bits) + rnd.randrange(1, 1 << 60)\n", " while True:\n", " r = rnd.randrange(2, m)\n", " try:\n", " r_inv = modinv(r, m); break\n", " except ValueError:\n", " continue\n", " a = [(r * wi) % m for wi in w]\n", " return a, {'w': w, 'm': m, 'r': r, 'r_inv': r_inv}\n", "\n", "pk_w1, sk_w1 = merkle_hellman_keygen_lowdensity(n=32, target_bits=128)\n", "print()\n", "print(f'W2 lab key: n = {len(pk_w1)}, ~{int(math.log2(max(pk_w1)))}-bit a_i, '\n", " f'density = {density(pk_w1):.3f}')\n", "\n", "# Encrypt a plaintext to hand off.\n", "plaintext_w1 = [int(b) for b in '11001010101100001100110010100111']\n", "S_w1 = merkle_hellman_encrypt(pk_w1, plaintext_w1)\n", "\n", "# Round-trip check before the lab handover.\n", "assert merkle_hellman_decrypt(sk_w1, S_w1) == plaintext_w1, 'self-decrypt failed'\n", "\n", "# Print a JSON blob ready to save as pk_w1.json (the W2 lab will read it).\n", "handover = {\n", " 'n': len(pk_w1),\n", " 'public_key': pk_w1,\n", " 'ciphertext': S_w1,\n", " 'density': density(pk_w1),\n", "}\n", "print()\n", "print('--- pk_w1.json (first 240 chars) ---')\n", "print(json.dumps(handover)[:240], '...')\n" ] }, { "cell_type": "markdown", "id": "ch46-011", "metadata": {}, "source": [ "## 46.7 Why Merkle–Hellman Broke\n", "\n", "The Merkle–Hellman cryptosystem was published in 1978 and broken by **Adi\n", "Shamir** in 1982 (published 1984). Shamir's polynomial-time attack does *not*\n", "solve the general NP-hard subset-sum problem — that remains hard. It exploits\n", "the fact that the public sequence is a *modular linear image* of a\n", "superincreasing sequence, and that this leaves a recoverable pattern in the\n", "continued-fraction expansion of $a_i / m$.\n", "\n", "A second attack, due to **Lagarias and Odlyzko** (1985), realised that\n", "**low-density** subset-sum instances — those where the number of bits in each\n", "$a_i$ is much larger than $n$ — can be solved by **lattice reduction**. Each\n", "such instance is converted to a lattice in which a short vector encodes the\n", "plaintext bit-vector $\\bx$, and LLL recovers it in polynomial time.\n", "\n", "Both attacks belong squarely in our W2 lecture: Shamir's attack illustrates the\n", "danger of *structured* trapdoors, and the Lagarias–Odlyzko attack is the first\n", "crypto-relevant application of LLL we will see (full treatment in Chapter 40\n", "of the upstream cryptanalysis book).\n", "\n", "```{admonition} Lesson for this course\n", ":class: tip\n", "NP-hardness of a problem is necessary but not sufficient for a public-key\n", "cryptosystem. The cryptosystem must use *random-looking* instances of the\n", "problem, not engineered ones with a hidden structure. Every PQC family we will\n", "study has had to prove this — typically through a worst-case-to-average-case\n", "reduction (Ajtai for lattices, Brakerski–Vaikuntanathan for LWE) or through\n", "two decades of public cryptanalytic effort (McEliece, SPHINCS+).\n", "```\n" ] }, { "cell_type": "markdown", "id": "ch46-012", "metadata": {}, "source": [ "## 46.8 Exercises\n", "\n", "---\n", "\n", "**Exercise 46.1 — Counting trapdoors.**\n", "\n", "For $n = 8$, count how many distinct superincreasing sequences with $w_1 \\in [2,9]$\n", "and $w_{k+1} \\in [\\sum_{i \\le k} w_i + 1, \\sum_{i \\le k} w_i + 10]$ exist. Estimate\n", "the entropy of the secret key for $n = 256$ under the same per-step uniform\n", "choice. Is it sufficient to resist exhaustive search? Why is \"exhaustive search of\n", "the secret key\" not the right threat model for a knapsack cryptosystem?\n", "\n", "---\n", "\n", "**Exercise 46.2 — Density of a knapsack.**\n", "\n", "The **density** of a knapsack instance $(a_1, \\ldots, a_n)$ is\n", "$d = n / \\log_2 (\\max_i a_i)$. Compute the density of the public key produced\n", "by `merkle_hellman_keygen(n=8)` and `merkle_hellman_keygen(n=64)`. The\n", "Lagarias–Odlyzko (1985) attack succeeds for densities below $\\approx 0.6463$;\n", "the Coster–Joux–LaMacchia–Odlyzko–Schnorr–Stern (1992) refinement raised the\n", "threshold to $\\approx 0.9408$. Are the default parameters in the notebook\n", "below or above each threshold?\n", "\n", "---\n", "\n", "**Exercise 46.3 — Implement Shamir's continued-fraction attack (sketch).**\n", "\n", "Read Shamir 1984 §3. Implement, on a small instance ($n = 5$), the step that\n", "extracts a candidate multiplier $r$ from the continued-fraction expansion of\n", "$a_1 / a_2$. You do not need the full attack; the goal is to see *why* the\n", "trapdoor leaks.\n", "\n", "---\n", "\n", "**Exercise 46.4 — Knapsack cryptosystem in modern wrapping.**\n", "\n", "Pretend the year is 2026 and you are pitching a \"post-quantum\" KEM based on\n", "subset-sum. Write a one-page memo (a) describing the parameters you would\n", "propose, (b) listing the two known attacks and their density requirements, and\n", "(c) estimating, by combining the attacks, what density would currently be\n", "considered safe. End with a recommendation: would you submit this to a NIST\n", "round 5 call?\n", "\n", "---\n", "\n", "**Exercise 46.5 (lab handover to W2) — Build the artefact you will break.**\n", "\n", "Generate a Merkle–Hellman public key with $n = 32$ and *low* density (modulus\n", "chosen so that each $a_i$ has roughly $4n = 128$ bits). Save the public key\n", "and a ciphertext to a JSON file `pk_w1.json` in your working directory.\n", "\n", "In the W2 lab you will read this file back, build the lattice from\n", "Lagarias–Odlyzko (the construction in Ex 40.4 of the upstream Ch 40), run LLL\n", "on it, and recover the plaintext bit-vector.\n", "\n", "```{admonition} Hint for picking the modulus\n", ":class: dropdown\n", "\n", "To produce roughly $b$-bit $a_i$ values, pick the modulus $m$ to be roughly\n", "$2^b$. The density is then $n/b$, so for $n = 32$ and density $\\approx 0.25$\n", "(safely in LLL-attackable territory) take $m \\approx 2^{128}$.\n", "```\n" ] }, { "cell_type": "markdown", "id": "ch46-013", "metadata": {}, "source": [ "## 46.9 Summary\n", "\n", "1. Quantum-resistant cryptography is needed *now*, not when a quantum computer\n", " appears, because of harvest-now-decrypt-later.\n", "2. Five public-key families are candidates: lattice, code, hash, multivariate,\n", " isogeny. Three have NIST standards (lattice + hash + code); two saw their\n", " flagship submissions broken in 2022.\n", "3. NP-hardness alone does not yield a public-key cryptosystem. Merkle–Hellman\n", " (1978) demonstrated this: subset-sum is NP-hard, but the trapdoor leaks\n", " structure that is exploitable in polynomial time (Shamir 1984;\n", " Lagarias–Odlyzko 1985 via LLL).\n", "4. The Lagarias–Odlyzko attack is the first crypto-relevant application of\n", " lattice reduction we meet — the formal LLL treatment is the W2 chapter\n", " (upstream Ch 40).\n", "5. Crypto-agility — the ability to swap algorithms cheaply — matters as much as\n", " any single algorithm choice.\n" ] }, { "cell_type": "markdown", "id": "ch46-014", "metadata": {}, "source": [ "## 46.10 References\n", "\n", "1. **Diffie, W. and Hellman, M. E.** (1976). *New Directions in Cryptography.*\n", " IEEE Trans. Information Theory **22**(6), 644–654.\n", "2. **Merkle, R. C. and Hellman, M. E.** (1978). *Hiding Information and\n", " Signatures in Trapdoor Knapsacks.* IEEE Trans. Information Theory **24**(5),\n", " 525–530.\n", "3. **Shamir, A.** (1984). *A Polynomial-Time Algorithm for Breaking the Basic\n", " Merkle–Hellman Cryptosystem.* IEEE Trans. Information Theory **30**(5),\n", " 699–704.\n", "4. **Lagarias, J. C. and Odlyzko, A. M.** (1985). *Solving Low-Density\n", " Subset Sum Problems.* J. ACM **32**(1), 229–246.\n", "5. **Coster, M. J., Joux, A., LaMacchia, B. A., Odlyzko, A. M., Schnorr, C.-P.,\n", " Stern, J.** (1992). *Improved Low-Density Subset Sum Algorithms.*\n", " Computational Complexity **2**, 111–128.\n", "6. **NIST** (2024). *FIPS 203 — Module-Lattice-Based Key-Encapsulation\n", " Mechanism Standard.* \n", "7. **NIST** (2024). *FIPS 204 — Module-Lattice-Based Digital Signature\n", " Standard.*\n", "8. **NIST** (2024). *FIPS 205 — Stateless Hash-Based Digital Signature\n", " Standard.*\n", "9. **NIST** (2025-03-11). *Public announcement: HQC selected as the fifth\n", " PQC standard.* .\n", "10. **NSA** (2024). *Commercial National Security Algorithm Suite 2.0\n", " (CNSA 2.0).* \n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.14.2" } }, "nbformat": 4, "nbformat_minor": 5 }