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