Chapter 3: Hard problems at a glance

The four post-quantum families this book studies are organized around four kinds of hardness assumption. Lattice schemes rest on finding short vectors in a high-dimensional integer grid. Hash-based schemes rest on inverting or colliding a one-way function. Code-based schemes rest on decoding a random linear code. Isogeny schemes rest on finding walks between supersingular elliptic curves, and on the endomorphism-ring structure that those walks reveal.

Other post-quantum constructions exist: multivariate signatures, MPC-in-the-head signatures, rank-metric and other code-based variants, and additional lattice designs not treated in depth here. All four have a current FIPS standard, a selected future standard, or an active NIST candidate process, and they are the families the rest of the book treats in depth. They are not the only ones in an active process: NIST’s round-3 additional-signatures list also carries multivariate, MPC-in-the-head, and symmetric-primitive candidates. Chapter 3 states each of the four problems in the form the later chapters use as a security assumption.

A lattice you can draw

Consider the integer lattice $L \subset \mathbb{Z}^2$ with basis vectors $b_1 = (2, 7)$ and $b_2 = (5, 3)$. The lattice $L$ is the set of all integer combinations $\alpha b_1 + \beta b_2$ with $\alpha, \beta \in \mathbb{Z}$. Because $b_1$ and $b_2$ are linearly independent, every point of $L$ comes from exactly one pair $(\alpha, \beta)$, so two vectors generate $L$ and no single vector does. Chapter 7 develops what a basis means over $\mathbb{Z}$, which Chapter 2 deliberately set aside in favour of bases over $\mathbb{F}_p$.

The two basis vectors $(2, 7)$ and $(5, 3)$ have Euclidean norms $\sqrt{53} \approx 7.28$ and $\sqrt{34} \approx 5.83$, respectively. Neither is the shortest nonzero vector in $L$. The combination $b_1 - b_2 = (-3, 4)$ lies in $L$ and has norm $\sqrt{9 + 16} = 5$.

To prove that 5 is globally shortest, it is enough to rule out any lattice point with norm strictly less than 5. Such a point would lie among the finitely many integer points $(x, y) \neq (0, 0)$ with $x^2 + y^2 < 25$. A point $(x, y)$ belongs to $L$ iff there exist integers $a, b$ with $x = 2a + 5b$ and $y = 7a + 3b$, which forces the congruence $7x - 2y \equiv 0 \pmod{29}$. Checking each integer point with $x^2 + y^2 < 25$ against that congruence (Exercise 1, and the appendix walks the residue check) returns the empty set, so $\lambda_1(L) = 5$, attained on the boundary by $(\pm 3, \mp 4)$.

Figure 3.1. The lattice $L$ generated by $b_1 = (2, 7)$ and $b_2 = (5, 3)$, with the circle of radius 5 about the origin drawn dashed. Both basis vectors end outside that circle; their difference $b_1 - b_2 = (-3, 4)$ ends on it. No nonzero point lies strictly inside, which is what makes $\lambda_1(L) = 5$ rather than merely the best value found so far.

Finding the shortest vector of this two-dimensional lattice by hand is annoying but possible. ML-KEM-512 (National Institute of Standards and Technology, 2024) uses Module-LWE with module rank 2 over a degree-256 polynomial ring, giving a natural module dimension of $2 \cdot 256 = 512$. Concrete attacks on Module-LWE translate that structured noisy-linear-algebra problem into lattice-reduction instances, whose dimension depends on the chosen primal or dual attack model (Chapter 13 walks both). They do not translate it into the exact toy shortest vector problem (SVP) solved by hand above. The jump from dimension 2 to module-rank-2 over a 256-coefficient ring is the jump from “undergraduate exercise” to “security assumption”. The rest of Chapter 3 names the three other places where a similar jump happens.

What a hard problem is

A computational or search problem asks the solver to produce an object: the shortest vector, a colliding pair, an error pattern, an isogeny. A decision problem asks for a yes-or-no answer. Both flavours appear among the four problems below, and the decision problems are not all of one kind: $\mathrm{GapSVP}$ and $\mathrm{GapCVP}$ decide between two promised numerical cases, while decisional LWE decides which of two distributions its samples came from. Many lattice KEMs (including ML-KEM) use a decisional Module-LWE assumption as their security assumption, while lattice signatures (including ML-DSA) involve SIS-style assumptions as well. In both cases the hardness reductions are routed through search variants of the same problems.

