Appendix D: Solutions for Chapter 3

This page collects solutions and editorial notes for the exercises in Chapter 3: Hard problems at a glance. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

Every block below is self-contained and runs on the standard library alone. The fuller versions of these routines, with the lattice-membership congruence derived rather than asserted, are in the hard_problems package under solutions/ch03-hard-problems. From a clone of the companion repository, pytest tests/ch03 runs its suite. Appendix C has the setup.

Exercise 1

Brute search. The brute search covers $7 \times 7 - 1 = 48$ pairs. The minimum squared norm is 25, achieved by $(a, b) = (1, -1)$, which gives $v = (2 - 5, 7 - 3) = (-3, 4)$, and by $(a, b) = (-1, 1)$, which gives $v = (3, -4)$. The vectors $(\pm 3, \mp 4)$ are negatives of each other, as expected: a lattice is closed under negation, so the shortest nonzero vector always comes in $\pm$ pairs.

B = [(2, 7), (5, 3)]  # the basis vectors b_1, b_2, the columns of B in the exercise
norms = []
for a in range(-3, 4):
    for b in range(-3, 4):
        if (a, b) == (0, 0):
            continue
        v = (a * B[0][0] + b * B[1][0], a * B[0][1] + b * B[1][1])
        norms.append((v[0] * v[0] + v[1] * v[1], (a, b), v))
norms.sort()
print("pairs checked:", len(norms))
print("minimum squared norm:", norms[0][0])
print("minimizers:", [(ab, v) for sq, ab, v in norms if sq == norms[0][0]])
# ==> pairs checked: 48
# ==> minimum squared norm: 25
# ==> minimizers: [((-1, 1), (3, -4)), ((1, -1), (-3, 4))]

Closing the global-minimum gap. The brute search above only proves that 25 is the minimum squared norm over the chosen $7 \times 7$ coefficient box. It does not by itself rule out a shorter lattice vector that lives outside the box.

The closure is a finite enumeration. Any nonzero $v \in L$ with $\lVert v \rVert < 5$ would be an integer point $(x, y) \neq (0, 0)$ with $x^2 + y^2 < 25$, and the lattice membership condition is a single residue check. A point $(x, y)$ lies in $L$ iff there exist integers $a, b$ with $x = 2a + 5b$ and $y = 7a + 3b$. Eliminating $a$ from the two equations gives $7x - 2y = 29 b$, equivalently $7x \equiv 2y \pmod{29}$. That direction is only necessity. For the converse, solving the system gives $a = (5y - 3x)/29$ and $b = (7x - 2y)/29$. Both coefficients are integers exactly when 29 divides both numerators, and 29 divides $5y - 3x$ whenever it divides $7x - 2y$, because $2(5y - 3x) = 29x - 5(7x - 2y)$. So the single congruence really is an iff, which is what lets one modulo stand in for solving the system.

The exercise asks for every interior candidate. There are 68 nonzero integer points with $x^2 + y^2 < 25$:

• $x = 0$, with $y \in \{\pm 1, \pm 2, \pm 3, \pm 4\}$: 8 points
• $x \in \{\pm 1, \pm 2\}$, with $y \in \{-4, \dots, 4\}$: 36 points
• $x = \pm 3$, with $y \in \{-3, \dots, 3\}$: 14 points
• $x = \pm 4$, with $y \in \{-2, \dots, 2\}$: 10 points

Applying the residue check to all 68 returns the empty set.

# Strict-interior search: integer points (x, y) != (0, 0) with x^2 + y^2 < 25
# that satisfy the lattice membership condition 7x - 2y ≡ 0 (mod 29).
candidates_interior = []
for x in range(-4, 5):
    for y in range(-4, 5):
        if (x, y) == (0, 0):
            continue
        if x * x + y * y >= 25:
            continue
        if (7 * x - 2 * y) % 29 == 0:
            candidates_interior.append((x, y, x * x + y * y))
print("short lattice points (sq norm < 25):", candidates_interior)
# ==> short lattice points (sq norm < 25): []

That settles strict shortness: no lattice vector has squared norm $< 25$. The boundary set $x^2 + y^2 = 25$ contains exactly twelve integer points ($(\pm 5, 0)$, $(0, \pm 5)$, $(\pm 3, \pm 4)$, $(\pm 4, \pm 3)$). The same residue check picks out which of those are in $L$.

# Boundary search: integer points with x^2 + y^2 == 25 in the lattice.
candidates_boundary = []
for x in range(-5, 6):
    for y in range(-5, 6):
        if x * x + y * y != 25:
            continue
        if (7 * x - 2 * y) % 29 == 0:
            candidates_boundary.append((x, y))
print("lattice points on sq norm 25:", candidates_boundary)
# ==> lattice points on sq norm 25: [(-3, 4), (3, -4)]

The boundary check returns exactly the two vectors found in the brute search, so $\lambda_1(L) = 5$ globally, with minimizers $(\pm 3, \mp 4)$. Minkowski’s first theorem (Chapter 7) is unnecessary for this finite-search proof. It gives a different statement, an existence bound on some short nonzero lattice vector rather than a uniform bound on every lattice vector, and is left for Chapter 7’s general treatment.

Exercise 2

The syndrome $(1, 0, 1)^\top$ read as a binary integer (most significant bit first) is $5$, so the error is at position 5. The weight-1 error vector is $e = (0, 0, 0, 0, 1, 0, 0)$, with the 1 in the fifth coordinate.

