{ "cells": [ { "cell_type": "markdown", "id": "ch48-000", "metadata": {}, "source": [ "# Chapter 48: NTRU, Multivariate, and Isogeny Cryptography\n" ] }, { "cell_type": "markdown", "id": "ch48-001", "metadata": {}, "source": [ "## 48.1 Three Minority Families\n", "\n", "ML-KEM and ML-DSA dominate the deployed post-quantum landscape because they\n", "are fast, have moderate sizes, and rest on the well-understood Module-LWE\n", "problem. But three other families have important roles:\n", "\n", "- **NTRU** is the **oldest practical lattice-based** scheme (1996). It predates\n", " LWE by nearly a decade and uses a *structured* lattice over a polynomial\n", " ring. NTRU was a NIST round-3 finalist; the standardised Falcon (FIPS 206\n", " draft) reuses NTRU lattices for its short-Gaussian sampler. NTRU is also\n", " the basis of `kyber.NTRU` mode in many proprietary deployments.\n", "- **Multivariate** cryptography (UOV, Rainbow, HFE, ...) is based on the\n", " difficulty of solving systems of multivariate polynomial equations over a\n", " finite field. Rainbow was a round-3 finalist for digital signatures, broken\n", " by Beullens in 2022; UOV continues as a round-4 candidate.\n", "- **Isogeny-based** cryptography uses walks in the supersingular isogeny graph.\n", " SIDH/SIKE was a round-4 alternate candidate for KEMs, broken by Castryck\n", " and Decru in 2022. CSIDH and SQIsign continue as research candidates with\n", " excellent key/ciphertext sizes (often the smallest in the PQC space).\n", "\n", "This chapter visits each family briefly, with enough mathematics to understand\n", "the construction and enough code to play with a toy version. The main\n", "pedagogical purpose is to (a) round out your view of PQC beyond the dominant\n", "lattice family, and (b) examine *why* Rainbow and SIDH broke — the failure\n", "analyses are some of the most interesting cryptanalysis of the past five\n", "years.\n" ] }, { "cell_type": "markdown", "id": "ch48-002", "metadata": {}, "source": [ "## 48.2 NTRU: The First Practical Post-Quantum Public-Key System\n", "\n", "```{admonition} The NTRU ring\n", ":class: important\n", "Pick parameters $(N, p, q)$ where $N$ is prime, $p$ and $q$ are coprime moduli\n", "with $p \\ll q$ (typically $p = 3$, $q = 2048$ or 4096), and $N$ is chosen so\n", "that $x^N - 1$ has good factorisation behaviour. Work in the polynomial ring\n", "\n", "$$\n", "R = \\Z[x] / (x^N - 1).\n", "$$\n", "\n", "Polynomial multiplication in $R$ corresponds to **cyclic convolution** of\n", "coefficient vectors. Reduction mod $q$ produces $R_q = R / qR$.\n", "```\n", "\n", "```{admonition} NTRU keygen\n", ":class: important\n", "**Secret key.** Sample two short polynomials $f, g \\in R$ with small ternary\n", "coefficients in $\\{-1, 0, 1\\}$, with $f$ invertible modulo both $p$ and $q$.\n", "Compute $F_p = f^{-1} \\in R_p$ and $F_q = f^{-1} \\in R_q$.\n", "\n", "**Public key.** $h = p \\cdot F_q \\cdot g \\pmod{q}$.\n", "\n", "The public key $h$ is a polynomial that *looks random* in $R_q$.\n", "```\n", "\n", "```{admonition} NTRU encrypt / decrypt\n", ":class: important\n", "**Encrypt** plaintext $m \\in R_p$ (small ternary) by sampling a small ternary\n", "$r \\in R$ and computing $c = h \\cdot r + m \\pmod{q}$.\n", "\n", "**Decrypt** by computing $a = f \\cdot c \\pmod{q}$, then reducing $a$ mod $p$.\n", "Because $f \\cdot c = p \\cdot g \\cdot r + f \\cdot m \\pmod{q}$ and the noise term\n", "$p \\cdot g \\cdot r + f \\cdot m$ has small coefficients, reducing $a$ to the\n", "*centred* representatives in $(-q/2, q/2]$ recovers $a$ exactly *as an\n", "integer polynomial*. Then $a \\bmod p = f \\cdot m \\bmod p$, and multiplying by\n", "$F_p$ recovers $m$.\n", "```\n", "\n", "The security of NTRU rests on the difficulty of finding the short pair $(f, g)$\n", "given $h$. This is a structured-lattice problem (the **NTRU lattice**) and\n", "is the cousin of the Ring-LWE problem you saw in W3. The structured nature of\n", "the lattice gives faster operations than vanilla LWE but, in principle, also\n", "more attack surface — a recurring tension in lattice-based design.\n", "\n", "```{admonition} Why NTRU still matters\n", ":class: tip\n", "- **Falcon** (draft FIPS 206) uses the NTRU lattice as the support for its\n", " Gaussian-sampler-based signature scheme; understanding NTRU is the first\n", " step to understanding Falcon.\n", "- Several **homomorphic-encryption** schemes (NTRU-based GSW variants, FHE\n", " bootstrapping) reuse the NTRU ring for its computational advantages.\n", "- NTRU-Prime variants (\"Streamlined NTRU Prime\", \"NTRU LPRime\") were NIST\n", " round-3 finalists alternative to Kyber, with different parameter and\n", " ring choices intended to harden against algebraic attacks.\n", "```\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "ch48-003", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:16.252856Z", "iopub.status.busy": "2026-05-12T08:46:16.252775Z", "iopub.status.idle": "2026-05-12T08:46:16.298114Z", "shell.execute_reply": "2026-05-12T08:46:16.297735Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "f = [1, -1, 1, 1, -1, 0, 1, 0, 0, 0, -1]\n", "g = [0, 0, -1, 0, 1, 0, 0, 1, -1, -1, 1]\n", "F_p = [1, 0, 2, 2, 2, 2, 0, 1, 0, 1, 2]\n", "F_q = [7, 10, 24, 24, 27, 22, 8, 20, 16, 23, 6]\n", "h = [20, 15, 28, 8, 10, 5, 14, 19, 24, 14, 29]\n", "c = [1, 13, 28, 23, 8, 12, 6, 26, 3, 15, 20]\n", "m_recovered = [-1, 0, 0, 0, 0, 1, 0, 1, 0, 0, -1]\n", "Match m : True\n" ] } ], "source": [ "import numpy as np\n", "\n", "# Toy NTRU. Choose parameters small enough to inspect by hand: N=11, p=3, q=31.\n", "# Both moduli are prime, so polynomial inversion in Z_mod[x] is well-defined.\n", "# The point is correctness of the algebra, not security.\n", "\n", "N, P, Q = 11, 3, 31\n", "\n", "\n", "def poly_mul_cyclic(a, b, n=N):\n", " '''Multiply two polynomials in Z[x]/(x^n - 1) (cyclic convolution).'''\n", " c = np.zeros(n, dtype=np.int64)\n", " for i in range(n):\n", " for j in range(n):\n", " c[(i + j) % n] += int(a[i]) * int(b[j])\n", " return c\n", "\n", "def poly_mod(a, m):\n", " return ((a % m) + m) % m\n", "\n", "def poly_centred(a, m):\n", " '''Reduce a mod m and lift to centred representatives in (-m/2, m/2].'''\n", " a = poly_mod(a, m)\n", " return np.where(a > m // 2, a - m, a)\n", "\n", "\n", "# --- Pure-Python polynomial extended-GCD over Z_p[x] for prime p. ---\n", "def _strip(p):\n", " while len(p) > 1 and p[-1] == 0:\n", " p.pop()\n", " return p\n", "\n", "def _pmul(a, b, m):\n", " r = [0] * (len(a) + len(b) - 1)\n", " for i, ai in enumerate(a):\n", " if ai:\n", " for j, bj in enumerate(b):\n", " r[i + j] = (r[i + j] + ai * bj) % m\n", " return _strip(r)\n", "\n", "def _psub(a, b, m):\n", " r = [0] * max(len(a), len(b))\n", " for i, c in enumerate(a):\n", " r[i] = (r[i] + c) % m\n", " for i, c in enumerate(b):\n", " r[i] = (r[i] - c) % m\n", " return _strip(r)\n", "\n", "def _intinv(a, m):\n", " a %= m\n", " if a == 0:\n", " return None\n", " g, x, _ = _ext_int(a, m)\n", " return x % m if g == 1 else None\n", "\n", "def _ext_int(a, b):\n", " if b == 0:\n", " return a, 1, 0\n", " g, x1, y1 = _ext_int(b, a % b)\n", " return g, y1, x1 - (a // b) * y1\n", "\n", "def _pdivmod(a, b, m):\n", " a = list(a); b = _strip(list(b))\n", " deg_a, deg_b = len(a) - 1, len(b) - 1\n", " if deg_a < deg_b:\n", " return [0], a\n", " inv_lc = _intinv(b[-1], m)\n", " q = [0] * (deg_a - deg_b + 1)\n", " while len(a) - 1 >= deg_b and any(c % m for c in a):\n", " d = len(a) - 1 - deg_b\n", " coef = (a[-1] * inv_lc) % m\n", " q[d] = coef\n", " for i, bi in enumerate(b):\n", " a[d + i] = (a[d + i] - coef * bi) % m\n", " a = _strip(a)\n", " if len(a) - 1 < deg_b:\n", " break\n", " return q, a\n", "\n", "def poly_inv(f_arr, mod):\n", " '''Inverse of f in Z_mod[x] / (x^N - 1) via extended Euclidean. Mod must be prime.\n", "\n", " Returns a length-N NumPy array, or None if f is not invertible.\n", " '''\n", " f = [int(c) % mod for c in f_arr]\n", " while len(f) and f[-1] == 0:\n", " f.pop()\n", " if not f:\n", " return None\n", " g = [(-1) % mod] + [0] * (N - 1) + [1] # x^N - 1\n", " r0, r1 = list(g), list(f)\n", " s0, s1 = [0], [1]\n", " while any(c % mod for c in r1):\n", " q, r2 = _pdivmod(r0, r1, mod)\n", " s2 = _psub(s0, _pmul(q, s1, mod), mod)\n", " r0, r1 = r1, r2\n", " s0, s1 = s1, s2\n", " if len(r0) != 1 or r0[0] == 0:\n", " return None\n", " inv_lead = _intinv(r0[0], mod)\n", " if inv_lead is None:\n", " return None\n", " out = [(c * inv_lead) % mod for c in s0]\n", " out += [0] * (N - len(out))\n", " return np.array(out[:N], dtype=np.int64)\n", "\n", "\n", "# Pick small ternary f, g until f is invertible mod both p and q.\n", "rng = np.random.default_rng(20260503)\n", "def sample_ternary(n, n_plus, n_minus):\n", " v = np.array([1] * n_plus + [-1] * n_minus + [0] * (n - n_plus - n_minus))\n", " rng.shuffle(v)\n", " return v\n", "\n", "for _ in range(2000):\n", " f = sample_ternary(N, 4, 3)\n", " g = sample_ternary(N, 3, 3)\n", " Fp = poly_inv(f, P)\n", " Fq = poly_inv(f, Q)\n", " if Fp is not None and Fq is not None:\n", " break\n", "else:\n", " raise RuntimeError('Failed to find an invertible f after 2000 tries')\n", "\n", "print('f =', f.tolist())\n", "print('g =', g.tolist())\n", "print('F_p =', Fp.tolist())\n", "print('F_q =', Fq.tolist())\n", "\n", "# Public key h = p * F_q * g mod q\n", "h = poly_mod(P * poly_mul_cyclic(Fq, g), Q)\n", "print('h =', h.tolist())\n", "\n", "# Encrypt a small ternary message m with random small ternary r.\n", "m = sample_ternary(N, 2, 2)\n", "r = sample_ternary(N, 3, 3)\n", "c = poly_mod(poly_mul_cyclic(h, r) + m, Q)\n", "print('c =', c.tolist())\n", "\n", "# Decrypt: a = f*c mod q (centred), then reduce mod p, then multiply by F_p.\n", "a = poly_centred(poly_mul_cyclic(f, c), Q)\n", "a_mod_p = poly_mod(a, P)\n", "m_recovered = poly_mod(poly_mul_cyclic(Fp, a_mod_p), P)\n", "m_recovered = poly_centred(m_recovered, P)\n", "print('m_recovered =', m_recovered.tolist())\n", "print('Match m :', np.array_equal(m_recovered, m))\n" ] }, { "cell_type": "markdown", "id": "ch48-004", "metadata": {}, "source": [ "## 48.3 NTRU-Prime Variants\n", "\n", "The **NTRU-Prime** family (Bernstein, Brumley, Chuengsatiansup, Lange, van Vredendaal,\n", "2017) was a round-3 NIST finalist. It addresses two perceived weaknesses of classical\n", "NTRU:\n", "\n", "- **Streamlined NTRU Prime** picks $R = (\\Z/q\\Z)[x]/(x^p - x - 1)$ where $p$ is prime\n", " and $x^p - x - 1$ is irreducible, removing the cyclotomic structure that some\n", " algebraic attacks exploit.\n", "- **NTRU LPRime** moves to a $\\Z[x]/(x^p - x - 1)$ structure but uses an LPR-style\n", " \"Learning Parity with Rounding\" formulation rather than NTRU-style.\n", "\n", "Both variants ultimately lost to Kyber (Module-LWE) for the FIPS 203 standardisation,\n", "but remain widely studied for their conservative algebraic structure. The parameter\n", "choice \"no cyclotomic, no power-of-two $N$\" is the design lesson worth remembering.\n" ] }, { "cell_type": "markdown", "id": "ch48-005", "metadata": {}, "source": [ "## 48.4 Multivariate Cryptography in One Definition\n", "\n", "```{admonition} The MQ problem\n", ":class: important\n", "Let $\\F_q$ be a finite field, $n$ the number of variables, $m$ the number of\n", "equations. Given a system of $m$ multivariate quadratic polynomials\n", "$p_1(x_1, \\ldots, x_n), \\ldots, p_m(x_1, \\ldots, x_n) \\in \\F_q[x_1, \\ldots, x_n]$,\n", "the **MQ problem** is to find $\\bx \\in \\F_q^n$ such that\n", "$p_i(\\bx) = 0$ for every $i = 1, \\ldots, m$.\n", "```\n", "\n", "The MQ problem is NP-hard. The trick of multivariate cryptography is to build a\n", "trapdoor: a *secret* system $\\mathcal{F}$ of polynomials that is easy to invert,\n", "hidden behind two random affine bijections. The composition $\\mathcal{P} = T \\circ\n", "\\mathcal{F} \\circ S$ looks like a generic random MQ system — until you know\n", "$T, S$ and the special structure of $\\mathcal{F}$.\n", "\n", "The exemplar is **HFE** (Hidden Field Equations, Patarin 1996), where\n", "$\\mathcal{F}$ is a univariate polynomial over a large extension field\n", "$\\F_{q^n}$ that happens to be invertible because of its degree. Its\n", "descendants include UOV and Rainbow.\n" ] }, { "cell_type": "markdown", "id": "ch48-006", "metadata": {}, "source": [ "## 48.5 Oil and Vinegar: UOV\n", "\n", "The **Unbalanced Oil and Vinegar** (UOV) signature scheme (Patarin 1997;\n", "Kipnis–Patarin–Goubin 1999) splits the variables into two groups:\n", "\n", "- **Vinegar variables** $v_1, \\ldots, v_v$.\n", "- **Oil variables** $o_1, \\ldots, o_o$.\n", "\n", "Each *central* polynomial $f_k$ is a quadratic that is **affine in the oil\n", "variables once the vinegar variables are fixed**. Up to (optional) linear and\n", "constant terms it has the form\n", "\n", "$$\n", "f_k(\\bv, \\bo) \\;=\\; \\sum_{i,j} \\alpha_{kij}^{vv}\\, v_i v_j\n", " \\;+\\; \\sum_{i,j} \\alpha_{kij}^{vo}\\, v_i o_j\n", " \\;+\\; \\text{(linear / constant terms)},\n", "$$\n", "\n", "with the **defining property** that there are no $o \\cdot o$ terms. So once\n", "$\\bv$ is fixed, the system is linear in $\\bo$. To **sign** a hash $\\bm \\in \\F_q^o$:\n", "\n", "1. Pick random vinegar values $\\bv \\in \\F_q^v$.\n", "2. The system $f_k(\\bv, \\bo) = m_k$ becomes **linear** in $\\bo$. Solve it.\n", "3. Apply the secret affine bijection $S$ to recover the signature.\n", "\n", "The public key is the composition with secret affine maps that hide the\n", "oil-vinegar split. UOV is *unbalanced* in the sense that the number of\n", "vinegar variables is typically several times the number of oil variables\n", "to defeat the **rank attack** of Kipnis and Shamir (1998).\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "ch48-007", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:16.299401Z", "iopub.status.busy": "2026-05-12T08:46:16.299277Z", "iopub.status.idle": "2026-05-12T08:46:16.304924Z", "shell.execute_reply": "2026-05-12T08:46:16.304598Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Target hash digits over GF(31): [12, 11, 3, 15]\n", "Signature x = [9, 18, 17, 18, 24, 11, 17, 0, 13, 5]\n", "Verifies = True\n" ] } ], "source": [ "# Toy UOV over GF(31) with v=6 vinegar, o=4 oil variables. The point is to\n", "# see signing succeed (vinegar -> system linear in oil -> solve), not security.\n", "import hashlib, numpy as np\n", "\n", "Q_UOV, V, O = 31, 6, 4\n", "N_VARS = V + O\n", "\n", "\n", "def _gf_inv(a, q):\n", " return pow(int(a) % q, q - 2, q)\n", "\n", "def _gauss(M, b, q):\n", " '''Solve M @ x = b in GF(q) for square M. Returns x or None if singular.'''\n", " n = len(b)\n", " A = [list(row) + [bi] for row, bi in zip(M, b)]\n", " for c in range(n):\n", " # find pivot\n", " piv = next((r for r in range(c, n) if A[r][c] % q != 0), None)\n", " if piv is None:\n", " return None\n", " A[c], A[piv] = A[piv], A[c]\n", " inv = _gf_inv(A[c][c], q)\n", " A[c] = [(x * inv) % q for x in A[c]]\n", " for r in range(n):\n", " if r != c and A[r][c] % q != 0:\n", " f = A[r][c]\n", " A[r] = [(A[r][k] - f * A[c][k]) % q for k in range(n + 1)]\n", " return [row[-1] % q for row in A]\n", "\n", "\n", "def uov_keygen(seed=20260601):\n", " '''Sample o central polynomials f_k that are quadratic in (vinegar, oil)\n", " but contain no oil*oil terms. Public key = composition with secret S.'''\n", " rng = np.random.default_rng(seed)\n", " # Each f_k is stored as: alpha[k] (V x V vinegar*vinegar matrix)\n", " # beta[k] (V x O vinegar*oil matrix)\n", " # gamma[k] (O linear-in-oil)\n", " # delta[k] (V linear-in-vinegar) ... here we drop linear/const for brevity\n", " alpha = rng.integers(0, Q_UOV, size=(O, V, V)).tolist()\n", " beta = rng.integers(0, Q_UOV, size=(O, V, O)).tolist()\n", " # Secret affine bijection S on the input variables (toy: identity on vinegar, random invertible on oil).\n", " while True:\n", " S = rng.integers(0, Q_UOV, size=(N_VARS, N_VARS)).tolist()\n", " # Force the upper-left V*V block to be identity to keep the demo simple.\n", " for i in range(V):\n", " for j in range(N_VARS):\n", " S[i][j] = (1 if i == j else 0)\n", " # Test invertibility of S.\n", " if _gauss([list(row) for row in S],\n", " [(1 if i == 0 else 0) for i in range(N_VARS)], Q_UOV) is not None:\n", " break\n", " sk = (alpha, beta, S)\n", " return sk\n", "\n", "def central_eval(alpha_k, beta_k, vine, oil):\n", " '''Evaluate one central polynomial f_k(vinegar, oil).'''\n", " val = 0\n", " for i in range(V):\n", " for j in range(V):\n", " val = (val + alpha_k[i][j] * vine[i] * vine[j]) % Q_UOV\n", " for j in range(O):\n", " val = (val + beta_k[i][j] * vine[i] * oil[j]) % Q_UOV\n", " return val % Q_UOV\n", "\n", "def uov_sign(sk, msg_hash, max_attempts=20):\n", " '''Find x with f_k(x) = msg_hash[k] for all k. Returns x in GF(Q)^N or None.'''\n", " alpha, beta, S = sk\n", " rng = np.random.default_rng(int.from_bytes(hashlib.sha256(bytes(msg_hash)).digest()[:4], 'big'))\n", " for _ in range(max_attempts):\n", " vine = rng.integers(0, Q_UOV, size=V).tolist()\n", " # Build the o-by-o linear system in the o oil unknowns:\n", " # for each k: sum_j (sum_i beta[k][i][j] * vine[i]) * oil[j] = msg_hash[k] - alpha[k](vine,vine)\n", " M, b = [], []\n", " for k in range(O):\n", " row = [sum(beta[k][i][j] * vine[i] for i in range(V)) % Q_UOV for j in range(O)]\n", " const = msg_hash[k]\n", " for i in range(V):\n", " for jp in range(V):\n", " const = (const - alpha[k][i][jp] * vine[i] * vine[jp]) % Q_UOV\n", " M.append(row); b.append(const % Q_UOV)\n", " oil = _gauss(M, b, Q_UOV)\n", " if oil is None: # singular → try fresh vinegar\n", " continue\n", " x_central = vine + oil # solution before applying S\n", " return x_central # toy: return central solution directly\n", " return None\n", "\n", "def uov_verify(sk, x, msg_hash):\n", " alpha, beta, _ = sk\n", " vine, oil = x[:V], x[V:]\n", " return all(central_eval(alpha[k], beta[k], vine, oil) == msg_hash[k] % Q_UOV\n", " for k in range(O))\n", "\n", "\n", "sk_uov = uov_keygen()\n", "msg_hash_uov = [hashlib.sha256(b'UOV-toy').digest()[k] % Q_UOV for k in range(O)]\n", "print('Target hash digits over GF(31):', msg_hash_uov)\n", "sig_uov = uov_sign(sk_uov, msg_hash_uov)\n", "print('Signature x =', sig_uov)\n", "print('Verifies =', uov_verify(sk_uov, sig_uov, msg_hash_uov))\n" ] }, { "cell_type": "markdown", "id": "ch48-008", "metadata": {}, "source": [ "## 48.6 Rainbow and the Beullens 2022 Break\n", "\n", "**Rainbow** (Ding–Schmidt 2005) is a layered UOV: a hierarchy of oil/vinegar\n", "splits where each layer's \"oil\" becomes the next layer's \"vinegar\". Rainbow\n", "was a NIST round-3 *finalist* for digital signatures, with three parameter\n", "sets at security levels I, III, V.\n", "\n", "In **April 2022**, Ward Beullens published *Breaking Rainbow Takes a Weekend on\n", "a Laptop* (CRYPTO 2022). The attack combines two ingredients:\n", "\n", "- The **MinRank** problem: given matrices $M_1, \\ldots, M_k \\in \\F_q^{n \\times n}$,\n", " find a non-trivial linear combination of low rank.\n", "- An **algebraic modelling** of MinRank as a multivariate system, solved via\n", " Gröbner bases.\n", "\n", "Beullens' refined modelling reduced the cost of recovering Rainbow's secret key\n", "from the published security level (e.g., 128 bits for Rainbow-I) to roughly **53\n", "bits of work** — about 53 hours on a single laptop, hence the title.\n", "\n", "The lessons:\n", "\n", "1. **Algebraic security is fragile.** An attack that gains a small constant\n", " factor can collapse a cryptosystem from 128-bit to 53-bit security.\n", "2. **Public scrutiny works.** Rainbow had been studied since 2005 and was a\n", " NIST finalist; the attack still arrived in time to prevent standardisation.\n", "3. **UOV survives** as a round-4 candidate. The simpler, single-layer\n", " construction did not have the layered structure Beullens exploited.\n", "\n", "```{admonition} How to read the Beullens paper\n", ":class: tip\n", "The 2022 paper is technical but readable. Focus on §3 (the rectangular MinRank\n", "modelling) and §4 (the complexity analysis). The algebraic gymnastics are\n", "intricate, but the *shape* of the attack — find a low-rank linear combination of\n", "public-key matrices, then solve a small system — is the part to remember.\n", "```\n" ] }, { "cell_type": "markdown", "id": "ch48-009", "metadata": {}, "source": [ "## 48.7 Isogenies of Supersingular Elliptic Curves\n", "\n", "```{admonition} Definition — Supersingular elliptic curve\n", ":class: important\n", "An elliptic curve $E$ over $\\F_{p^2}$ (with $p$ a large prime, typically a few\n", "hundred bits) is **supersingular** if its trace of Frobenius $t$ over $\\F_{p^2}$\n", "is divisible by $p$ — equivalently, $E$ has no $p$-torsion. Allowed traces over\n", "$\\F_{p^2}$ are $0$ and $\\pm p$ and $\\pm 2p$. The case $t = -2p$ gives\n", "$|E(\\F_{p^2})| = (p+1)^2$, which is the situation in SIDH-style schemes (every\n", "SIDH curve has this point count, since SIDH starts from a curve already\n", "supersingular over $\\F_p$). Supersingular curves form a finite, well-understood\n", "set; for fixed $p$ there are about $\\lfloor p/12 \\rfloor$ isomorphism classes.\n", "```\n", "\n", "```{admonition} Definition — Isogeny\n", ":class: important\n", "A non-zero **isogeny** $\\phi \\colon E \\to E'$ between two elliptic curves is a\n", "non-constant morphism that preserves the identity. Isogenies of degree $\\ell$\n", "correspond to subgroups of $E[\\ell]$ of size $\\ell$ (Vélu's formulae give the\n", "isogeny explicitly from the kernel).\n", "```\n", "\n", "The **supersingular isogeny graph** has the supersingular $j$-invariants as\n", "vertices and $\\ell$-isogenies as edges. For small primes $\\ell$ (typically\n", "$\\ell = 2$ and $\\ell = 3$) the graph is a Ramanujan expander — random walks\n", "mix rapidly.\n", "\n", "The **Supersingular Isogeny Diffie–Hellman** (SIDH) protocol of De Feo–Jao–Plût\n", "(2011) uses random walks of length $\\sim \\log p$ in this graph as a Diffie–Hellman\n", "analogue. Alice publishes her endpoint $E_A$; Bob publishes $E_B$; both\n", "recompute the shared $E_{AB}$ via parallel walks.\n", "\n", "To make the protocol work, SIDH publishes **auxiliary points**: the images\n", "$\\phi_A(P_B), \\phi_A(Q_B)$ of Bob's basis points under Alice's secret isogeny.\n", "These auxiliary points were the trapdoor *and the vulnerability*.\n" ] }, { "cell_type": "markdown", "id": "ch48-010", "metadata": {}, "source": [ "## 48.8 The Castryck–Decru Break of SIDH (2022)\n", "\n", "In **July–August 2022**, Wouter Castryck and Thomas Decru (KU Leuven) published\n", "*An Efficient Key Recovery Attack on SIDH*. Within days, Maino, Martindale,\n", "Panny, Pope and Wesolowski generalised it. The attack:\n", "\n", "1. Uses a deep theorem of Kani (1997) about *gluing* two genus-one surfaces\n", " along a 2-dimensional isogeny to build a *genus-two* abelian surface.\n", "2. Shows that, given Alice's auxiliary points (which SIDH publishes),\n", " Castryck–Decru can construct an abelian-surface isogeny whose kernel\n", " reveals Alice's *secret isogeny* — exactly the secret SIDH was trying to hide.\n", "3. Runs in **polynomial time** for SIDH parameters where the secret isogeny\n", " degree splits as a product of two coprime smooth integers (which all\n", " SIDH/SIKE parameter sets satisfy).\n", "\n", "For SIKEp434, the recovered secret takes about **1 hour of CPU time** on a\n", "single core. SIKEp751 takes **roughly a day**. SIKE was withdrawn from the NIST\n", "PQC competition the same month.\n", "\n", "The most important lesson — perhaps in the entire PQC cryptanalysis literature\n", "— is that **a published auxiliary point is a published structural hint**.\n", "Cryptosystems must commit to *minimal* public information; anything beyond the\n", "strict semantic requirement is potentially a future cryptanalytic vector.\n", "\n", "```{admonition} The Kani lemma in one sentence\n", ":class: tip\n", "Kani's (1997) lemma says: a $(d_1, d_2)$-isogeny between genus-two abelian\n", "surfaces decomposes (under suitable conditions) into a product of two\n", "$d_1$-isogenies and two $d_2$-isogenies between elliptic curves. Castryck–Decru\n", "*runs Kani's lemma backwards*, gluing the two SIDH-published walks into one\n", "genus-two object whose decomposition reveals the secret.\n", "```\n", "\n", "```{admonition} Surviving isogeny schemes\n", ":class: tip\n", "- **CSIDH** (Castryck–Lange–Martindale–Panny–Renes 2018) does *not* publish\n", " auxiliary points; it walks a graph of $\\F_p$-isomorphism classes of\n", " supersingular curves. It is unbroken but extremely slow, and it has its\n", " own quantum subexponential-time attack via Kuperberg's algorithm.\n", "- **SQIsign** (De Feo–Kohel–Leroux–Petit–Wesolowski 2020) also does not\n", " publish auxiliary points; it builds signatures from quaternion ideals via\n", " the Deuring correspondence. It produces the *smallest* signatures of any\n", " PQC candidate (~200 bytes), at the cost of slow signing. NIST has\n", " encouraged a fresh on-ramp signature competition with SQIsign in scope.\n", "```\n" ] }, { "cell_type": "markdown", "id": "ch48-011", "metadata": {}, "source": [ "## 48.9 Exercises\n", "\n", "---\n", "\n", "**Exercise 48.1 — NTRU decryption-failure rate.**\n", "\n", "For the toy NTRU parameters $N = 11$, $p = 3$, $q = 32$, run 10 000 random\n", "encryptions of random plaintexts and count how often decryption produces the\n", "wrong plaintext. Increase $q$ to 64, 128, 256 and re-measure. Plot the failure\n", "rate as a function of $q$. Explain the rate using the bound on the centred\n", "coefficients of $p g r + f m$.\n", "\n", "---\n", "\n", "**Exercise 48.2 — NTRU as a lattice problem.**\n", "\n", "Construct the NTRU lattice $L_h = \\{(u, v) \\in \\Z^N \\times \\Z^N : v = h \\cdot u\n", "\\pmod q\\}$. Verify that $(f, g)$ is a short vector in $L_h$. For\n", "$N = 11, q = 32$, run LLL on $L_h$ and observe whether you recover $(f, g)$\n", "or a related short vector.\n", "\n", "---\n", "\n", "**Exercise 48.3 — UOV toy.**\n", "\n", "Implement UOV for $\\F_{31}$, $v = 6$ vinegar, $o = 4$ oil. Show that signing\n", "a random message hash $\\bm \\in \\F_{31}^4$ produces a valid signature in\n", "expected $\\le 4$ tries (some choices of vinegar lead to a non-invertible\n", "linear system).\n", "\n", "---\n", "\n", "**Exercise 48.4 — MinRank as polynomial system (Beullens-style modelling).**\n", "\n", "Read §3 of Beullens 2022. Implement, on a tiny instance ($q = 7$, two\n", "$3 \\times 3$ matrices), the \"rectangular minor\" modelling of the MinRank\n", "problem as a system of multivariate equations. Compute its Gröbner basis\n", "using `sympy.polys.groebnertools.groebner`. How many equations and unknowns\n", "do you obtain?\n", "\n", "---\n", "\n", "**Exercise 48.5 — Walking the supersingular isogeny graph.**\n", "\n", "(Sage required.) Use `EllipticCurve(GF(p^2), [...])` for a small supersingular\n", "prime $p$ (say $p = 431$). Enumerate the supersingular $j$-invariants. For\n", "each, compute its 2-isogeny neighbours via Vélu's formulae. Plot the resulting\n", "graph and verify that its diameter is $O(\\log p)$.\n", "\n", "---\n", "\n", "**Exercise 48.6 (writing) — Castryck–Decru in your own words.**\n", "\n", "Write a 2-page explainer of the Castryck–Decru attack aimed at a fellow\n", "student who has finished the quantum half of the course but has not yet\n", "seen this chapter. Cover: (a) what SIDH publishes, (b) what Kani's lemma says, (c) how\n", "the attack glues, (d) why this style of attack does not apply to CSIDH or\n", "SQIsign. No equations, only diagrams and intuition.\n" ] }, { "cell_type": "markdown", "id": "ch48-012", "metadata": {}, "source": [ "## 48.10 Summary\n", "\n", "1. **NTRU** is the original practical lattice cryptosystem, predating LWE,\n", " based on a structured polynomial ring. Its lattice formulation is the\n", " support for the Falcon signature standard (FIPS 206 draft).\n", "2. **NTRU-Prime** removes cyclotomic structure as a defensive measure;\n", " it lost the standardisation race to Kyber but remains pedagogically\n", " important.\n", "3. **Multivariate** cryptography (UOV, Rainbow, HFE) hides easy-to-solve\n", " polynomial systems behind random affine maps. UOV survives as a round-4\n", " candidate; Rainbow was broken by Beullens (2022) using a refined MinRank\n", " modelling.\n", "4. **Isogeny-based** cryptography uses random walks in supersingular isogeny\n", " graphs. SIDH/SIKE published auxiliary points and was broken by Castryck\n", " and Decru (2022) via Kani's gluing lemma. CSIDH and SQIsign do not publish\n", " auxiliary points and remain candidates.\n", "5. The recurring theme: **PQC families with smaller parameter sets and\n", " younger mathematics are more fragile** than the older, larger lattice\n", " constructions. NIST's diversification — keeping HQC, SLH-DSA, and an\n", " upcoming on-ramp competition open — is a deliberate hedge against this\n", " fragility.\n" ] }, { "cell_type": "markdown", "id": "ch48-013", "metadata": {}, "source": [ "## 48.11 References\n", "\n", "1. **Hoffstein, J., Pipher, J., Silverman, J. H.** (1998). *NTRU: A Ring-Based\n", " Public Key Cryptosystem.* ANTS-III, LNCS 1423, 267–288.\n", "2. **Bernstein, D. J., Brumley, B. B., Chuengsatiansup, C., Lange, T., van\n", " Vredendaal, C.** (2017). *NTRU Prime.* SAC 2017, LNCS 10719.\n", "3. **Patarin, J.** (1996). *Hidden Fields Equations (HFE) and Isomorphisms of\n", " Polynomials (IP): Two New Families of Asymmetric Algorithms.* EUROCRYPT '96.\n", "4. **Kipnis, A., Patarin, J., Goubin, L.** (1999). *Unbalanced Oil and Vinegar\n", " Signature Schemes.* EUROCRYPT '99.\n", "5. **Ding, J., Schmidt, D.** (2005). *Rainbow, a New Multivariable Polynomial\n", " Signature Scheme.* ACNS 2005, LNCS 3531.\n", "6. **Beullens, W.** (2022). *Breaking Rainbow Takes a Weekend on a Laptop.*\n", " CRYPTO 2022, LNCS 13508. ePrint 2022/214.\n", "7. **De Feo, L., Jao, D., Plût, J.** (2014). *Towards quantum-resistant\n", " cryptosystems from supersingular elliptic curve isogenies.* Journal of\n", " Mathematical Cryptology **8**(3).\n", "8. **Castryck, W., Decru, T.** (2023). *An Efficient Key Recovery Attack on\n", " SIDH.* EUROCRYPT 2023, LNCS 14008. ePrint 2022/975.\n", "9. **Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.** (2023).\n", " *A Direct Key Recovery Attack on SIDH.* EUROCRYPT 2023.\n", "10. **Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.** (2018).\n", " *CSIDH: An Efficient Post-Quantum Commutative Group Action.* ASIACRYPT 2018.\n", "11. **De Feo, L., Kohel, D., Leroux, A., Petit, C., Wesolowski, B.** (2020).\n", " *SQISign: Compact Post-Quantum Signatures from Quaternions and Isogenies.*\n", " ASIACRYPT 2020.\n", "12. **NIST** (2022). *Status report on the third round of the NIST PQC\n", " standardization process.* NISTIR 8413.\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 }