Cryptography cares about average-case hardness, not worst-case hardness. A randomly chosen key must be hard to break, not merely some specific adversarial key. Lattice cryptography is unusual because it has a worst-case to average-case reduction. Ajtai proved in 1996 that approximating the shortest vector problem within polynomial factors in the worst case reduces to solving the short integer solution (SIS) problem on average (Ajtai, 1996). This was the first worst-case to average-case reduction in cryptography. Regev introduced learning with errors in 2005 and extended the approach to it. The expanded journal version appeared in 2009 (Regev, 2009).

The other three families stand differently. Code-based cryptography has a worst-case hardness result for syndrome decoding: Berlekamp, McEliece, and van Tilborg proved in 1978 that the decision problem is NP-complete, which makes the corresponding search problem NP-hard (Berlekamp et al., 1978). But the connection to the average case is a working conjecture, not a theorem. Hash-based cryptography rests on properties of concrete hash-function-derived primitives, with no Ajtai/Regev-style worst-case lattice reduction underneath. Isogeny cryptography sits closer to the lattice picture than to the hash picture: the supersingular endomorphism-ring problem comes with a random self-reduction that turns its worst-case difficulty into average-case difficulty over the natural distribution of supersingular curves. What it does not do is reduce to a worst-case problem outside the isogeny world. The comparison at the end of the chapter sets the four positions side by side.

Shor’s algorithm breaks RSA and elliptic-curve discrete log because those problems reduce to quantum period-finding, which is in BQP (Chapter 1). None of the four problems below has a known quantum polynomial-time algorithm. The best quantum speedups known are Grover-style square-root speedups and their generalizations. They force parameters up but do not collapse security classes.

The four problems

Lattice problems: SVP, CVP, and LWE

A lattice of dimension $n$ is the set of all integer combinations of $n$ linearly independent vectors in $\mathbb{R}^n$. Those vectors form a basis. Different bases can span the same lattice. Chapter 7 develops the full algebra; this chapter needs only the definition and three problems stated on top of it.

The shortest vector problem (SVP) takes as input a basis $B$ of a lattice $L \subset \mathbb{R}^n$. It asks for a nonzero vector $v \in L$ minimizing the Euclidean norm $\lVert v \rVert_2$. The closest vector problem (CVP) takes as input a basis $B$ and a target point $t \in \mathbb{R}^n$. It asks for a vector $v \in L$ minimizing $\lVert v - t \rVert_2$.

Two relaxations of these exact problems matter for cryptography. The approximate search versions $\mathrm{SVP}_\gamma$ and $\mathrm{CVP}_\gamma$ ask for an output vector within a factor $\gamma$ of optimal. The gap decision versions $\mathrm{GapSVP}_\gamma$ and $\mathrm{GapCVP}_\gamma$ take an additional threshold $d > 0$. Under the promise that one of the two cases holds, they ask the solver to decide whether the optimum is at most $d$ or strictly greater than $\gamma d$. At suitable approximation factors these relaxations remain hard enough for cryptography. On the shortest-vector side that is Ajtai’s result (Ajtai, 1996). Chapter 7 spells out the gap parameters that matter. The worst-case-to-average-case reductions cited later in this chapter target approximation problems including $\mathrm{GapSVP}$ and $\mathrm{SIVP}$. Because $\mathrm{SIVP}$ is a search problem, not a decision problem, “the gap-decision form” would not describe them.

The learning with errors (LWE) problem has two standard forms, search and decisional. They are equivalent only under additional parameter conditions, which the next paragraph states. Search LWE takes as input a uniform matrix $A \in \mathbb{Z}_q^{m \times n}$ and the vector $b = A s + e \in \mathbb{Z}_q^m$. Here $s \in \mathbb{Z}_q^n$ is a uniformly random secret and $e$ has entries drawn from a narrow error distribution. The solver must recover $s$ (Regev, 2009). Decisional LWE gives the solver either the pair $(A, A s + e)$ or the pair $(A, u)$ for a uniform $u \in \mathbb{Z}_q^m$, and the solver must decide which.

Regev’s paper proved two reductions, and their hypotheses differ. The worst-case-to-average-case reduction constrains both the modulus $q$ and the Gaussian noise rate. Under those conditions, solving search LWE on average is at least as hard as approximating $\mathrm{GapSVP}$ and the shortest independent vectors problem $\mathrm{SIVP}$ in the worst case, under a quantum reduction. Separately, for prime $q$ polynomial in $n$, a decisional-LWE oracle recovers the search secret, and that lemma holds for any fixed error distribution $\chi$ on $\mathbb{Z}_q$ rather than needing a noise-rate condition of its own (Regev, 2009). Chapter 8 develops both reductions and states the exact hypotheses each one needs.

