{ "cells": [ { "cell_type": "markdown", "id": "ex46-000", "metadata": {}, "source": [ "# Chapter 46 — Practical Exercises\n", "\n", "This sheet accompanies [Chapter 46 — *The Post-Quantum Landscape and the\n", "Knapsack Problem*](ch46_pqc_landscape.ipynb). Six exercises from one-liner\n", "to small research project.\n", "\n", "## How to use\n", "\n", "Each exercise has three parts:\n", "\n", "1. **Problem statement** — the goal, plus a difficulty marker (★ very easy\n", " to ★★★★★ research project) and a link to the chapter section that\n", " covers the theory.\n", "2. **Your turn** — a code cell with `TODO` gaps. Fill them in, run the cell,\n", " and check the assertion at the bottom.\n", "3. **Solution** — hidden by default. Click *\"Click to show\"* to reveal a\n", " fully-commented reference implementation that explains every step and\n", " links back to the chapter.\n", "\n", "The gaps deliberately point at concepts the chapter teaches; doing the\n", "exercises is a more durable way to learn the theory than re-reading the\n", "text.\n", "\n", "```{admonition} Working environment\n", ":class: tip\n", "All exercises run in pure Python with the standard library plus NumPy.\n", "Run `pip install numpy matplotlib` once if you have not already.\n", "```\n" ] }, { "cell_type": "markdown", "id": "ex46-001", "metadata": {}, "source": [ "## Exercise 46.E1 — ★ Validate a superincreasing sequence\n", "\n", "**Goal.** Write `is_superincreasing(w)` returning `True` iff\n", "$w_k > \\sum_{i sum(w_i for i < k) for every k >= 2.'''\n", " # TODO: walk through w accumulating a running sum and check each w_k.\n", " # If any element fails the condition, return False; otherwise True.\n", " raise NotImplementedError('your turn')\n", "\n", "\n", "# Tests. Uncomment and run.\n", "# assert is_superincreasing([2, 3, 8, 17, 31, 65, 130, 258])\n", "# assert not is_superincreasing([2, 3, 4]) # 4 == 2+3 fails strict >\n", "# assert not is_superincreasing([5, 3])\n", "# assert is_superincreasing([1]) # singleton trivially yes\n", "# print('E1 OK')\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "ex46-003", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:18.283684Z", "iopub.status.busy": "2026-05-12T08:46:18.283581Z", "iopub.status.idle": "2026-05-12T08:46:18.286307Z", "shell.execute_reply": "2026-05-12T08:46:18.285949Z" }, "tags": [ "hide-cell" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "E1 OK\n" ] } ], "source": [ "# Solution.\n", "#\n", "# We walk through the sequence with a running prefix sum. At step k we test\n", "# whether the current element strictly exceeds the sum of everything before it.\n", "#\n", "# Reference: §46.5 of the chapter defines the property. The greedy decoder\n", "# in the same section relies critically on this STRICT inequality -- if we had\n", "# w_k == sum_{i d~0.5\n", "PK_MED = [(1 << 12) - 1 - i * 137 for i in range(8)] # ~12-bit a_i -> d~0.67\n", "PK_HIGH = [3 + i for i in range(8)] # tiny a_i -> d ~ 2\n", "\n", "# print('low d =', density(PK_LOW), ' attackable =', lo_attackable(PK_LOW))\n", "# print('med d =', density(PK_MED), ' attackable =', lo_attackable(PK_MED))\n", "# print('high d =', density(PK_HIGH), ' attackable =', lo_attackable(PK_HIGH))\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "ex46-009", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:18.298776Z", "iopub.status.busy": "2026-05-12T08:46:18.298705Z", "iopub.status.idle": "2026-05-12T08:46:18.301147Z", "shell.execute_reply": "2026-05-12T08:46:18.300807Z" }, "tags": [ "hide-cell" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "low d = 0.5 attackable = True\n", "med d = 0.667 attackable = True\n", "high d = 2.0 attackable = False\n", "E3 OK\n" ] } ], "source": [ "# Solution.\n", "#\n", "# Density is just the bit budget per knapsack entry: n / log_2(max a_i).\n", "# Lagarias-Odlyzko 1985 proved an LLL-based attack succeeds for d < 0.6463;\n", "# Coster, Joux, LaMacchia, Odlyzko, Schnorr, Stern (1992) raised this to\n", "# d < 0.9408. See the chapter §46.7.\n", "#\n", "# Note we use ceil(log2) -- a power-of-two max would otherwise be off by one.\n", "\n", "def density(a):\n", " return len(a) / math.ceil(math.log2(max(a)))\n", "\n", "def lo_attackable(a, threshold=0.9408):\n", " return density(a) < threshold\n", "\n", "print('low d =', round(density(PK_LOW), 3), ' attackable =', lo_attackable(PK_LOW))\n", "print('med d =', round(density(PK_MED), 3), ' attackable =', lo_attackable(PK_MED))\n", "print('high d =', round(density(PK_HIGH), 3), ' attackable =', lo_attackable(PK_HIGH))\n", "print('E3 OK')\n" ] }, { "cell_type": "markdown", "id": "ex46-010", "metadata": {}, "source": [ "## Exercise 46.E4 — ★★★ Brute force vs greedy: timing comparison\n", "\n", "**Goal.** Implement an exhaustive $O(2^n)$ subset-sum solver and time it\n", "against the greedy decoder on superincreasing instances of growing $n$.\n", "\n", "**Theory.** [§46.4 — The subset-sum / 0-1 knapsack problem](ch46_pqc_landscape.ipynb#the-subset-sum-0-1-knapsack-problem).\n", "\n", "**Why this matters.** Convince yourself, with concrete timings, that the\n", "NP-hard generic problem and the $O(n)$ trapdoored problem really are in\n", "totally different complexity classes.\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "ex46-011", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:18.302216Z", "iopub.status.busy": "2026-05-12T08:46:18.302143Z", "iopub.status.idle": "2026-05-12T08:46:18.304504Z", "shell.execute_reply": "2026-05-12T08:46:18.304160Z" } }, "outputs": [], "source": [ "import time, itertools\n", "\n", "def brute_force_subset_sum(a, S):\n", " '''Try every subset; return the bit-vector matching S, or None.'''\n", " # TODO: enumerate all 2^n bit-vectors and pick the first whose dot product\n", " # with `a` equals S. itertools.product([0,1], repeat=n) is one way.\n", " raise NotImplementedError('your turn')\n", "\n", "\n", "def greedy_subset_sum(w, S):\n", " bits = [0] * len(w)\n", " rem = S\n", " for k in range(len(w) - 1, -1, -1):\n", " if w[k] <= rem:\n", " bits[k] = 1\n", " rem -= w[k]\n", " return bits if rem == 0 else None\n", "\n", "\n", "# Generate a superincreasing sequence and time both solvers for growing n.\n", "def superincr(n):\n", " w = [2]\n", " while len(w) < n:\n", " w.append(sum(w) + 1)\n", " return w\n", "\n", "# for n in (8, 12, 16, 20):\n", "# w = superincr(n)\n", "# S = sum(w[:n:2]) # take the even-indexed weights\n", "# t0 = time.time(); b1 = brute_force_subset_sum(w, S); tb = time.time() - t0\n", "# t0 = time.time(); b2 = greedy_subset_sum(w, S); tg = time.time() - t0\n", "# print(f'n={n:2d} brute = {tb*1000:7.1f} ms greedy = {tg*1000:6.3f} ms match={b1==b2}')\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "ex46-012", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:18.305620Z", "iopub.status.busy": "2026-05-12T08:46:18.305551Z", "iopub.status.idle": "2026-05-12T08:46:18.844104Z", "shell.execute_reply": "2026-05-12T08:46:18.843785Z" }, "tags": [ "hide-cell" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n= 8 brute = 0.1 ms greedy = 0.003 ms match=True\n", "n=12 brute = 1.7 ms greedy = 0.002 ms match=True\n", "n=16 brute = 29.2 ms greedy = 0.005 ms match=True\n" ] }, { "name": "stdout", "output_type": "stream", "text": [ "n=20 brute = 504.5 ms greedy = 0.011 ms match=True\n", "E4 OK\n" ] } ], "source": [ "# Solution.\n", "#\n", "# Brute force enumerates all 2^n subsets. itertools.product is the cleanest\n", "# implementation; for serious benchmarking you would prefer a meet-in-the-\n", "# middle algorithm (Schroeppel-Shamir 1981) which runs in O(2^{n/2}) time and\n", "# space.\n", "#\n", "# Empirically you should see brute-force time roughly DOUBLE per +1 in n,\n", "# while greedy stays essentially flat -- the textbook exponential vs linear\n", "# divide. This is exactly the gap that motivates the trapdoor-knapsack idea\n", "# (chapter §46.6) and exactly what makes that idea fragile (§46.7).\n", "\n", "def brute_force_subset_sum(a, S):\n", " n = len(a)\n", " for bits in itertools.product([0, 1], repeat=n):\n", " if sum(b * ai for b, ai in zip(bits, a)) == S:\n", " return list(bits)\n", " return None\n", "\n", "for n in (8, 12, 16, 20):\n", " w = superincr(n)\n", " S = sum(w[:n:2])\n", " t0 = time.time(); b1 = brute_force_subset_sum(w, S); tb = time.time() - t0\n", " t0 = time.time(); b2 = greedy_subset_sum(w, S); tg = time.time() - t0\n", " print(f'n={n:2d} brute = {tb*1000:7.1f} ms greedy = {tg*1000:6.3f} ms match={b1==b2}')\n", "\n", "print('E4 OK')\n" ] }, { "cell_type": "markdown", "id": "ex46-013", "metadata": {}, "source": [ "## Exercise 46.E5 — ★★★★ Build the Lagarias–Odlyzko lattice + a tiny LLL\n", "\n", "**Goal.** Construct the Lagarias–Odlyzko (LO) lattice for a given\n", "public-key / ciphertext pair, run a NumPy implementation of LLL on it,\n", "and decode the bit-vector from the resulting short vector.\n", "\n", "**Theory.** [§46.7 — Why Merkle–Hellman broke](ch46_pqc_landscape.ipynb#why-merklehellman-broke)\n", "and the *upstream* cryptanalysis chapter Ch 40 (§40.3–40.7) for the LLL\n", "algorithm itself.\n", "\n", "**Why this matters.** This is the W2 lab in miniature. The LO lattice is\n", "the bridge from \"knapsack as a hard problem\" to \"LLL as a near-universal\n", "cryptanalytic hammer\".\n" ] }, { "cell_type": "code", "execution_count": 9, "id": "ex46-014", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:18.845667Z", "iopub.status.busy": "2026-05-12T08:46:18.845565Z", "iopub.status.idle": "2026-05-12T08:46:18.869799Z", "shell.execute_reply": "2026-05-12T08:46:18.869304Z" } }, "outputs": [], "source": [ "import numpy as np\n", "\n", "def build_LO_lattice(a, S):\n", " '''Lagarias-Odlyzko lattice: returns an (n+1) x (n+1) integer basis B.\n", "\n", " Rows are the basis vectors; the last column carries the sum constraint.\n", " A short vector with last coord 0 has front entries +/- 1 encoding bits.\n", " '''\n", " n = len(a)\n", " # TODO: build B with the following pattern (rows are vectors):\n", " # for i in 0..n-1: row i = 2 * e_i + 2 * a_i * e_n\n", " # for i = n : row n = 1_n + 2 * S * e_n\n", " # Return as a 2D NumPy array with dtype=object (so coefficients can be big ints).\n", " raise NotImplementedError('your turn')\n", "\n", "\n", "def lll(B, delta=0.75):\n", " '''Plain LLL on integer-row basis B (NumPy 2D array). Returns reduced B.'''\n", " B = np.array(B, dtype=object)\n", " n = B.shape[0]\n", " def gso():\n", " Bf = B.astype(float)\n", " Q = np.zeros_like(Bf)\n", " mu = np.zeros((n, n))\n", " for i in range(n):\n", " Q[i] = Bf[i].copy()\n", " for j in range(i):\n", " denom = float(Q[j] @ Q[j])\n", " mu[i, j] = float(Bf[i] @ Q[j]) / denom if denom else 0.0\n", " Q[i] -= mu[i, j] * Q[j]\n", " return Q, mu\n", " def size_reduce(k, mu):\n", " for j in range(k - 1, -1, -1):\n", " q = round(mu[k, j])\n", " if q:\n", " B[k] = B[k] - q * B[j]\n", " mu[k, :j+1] -= q * mu[j, :j+1]\n", " mu[k, j] -= q\n", " Q, mu = gso()\n", " k = 1\n", " iters = 0\n", " while k < n and iters < 1000 * n:\n", " size_reduce(k, mu)\n", " if (Q[k] @ Q[k]) >= (delta - mu[k, k-1]**2) * (Q[k-1] @ Q[k-1]):\n", " k += 1\n", " else:\n", " B[[k, k-1]] = B[[k-1, k]]\n", " Q, mu = gso()\n", " k = max(k - 1, 1)\n", " iters += 1\n", " return B\n", "\n", "\n", "def bits_from_short_vec(v, n):\n", " out = []\n", " for x in v[:n]:\n", " if int(x) == 1: out.append(0)\n", " elif int(x) == -1: out.append(1)\n", " else: return None\n", " return out\n", "\n", "\n", "def attack_merkle_hellman(a, S):\n", " B = build_LO_lattice(a, S)\n", " Bred = lll(B)\n", " for row in Bred:\n", " if int(row[-1]) != 0: continue\n", " b = bits_from_short_vec(row, len(a))\n", " if b is not None: return b\n", " bneg = bits_from_short_vec(-row, len(a))\n", " if bneg is not None: return bneg\n", " return None\n", "\n", "\n", "# Build a low-density instance and break it.\n", "# from random import Random\n", "# rnd = Random(42)\n", "# n = 10\n", "# w = [rnd.randrange(2, 10)]\n", "# for _ in range(n - 1):\n", "# w.append(sum(w) + rnd.randrange(1, 10))\n", "# m = (1 << 32) + rnd.randrange(1, 1024); r = 17 # tiny example\n", "# while True:\n", "# try: r_inv = pow(r, -1, m); break\n", "# except ValueError: r += 2\n", "# pk = [(r * wi) % m for wi in w]\n", "# bits = [rnd.randrange(2) for _ in range(n)]\n", "# S = sum(b * ai for b, ai in zip(bits, pk))\n", "# rec = attack_merkle_hellman(pk, S)\n", "# print('density =', n / max(pk).bit_length())\n", "# print('truth =', bits)\n", "# print('recovered =', rec)\n", "# assert rec == bits\n", "# print('E5 OK')\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "ex46-015", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:18.870911Z", "iopub.status.busy": "2026-05-12T08:46:18.870829Z", "iopub.status.idle": "2026-05-12T08:46:18.878179Z", "shell.execute_reply": "2026-05-12T08:46:18.877848Z" }, "tags": [ "hide-cell" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "density = 0.667\n", "truth = [0, 0, 0, 0, 0, 0, 1, 0, 1, 1]\n", "recovered = [0, 0, 0, 0, 0, 0, 1, 0, 1, 1]\n", "E5 OK\n" ] } ], "source": [ "# Solution.\n", "#\n", "# The lattice we build is the standard Lagarias-Odlyzko construction (1985):\n", "#\n", "# b_i (i" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "E6 OK\n" ] } ], "source": [ "# Solution sketch.\n", "#\n", "# The dominant subtlety is computing the modulus to land at a target density.\n", "# For an n-element key with d = n / log2(max(a_i)) and max(a_i) ~ m, we want\n", "# m ~ 2^(n/d). But m must also exceed sum(w); we take m = max(2^(n/d), sum(w))\n", "# plus a small random offset.\n", "#\n", "# Plotting matplotlib in this notebook requires `pip install matplotlib`.\n", "\n", "import math\n", "import matplotlib.pyplot as plt # noqa: only used in the solution\n", "\n", "def random_mh_instance(n, density_target, rnd):\n", " # superincreasing secret w\n", " w = [rnd.randrange(2, 10)]\n", " while len(w) < n:\n", " w.append(sum(w) + rnd.randrange(1, 10))\n", " target_max_log = max(int(round(n / density_target)), int(math.log2(sum(w))) + 1)\n", " m = max(sum(w) + rnd.randrange(1, 100), 1 << target_max_log)\n", " while True:\n", " r = rnd.randrange(2, m)\n", " if math.gcd(r, m) == 1: break\n", " pk = [(r * wi) % m for wi in w]\n", " bits = [rnd.randrange(2) for _ in range(n)]\n", " S = sum(b * ai for b, ai in zip(bits, pk))\n", " return pk, S, bits\n", "\n", "def success_rate(n, d, T, rnd):\n", " wins = 0\n", " for _ in range(T):\n", " pk, S, bits = random_mh_instance(n, d, rnd)\n", " rec = attack_merkle_hellman(pk, S)\n", " if rec == bits:\n", " wins += 1\n", " return wins / T\n", "\n", "# Reduce T at higher n for runtime.\n", "n = 10\n", "T = 30\n", "ds = [0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]\n", "rnd = Random(2026)\n", "rates = [success_rate(n, d, T, rnd) for d in ds]\n", "for d, p in zip(ds, rates):\n", " print(f'd = {d:.2f} success {int(p*T)}/{T} = {p:.0%}')\n", "\n", "# Plot.\n", "fig, ax = plt.subplots(figsize=(6, 3.2))\n", "ax.plot(ds, rates, marker='o', color='#4f46e5')\n", "ax.axvline(0.9408, color='#dc2626', linestyle='--', label='Coster et al. 1992 threshold')\n", "ax.set_xlabel('density d')\n", "ax.set_ylabel(f'LLL recovery rate (n={n}, T={T})')\n", "ax.set_ylim(-0.05, 1.05); ax.grid(True, alpha=0.3); ax.legend()\n", "ax.set_title('Lagarias-Odlyzko attack success vs. knapsack density')\n", "plt.tight_layout()\n", "plt.show()\n", "\n", "print('E6 OK')\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 }