For any parity-check matrix $H$, a weight-1 error in coordinate $j$ has syndrome equal to column $j$ of $H$. What the standard Hamming ordering adds is that those three bits can be read directly as the coordinate number, because column $j$ is the binary representation of $j$. For a generic matrix one must instead search for the matching column, and repeated or zero columns can leave a weight-1 error ambiguous or invisible. A full-rank $3 \times 7$ matrix whose seven columns are the seven distinct nonzero 3-bit vectors is a Hamming code up to a column permutation and a change of row basis. The only thing genuinely lost is the convenient indexing.

That indexing convenience is not why the McEliece family, in Chapter 20, uses Goppa codes. McEliece needs a secret structured family that admits an efficient algebraic decoder, while publishing a disguised generator or parity-check matrix that is meant to look like a random one. The decoder is the asset and the disguise is the security argument. Neither is about reading a syndrome as an index.

H = [[int(b) for b in format(j, "03b")] for j in range(1, 8)]  # columns
H = list(zip(*H))  # rows: 3 rows x 7 cols
s = (1, 0, 1)
position = int("".join(str(b) for b in s), 2)
e = [0] * 7
e[position - 1] = 1
print("error position (1-based):", position)
print("error vector:", e)
# ==> error position (1-based): 5
# ==> error vector: [0, 0, 0, 0, 1, 0, 0]

Exercise 3

Exact problems. A reference statement of all three (compare your own version to this, then to Regev’s paper):

• Shortest vector problem (SVP). Input: a basis $B$ of a lattice $L \subset \mathbb{R}^n$. Output: a nonzero lattice vector $v \in L$ of minimum Euclidean norm.
• Closest vector problem (CVP). Input: a basis $B$ of a lattice $L$ and a target $t \in \mathbb{R}^n$. Output: a lattice vector $v \in L$ that minimizes $\lVert v - t \rVert$.
• Learning with errors (LWE), search. Input: a list of pairs $(a_i, b_i)$ where each $a_i \in \mathbb{Z}_q^n$ is uniform and each $b_i = \langle a_i, s \rangle + e_i \pmod q$ for a fixed secret $s \in \mathbb{Z}_q^n$ and small noise $e_i$ drawn from a narrow distribution (typically a discrete Gaussian). Output: the secret $s$.

Decision and gap variants. The exact problems above are not all of what the cryptographic reductions target. Search LWE in particular is the average-case problem Regev’s reduction lands on. $\mathrm{GapSVP}_\gamma$ and $\mathrm{GapCVP}_\gamma$ are promise decision variants of SVP and CVP. Decisional LWE is a distribution-distinguishing variant, not a gap problem, so the three below are not three of a kind.

• $\mathrm{GapSVP}_\gamma$. Input: a basis $B$ of a lattice $L \subset \mathbb{R}^n$ and a threshold $d > 0$, under the promise that $\lambda_1(L) \leq d$ or $\lambda_1(L) > \gamma d$. Output: which of the two cases holds.
• $\mathrm{GapCVP}_\gamma$. Input: a basis $B$, a target $t$, and a threshold $d > 0$, under the promise that $\mathrm{dist}(t, L) \leq d$ or $\mathrm{dist}(t, L) > \gamma d$. Output: which of the two cases holds.
• Decisional LWE. Input: $m$ samples of the form $(a_i, b_i)$ with $a_i$ uniform in $\mathbb{Z}_q^n$. Output: decide whether the samples come from the LWE distribution ($b_i = \langle a_i, s \rangle + e_i \pmod q$ for a fixed secret $s$ and noise $e_i$) or from the uniform distribution on $\mathbb{Z}_q^n \times \mathbb{Z}_q$.

A complete answer also notes that the worst-case-to-average-case reduction (Regev, 2009) targets $\mathrm{GapSVP}_\gamma$ and $\mathrm{SIVP}_\gamma$, at approximation factors $\gamma$ polynomial in $n$, and reaches them through average-case search LWE. It does not target $\mathrm{GapCVP}$. Regev’s decision-to-search lemma assumes a prime $q$ polynomial in $n$ and holds for any fixed error distribution $\chi$. The noise-rate condition belongs to the separate worst-case lattice reduction, not to this one.

Exercise 4

(a) SIDH publishes the images of fixed torsion-point bases under the secret isogeny as part of the public protocol. The Castryck-Decru attack uses those auxiliary torsion-point images, together with Kani’s lemma on isogenies between products of elliptic curves, to glue the protocol’s two elliptic curves into a higher-dimensional abelian surface and recover the secret isogeny. The running time is heuristically polynomial and classical, assuming the endomorphism ring of SIDH’s starting curve is known, and apart from factoring a small number of parameter-dependent integers. The attack is specifically against the SIDH transcript (smooth-degree path-finding plus published torsion images), not against the general supersingular isogeny problem with no auxiliary data.

(b) SQIsign signs by exhibiting a single isogeny between two specific supersingular curves. The procedure has no SIDH-style images of publicly fixed torsion bases under the secret isogeny to feed into Kani’s lemma, so the attack does not transfer.

The claim has to be that specific. Current SQIsign signatures do carry interpolation point images and compact basis-generation hints; what they lack is the particular secret-isogeny leakage SIDH exposed. SQIsign’s central hardness assumption is the supersingular endomorphism-ring problem (recover $\mathrm{End}(E)$ from $E$), which is polynomial-time equivalent to general arbitrary-isogeny finding and to the OneEnd problem, and is not the smooth-degree torsion-leakage form SIDH was instantiated against.

References

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