The error distribution matters: too narrow and LWE is easy, too wide and the honest decrypter also fails. LWE over the ring $\mathbb{Z}_q[x]/(x^n + 1)$ (introduced in Chapter 2) gives a structured variant called Ring-LWE. ML-KEM uses a module generalization of Ring-LWE called Module-LWE, with module rank 2, 3, or 4 over the ring $\mathbb{Z}_{3329}[x]/(x^{256} + 1)$ for the three security levels (National Institute of Standards and Technology, 2024). Chapter 9 develops Ring-LWE and Module-LWE. The worst-case-to-average-case lineage from $\mathrm{GapSVP}$ and $\mathrm{SIVP}$ down to LWE/SIS is one reason lattice cryptography inspires unusual confidence. For standardized structured schemes such as ML-KEM and ML-DSA, that lineage is combined with module-lattice assumptions, concrete cryptanalysis based on the Block Korkine-Zolotarev (BKZ) lattice-reduction algorithm, scheme-construction reductions, and implementation-level requirements. The worst-case backing is one ingredient in the security story rather than its entirety.

Hash problems: preimage, second preimage, collision, multi-target

A cryptographic hash function $H: \{0,1\}^* \to \{0,1\}^n$ maps arbitrary-length messages to $n$-bit digests. A cryptographic hash is expected to satisfy three security properties (Boneh & Shoup, 2023).

For a well-designed $n$-bit hash, treated to first approximation as a random oracle on its domain, the standard bounds read as follows. Preimage resistance says that for a target digest $y = H(x)$ with $x$ unknown, finding any $x'$ with $H(x') = y$ takes roughly $2^n$ hash evaluations. Second-preimage resistance says that given a specific input $x$ and its digest $H(x)$, finding a different input $x' \neq x$ with $H(x') = H(x)$ also takes roughly $2^n$ evaluations (long-message variants and structured-domain attacks can shave this). Collision resistance says that finding any pair $(x, x')$ with $x \neq x'$ and $H(x) = H(x')$ takes roughly $2^{n/2}$ evaluations, by the birthday bound (Boneh & Shoup, 2023).

The multi-target setting changes these numbers. If the adversary is given $k$ target digests and only needs to invert any one of them, the expected cost drops from roughly $2^n$ to roughly $2^n / k$ for modest $k$. Hash-based signature schemes are designed so that multi-target attacks do not become the dominant threat.

SLH-DSA, which is the FIPS 205 hash-based signature standard (National Institute of Standards and Technology, 2024b), is stateless: it does not maintain a counter that guarantees a one-time key is reached at most once. Instead, it derives the WOTS+ and FORS secret values from SK.seed through PRF, and passes a distinct 32-byte ADRS address into each address-dependent call: PRF, $T_\ell$, H, and F. The two message-keyed functions, PRF_msg and H_msg, take no address. It then sizes the underlying hypertree and FORS construction so that the probability of harmful key reuse or collision over the approved signing limit of up to $2^{64}$ messages stays inside the security target. Chapter 17 walks that construction.

Code problems: syndrome decoding of a random linear code

A linear code $\mathcal{C} \subseteq \mathbb{F}_2^n$ of dimension $k$ is the kernel of a full-rank parity-check matrix $H \in \mathbb{F}_2^{(n-k) \times n}$ (the full-rank assumption is what forces $\dim \ker H = k$). In symbols, $\mathcal{C} = \{c \in \mathbb{F}_2^n : H c^\top = 0\}$. Chapter 2 developed the algebra of matrices over $\mathbb{F}_2$ and $\mathbb{F}_p$; this chapter needs only the parity-check viewpoint.

The syndrome decoding problem (SDP) takes three inputs: a parity-check matrix $H \in \mathbb{F}_2^{(n-k) \times n}$, a syndrome $s \in \mathbb{F}_2^{n-k}$, and a target weight $w \in \mathbb{N}$. The solver must find $e \in \mathbb{F}_2^n$ with Hamming weight $\mathrm{wt}(e) \leq w$ and $H e^\top = s$. The associated decision problem asks only whether such an $e$ exists. Berlekamp, McEliece, and van Tilborg proved in 1978 that this decision problem is NP-complete for arbitrary binary linear codes (Berlekamp et al., 1978). The search problem stated above, which must produce $e$, is NP-hard.

NP-completeness is a worst-case statement: it says that some instances of syndrome decoding are hard, not that random instances are hard on average. Code-based cryptography rests on the stronger working assumption that random linear codes are hard to decode on average. Chapter 19 walks where that assumption enters the security argument.

Real code-based cryptosystems pin their proofs to specific variants of this decoding problem rather than to bare SDP. HQC uses quasi-cyclic structure and proves IND-CCA2 security (indistinguishability under adaptive chosen-ciphertext attack) against a decisional Quasi-Cyclic Syndrome Decoding (QCSD) assumption (Gaborit et al., 2025). Classic McEliece uses binary Goppa codes and states its assumption as one-wayness of decoding directly over the Goppa-derived public key. The literature also names an extra indistinguishability assumption, that a random binary Goppa code is hard to tell from a random linear code. That assumption motivates studying distinguishers as a minimum bar for structural attacks, but the submission declines to rely on it (Albrecht et al., 2022, sec. 3.1 of the guide for security reviewers).

The bounded-distance-decoding (BDD) problem takes a code $\mathcal{C}$ of minimum distance $d$ and a received word $r$, under the promise that $\mathrm{dist}(r, \mathcal{C}) \leq t < d/2$, and asks for the unique closest codeword, or equivalently its error vector. The bound $t < d/2$ is what makes the answer unique; a promise that some low-weight error exists does not on its own. BDD is a related search problem that surfaces in the analysis, but it is not the primitive HQC’s proof targets. Chapter 19 develops these variants and Chapter 21 walks how HQC uses the QCSD form.

Isogeny problems: finding walks between supersingular curves

An isogeny between two elliptic curves $E_1$ and $E_2$ over a field $k$ is a nonconstant rational map $\phi: E_1 \to E_2$ that sends the identity of $E_1$ to the identity of $E_2$ and respects the group law. An elliptic curve over $\mathbb{F}_{p^2}$ is called supersingular when its $p$-torsion subgroup is trivial over the algebraic closure. To state the isogeny problems, the reader needs only that supersingular curves form a finite set that is connected under isogenies.

Structure deferred to Chapter 22

Two further pieces of structure attach to supersingular curves, and neither is needed to state the problems below. Chapter 22 develops the equivalent characterization of supersingularity in terms of the trace of Frobenius, and Deuring’s theorem: the endomorphism ring of a supersingular curve is a maximal order in the quaternion algebra ramified at $p$ and $\infty$. That endomorphism ring is the object SQIsign’s central hardness assumption is stated about, so the definition matters later even though the problem statement below does not need it.

The general supersingular isogeny path problem takes as input two supersingular elliptic curves $E_1$ and $E_2$ over $\mathbb{F}_{p^2}$ that are known to lie in the same isogeny graph. It asks for an efficiently representable isogeny $\phi: E_1 \to E_2$, or for a path between them in the graph. Some protocol-specific variants further prescribe the degree of $\phi$ or restrict it to be smooth (a product of small-prime isogenies). That sharpens the search space at the cost of introducing extra structure that the cryptanalyst can exploit. Couveignes gave the first cryptographic formulation of an isogeny problem in 1997 (Couveignes, 1997).

SIDH, the first efficient isogeny-based key exchange, was instantiated against a smooth-degree variant of this problem. To make the protocol non-interactive, SIDH published auxiliary torsion-point images that encoded the secret isogeny redundantly. Castryck and Decru used that redundancy together with Kani’s lemma on isogenies between products of elliptic curves to recover the secret in 2022, in heuristic polynomial classical time when the endomorphism ring of the starting curve is known, apart from the factorization of a few integers fixed by the system parameters (Castryck & Decru, 2023). The attack uniquely depends on the published torsion data.

SQIsign, the isogeny signature scheme currently in NIST’s additional-signatures standardization track, does not expose the artifact Castryck-Decru consumes: images of publicly fixed torsion bases under the secret isogeny. It is not true that SQIsign publishes no point images at all. Its signatures represent the response isogeny by interpolation data, the images of a few points under it, and also include compact hints used to regenerate torsion bases (The SQIsign Team, 2025). Those basis-generation hints are distinct from the simulator-side hint distributions the security proof reasons about. The specification says the two kinds are unrelated.

Its central hardness assumption is the supersingular endomorphism-ring problem: given a supersingular curve $E$ over $\mathbb{F}_{p^2}$, recover the maximal order $\mathrm{End}(E)$. General arbitrary-isogeny finding, the OneEnd problem of recovering any single non-scalar endomorphism, and the endomorphism-ring problem are polynomial-time equivalent (Page & Wesolowski, 2024). SQIsign’s soundness rests on OneEnd rather than on the ring directly. Wesolowski’s earlier fixed-$\ell$ path equivalence is weaker in its hypotheses: expected polynomial-time reductions, under the generalized Riemann hypothesis (Wesolowski, 2022). The current analysis states those relations with hints, and assumes that two hint distributions are computationally indistinguishable rather than proving it (The SQIsign Team, 2025). Because the SQIsign transcript is not the SIDH transcript, the Castryck-Decru attack does not apply. Chapter 22 builds SIDH, and Chapter 23 builds SQIsign and walks the reduction.

How each problem falls

Lattice attacks. The dominant attack on LWE and on lattice problems generally is the BKZ family of lattice basis reduction algorithms. BKZ’s cost grows with the block size chosen by the attacker, which trades runtime against approximation quality. Quantum lattice sieves recover Grover-style speedups but stay in the same asymptotic class. Chapter 13 walks BKZ, its quantum variants, and the concrete security margin that the three ML-KEM parameter sets of FIPS 203 §8 (National Institute of Standards and Technology, 2024a) target.

Hash attacks. Preimage resistance of an $n$-bit hash is attacked in $2^n$ evaluations classically and roughly $2^{n/2}$ queries under Grover search (Boneh & Shoup, 2023). Collision resistance is attacked in $2^{n/2}$ evaluations classically under the birthday bound. Quantum collision-finding algorithms (the Brassard-Hoyer-Tapp line) can push the query count to roughly $2^{n/3}$ (Brassard et al., 1998). Chapter 14 walks the hash-based signatures and Chapter 18 walks the cryptanalysis.

A query bound is not a security category

Mapping a quantum query bound into NIST’s practical security categories depends on the quantum cost model NIST applies, including circuit-depth limits, total circuit size, and the parallelization model (National Institute of Standards and Technology, 2016). How much large coherent quantum memory an attack assumes matters too, and it is what separates the $2^{n/3}$ bound from variants that assume less of it (Chailloux et al., 2017). NIST’s category definitions are anchored to specific reference primitives (AES-128/192/256 and SHA2/SHA3-256/384) at the corresponding security levels rather than to a single attack class. The $2^{n/3}$ figure above is a query count and not a category on its own.

Code attacks. The dominant attack on random-code syndrome decoding is information-set decoding (ISD). All known classical and quantum variants are exponential in the code length, and the line of algorithmic improvements has sharpened the exponent constant without changing that bound. Chapter 20 walks ISD and its effect on Classic McEliece parameter choices. Chapter 21 covers HQC.

Isogeny attacks. A meet-in-the-middle walk on the isogeny graph solves the supersingular isogeny problem in time $\tilde{O}(p^{1/2})$ classically, and in $\tilde{O}(p^{1/2})$ space, which is the cost that makes it awkward rather than the time (Delfs & Galbraith, 2016). For the endomorphism-ring problem SQIsign rests on, the round-3 specification of September 2026 bases its estimates on a July 2026 classical algorithm that, under a heuristic assumption on the smoothness of certain random integers, runs in $p^{1/3+o(1)}$ time and memory, priced through the time-memory tradeoff $t^2 w = \tilde{O}(p)$ its memory forces, and keeps the quantum bound at $\tilde{O}(p^{1/4})$ under Grover search at low memory (The SQIsign Team, 2026; Wesolowski, 2026). The quantum gain is a square root, not a Shor-style collapse. Chapter 22 walks the precise exponents. The Castryck-Decru attack, heuristic polynomial time for SIDH with a known starting endomorphism ring, is specific to SIDH’s torsion-point leakage and does not generalize to SQIsign (Castryck & Decru, 2023).

Comparing the four families

The four families differ along four deployment-relevant axes.

Assumption maturity. Hash and code are the oldest assumption families. Lattice has the strongest worst-case-to-average-case lineage in its unstructured form and now backs NIST’s main KEM and signature standards. Isogeny is the youngest and most specialized family in current standardization discussions. The supersingular endomorphism-ring problem has older mathematical roots. The relevant arithmetic geometry goes back to the 1990s (De Feo et al., 2020). But SQIsign’s specific construction dates from 2020, and the family has accumulated substantially less cryptanalytic history than hash, code, or lattice assumptions.

Artifact size. The artifact a deployment has to carry runs from 200 bytes to over a megabyte.

Scheme and artifact	Family	Size
SQIsign NIST-I / III / V signature	Isogeny	200 / 306 / 406 B (The SQIsign Team, 2026)
ML-DSA-44 / 65 / 87 signature	Lattice	2,420 / 3,309 / 4,627 B (National Institute of Standards and Technology, 2024b)
SLH-DSA signature	Hash	7,856 B to 49,856 B (National Institute of Standards and Technology, 2024c)
ML-KEM-512 / 768 / 1024 ciphertext	Lattice	768 / 1,088 / 1,568 B (National Institute of Standards and Technology, 2024a)
HQC public key and ciphertext	Code	A few kB to low tens of kB (Gaborit et al., 2025)
Classic McEliece public key	Code	Hundreds of kB to over 1 MB (Albrecht et al., 2022)

SQIsign has the smallest signatures among the schemes discussed here; those figures are the round-3 specification’s of September 2026, which raised the round-2 sizes after a new endomorphism-ring algorithm, and a later revision could move them again. The SLH-DSA range spans its parameter sets, and the Classic McEliece figure is reached at its highest parameter sets.

Kind of security evidence. The four families do not offer the same kind of guarantee, and the difference is in what connects a worst-case result to the average case a real key lives in.

Family	Worst-case hardness result	Route to the average case
Lattice	Approximate worst-case lattice problems: SVP-type, $\mathrm{GapSVP}$, $\mathrm{SIVP}$, depending on the reduction (Ajtai, 1996; Micciancio & Regev, 2007; Regev, 2009)	A reduction, to SIS (Ajtai, 1996; Micciancio & Regev, 2007) and to LWE (Regev, 2009)
Code	Syndrome decoding: the decision problem is NP-complete, the search problem NP-hard (Berlekamp et al., 1978)	A working conjecture, not a reduction
Hash	None	Studied properties of concrete primitives
Isogeny	None	A random self-reduction over supersingular curves

Three qualifications the table cannot carry. The lattice reductions are statements about the unstructured forms. The module variants the standards actually use have structured-lattice analogues rather than the original results. The isogeny self-reduction stays inside the isogeny world: it turns worst-case difficulty into average-case difficulty over the natural distribution of supersingular curves, and does not reach a worst-case problem outside that setting. And the isogeny row is about SQIsign’s assumptions, which are the supersingular endomorphism-ring and isogeny problems, distinct from the SIDH/SIKE setting that Castryck-Decru broke.

Standardization status. Three of these schemes are finalized standards and three are not.

Scheme	Family	Status
ML-KEM	Lattice	FIPS 203, August 2024 (National Institute of Standards and Technology, 2024a)
ML-DSA	Lattice	FIPS 204, August 2024 (National Institute of Standards and Technology, 2024b)
SLH-DSA	Hash	FIPS 205, August 2024 (National Institute of Standards and Technology, 2024c)
FN-DSA (Falcon)	Lattice	Selected, expected as FIPS 206 (Perlner, 2025)
HQC	Code	Selected March 2025 (National Institute of Standards and Technology, 2025); final standard expected in 2027, per NIST’s March 2025 announcement (National Institute of Standards and Technology, 2025b)
SQIsign	Isogeny	Additional Digital Signatures on-ramp, Round 3, May 2026 (National Institute of Standards and Technology, 2026)

FN-DSA is another lattice-based signature, and this chapter treats it under the same lattice-assumption umbrella as ML-DSA rather than as a fifth family. HQC was selected as a second KEM, intended as a non-lattice backup to ML-KEM. NIST has communicated a draft standard roughly one year after selection. Neither HQC nor SQIsign is a finalized FIPS standard yet.

Where Chapter 3 ends and Chapter 4 picks up

This chapter named four hardness assumptions and stated each one precisely enough to be used as one. It built nothing on any of them. No key was generated, no ciphertext was formed, and every size in the tables above was quoted from a specification rather than derived.

Chapter 4 starts from the other end, and from the schemes that are already deployed. It codes RSA and ECDSA from scratch, two schemes whose hardness assumptions Shor’s algorithm does break, as the foil the post-quantum families are measured against. Parts II through IV then build those families in the order this chapter introduced them, and produce the real numbers.

Exercises

1. Find the shortest vector of the chapter’s 2D lattice. Take the basis matrix $B = \begin{pmatrix} 2 & 5 \\ 7 & 3 \end{pmatrix}$, whose columns are $b_1 = (2, 7)$ and $b_2 = (5, 3)$, and work in three stages. A brute search over a coefficient box proves a minimum only over that box, so stages (b) and (c) are what close the argument.

   (a) Brute search. For every pair $(a, b) \in \{-3, -2, -1, 0, 1, 2, 3\}^2$ with $(a, b) \neq (0, 0)$, compute the vector $v = a(2, 7) + b(5, 3)$ and its squared Euclidean norm. Verify that the minimum squared norm over the checked coefficient box is 25, achieved by $v = (-3, 4)$ and $v = (3, -4)$. Count how many pairs $(a, b)$ you had to check.

   (b) Close the global-minimum gap. List every integer point $(x, y) \neq (0, 0)$ with $x^2 + y^2 < 25$, and explain why none of them lies in $L$. Hint: $(x, y)$ is in $L$ iff there exist integers $a, b$ with $x = 2a + 5b$ and $y = 7a + 3b$. Eliminating $a$ from those two equations forces the congruence $7x - 2y \equiv 0 \pmod{29}$, and a single residue check rules out every short candidate.

   (c) Check the boundary. The set $x^2 + y^2 = 25$ contains twelve integer points. Confirm that the only two in $L$ are $(-3, 4)$ and $(3, -4)$, which gives $\lambda_1(L) = 5$.

2. Decode a toy Hamming syndrome. Take the standard parity-check matrix $H$ of the $[7, 4]$ Hamming code, whose $j$-th column is the 3-bit binary representation of the integer $j$ for $j = 1, 2, \dots, 7$. Given the syndrome $s = (1, 0, 1)^\top$, find the weight-1 error vector $e \in \mathbb{F}_2^7$ with $H e^\top = s$. The hint is that the columns of $H$ are the binary representations of 1 through 7, so the syndrome directly names the error position. Then explain in one or two sentences why the same strategy does not work for a random $[7, 4]$ linear code.

3. State the three lattice problems from memory. Without looking back at the chapter’s lattice-problem definitions, write the exact shortest vector problem, the exact closest vector problem, and the exact (not gap, not approximate) learning with errors problem in one sentence each. Include the inputs and the required output for every problem. Then, in one extra sentence per problem, write down the corresponding decision variant, $\mathrm{GapSVP}_\gamma$, $\mathrm{GapCVP}_\gamma$, and decisional LWE, naming what the solver decides between. Only the first two are gap problems; decisional LWE distinguishes distributions. Cross-check your LWE statement against Regev’s original paper (Regev, 2009).

4. Explain the post-SIDH lesson in two sentences. Using only the chapter’s isogeny-problem and cryptanalysis sections, explain (a) what the Castryck-Decru attack (Castryck & Decru, 2023) exploits in the SIDH key exchange, and (b) why the same attack does not apply to SQIsign. Be specific about which protocol artifact (auxiliary torsion-point images) Castryck-Decru consumes, and which assumption (the supersingular endomorphism-ring problem) SQIsign substitutes for the SIDH-style smooth-degree path-finding problem.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 3. A separate track, for rebuilding rather than reading: the package exercises/ch03-hard-problems has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch03 to grade your version against the suite that proves the reference one.

References

Ajtai, M. (1996). Generating hard instances of lattice problems (extended abstract). Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 99–108. https://doi.org/10.1145/237814.237838

Albrecht, M. R., Bernstein, D. J., Chou, T., Cid, C., Gilcher, J., Lange, T., Maram, V., von Maurich, I., Misoczki, R., Niederhagen, R., Paterson, K. G., Persichetti, E., Peters, C., Schwabe, P., Sendrier, N., Szefer, J., Tjhai, C. J., Tomlinson, M., & Wang, W. (2022). Classic McEliece: conservative code-based cryptography. NIST Post-Quantum Cryptography Round 4 submission. https://classic.mceliece.org/nist.html

Berlekamp, E. R., McEliece, R. J., & van Tilborg, H. C. A. (1978). On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24(3), 384–386. https://doi.org/10.1109/TIT.1978.1055873

Boneh, D., & Shoup, V. (2023). A Graduate Course in Applied Cryptography (v0.6). Free online textbook. https://toc.cryptobook.us/

Brassard, G., Høyer, P., & Tapp, A. (1998). Quantum Cryptanalysis of Hash and Claw-Free Functions. LATIN ’98: Theoretical Informatics, 1380, 163–169. https://doi.org/10.1007/bfb0054319

Castryck, W., & Decru, T. (2023). An efficient key recovery attack on SIDH. Advances in Cryptology – EUROCRYPT 2023, Part V, 14008, 423–447. https://doi.org/10.1007/978-3-031-30589-4_15

Chailloux, A., Naya-Plasencia, M., & Schrottenloher, A. (2017). An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography. Advances in Cryptology — ASIACRYPT 2017, 211–240. https://doi.org/10.1007/978-3-319-70697-9_8

Couveignes, J.-M. (1997). Hard homogeneous spaces. Cryptology ePrint Archive, Paper 2006/291. https://eprint.iacr.org/2006/291

De Feo, L., Kohel, D., Leroux, A., Petit, C., & Wesolowski, B. (2020). SQIsign: Compact Post-Quantum Signatures from Quaternions and Isogenies. Advances in Cryptology – ASIACRYPT 2020, Part I, 12491, 64–93. https://doi.org/10.1007/978-3-030-64837-4_3

Delfs, C., & Galbraith, S. D. (2016). Computing isogenies between supersingular elliptic curves over 𝔽_p. Designs, Codes and Cryptography, 78(2), 425–440. https://doi.org/10.1007/s10623-014-0010-1

Gaborit, P., Aguilar-Melchor, C., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Persichetti, E., Zémor, G., Bos, J., Dion, A., Lacan, J., Robert, J.-M., Véron, P., Barreto, P. S. L. M., Ghosh, S., Gueron, S., Güneysu, T., Misoczki, R., … Vasseur, V. (2025). HQC: Hamming Quasi-Cyclic. https://pqc-hqc.org/doc/hqc_specifications_2025_08_22.pdf

Micciancio, D., & Regev, O. (2007). Worst-Case to Average-Case Reductions Based on Gaussian Measures. SIAM Journal on Computing, 37(1), 267–302. https://doi.org/10.1137/S0097539705447360

National Institute of Standards and Technology. (2016). Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Call for Proposals, Section 4.A.5 (Security Strength Categories). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

National Institute of Standards and Technology. (2024a). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.203

National Institute of Standards and Technology. (2024b). FIPS 204: Module-Lattice-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.204

National Institute of Standards and Technology. (2024c). FIPS 205: Stateless Hash-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.205

National Institute of Standards and Technology. (2025a). Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process (Internal Report NIST IR 8545). National Institute of Standards and Technology. https://doi.org/10.6028/NIST.IR.8545

National Institute of Standards and Technology. (2025b). NIST Selects HQC as Fifth Algorithm for Post-Quantum Encryption. NIST news release. https://www.nist.gov/news-events/news/2025/03/nist-selects-hqc-fifth-algorithm-post-quantum-encryption

National Institute of Standards and Technology. (2026). Status Report on the Second Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process (Internal Report NIST IR 8610). National Institute of Standards and Technology. https://doi.org/10.6028/NIST.IR.8610

Page, A., & Wesolowski, B. (2024). The Supersingular Endomorphism Ring and One Endomorphism Problems are Equivalent. In M. Joye & G. Leander (Eds.), Advances in Cryptology – EUROCRYPT 2024, Part VI (Vol. 14656, pp. 388–417). Springer, Cham. https://doi.org/10.1007/978-3-031-58751-1_14

Perlner, R. (2025). FIPS 206 Status Update: Fast-Fourier Lattice-Based Digital Signature Standard (FN-DSA, Falcon). NIST Computer Security Resource Center status presentation. https://csrc.nist.gov/presentations/2025/fips-206-fn-dsa-falcon

Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6), 34:1-34:40. https://doi.org/10.1145/1568318.1568324

The SQIsign Team. (2025). SQIsign: Algorithm Specifications and Supporting Documentation (Version 2.0.1). NIST Post-Quantum Cryptography Additional Signatures, Round 2 submission. https://sqisign.org/spec/sqisign-20250707.pdf

The SQIsign Team. (2026). SQIsign: Algorithm Specifications and Supporting Documentation (Version 3.0). NIST Post-Quantum Cryptography Additional Signatures, Round 3 submission. https://sqisign.org/spec/sqisign-20260901.pdf

Wesolowski, B. (2022). The Supersingular Isogeny Path and Endomorphism Ring Problems are Equivalent. 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, 1100–1111. https://doi.org/10.1109/FOCS52979.2021.00109

Wesolowski, B. (2026). The supersingular isogeny problem in time and memory p^1/3+o(1). Cryptology ePrint Archive, Paper 2026/1486. https://eprint.iacr.org/2026/1486