Appendix D: Solutions for Chapter 23

This page collects solutions and editorial notes for the exercises in Chapter 23: SQIsign in a toy setting. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

The fuller versions of these routines are in the sqisign package under solutions/ch23-sqisign. From a clone of the companion repository, pytest tests/ch23 runs its suite. Appendix C has the setup.

Exercise 1

In $B_{p, \infty}$ at $p \equiv 3 \pmod 4$ the rules are $i^2 = -1$, $j^2 = -p$, and $k = ij = -ji$. Anticommuting the units fixes the six cross products, and the two involving both $j$ and $k$ are the ones that carry the prime:

Product	Value	Product	Value
$ij$	$k$	$ji$	$-k$
$ik$	$-j$	$ki$	$j$
$jk$	$p \cdot i$	$kj$	$-p \cdot i$

Expanding $\alpha = 2 + 3i + j$ against $\beta = 1 - i + k$ term by term with those substitutions, at $p = 431$:

$$\alpha\beta = 5 + 432\,i - 2\,j + 3\,k, \qquad \beta\alpha = 5 - 430\,i + 4\,j + k.$$

from fractions import Fraction

p = 431

def quat(a, b, c, d):
    return (Fraction(a), Fraction(b), Fraction(c), Fraction(d))

def quat_mul(x, y, p):
    a, b, c, d = x
    e, f, g, h = y
    return (a*e - b*f - p*c*g - p*d*h,
            a*f + b*e + p*c*h - p*d*g,
            a*g + c*e - b*h + d*f,
            a*h + d*e + b*g - c*f)

alpha = quat(2, 3, 1, 0)   # 2 + 3i + j
beta = quat(1, -1, 0, 1)   # 1 - i + k
ab = quat_mul(alpha, beta, p)
ba = quat_mul(beta, alpha, p)
print([int(t) for t in ab])
# ==> [5, 432, -2, 3]
print([int(t) for t in ba])
# ==> [5, -430, 4, 1]
print(ab[0] == ba[0], ab[1:] == ba[1:])
# ==> True False

The scalar parts agree at 5 and all three of the $i$, $j$, $k$ parts differ, which is what the exercise asks you to confirm. Both scalars come from $ae - bf = 2 \cdot 1 - 3 \cdot (-1)$. The two terms that could have contributed a multiple of $p$ are $-p\,cg$ and $-p\,dh$, and each vanishes here, because $\beta$ carries no $j$ component and $\alpha$ carries no $k$ component. The reduced trace is $2a$ in both orderings, so equal scalar parts is equal traces, which is the cyclic identity $\mathrm{trd}(\alpha\beta) = \mathrm{trd}(\beta\alpha)$.

The $i$ coefficient is where the table earns its keep. The gap between $432$ and $-430$ is $862 = 2p$, and it is one product: $\alpha$‘s $j$ against $\beta$‘s $k$ contributes $jk = +p\,i$ in one ordering and $kj = -p\,i$ in the other. Get that one sign backwards and both answers move by $2p$ while every other component stays put, so the trace check still passes and the error survives.

Exercise 2

The standard maximal order $\mathcal{O}_0$ at $p \equiv 3 \pmod 4$ has $\mathbb{Z}$-basis $\{1,\, i,\, (i+j)/2,\, (1+k)/2\}$ (Chapter 23). Writing $\alpha = a + bi + cj + dk$, the chapter’s coordinate test is: $\alpha \in \mathcal{O}_0$ iff $2c$, $2d$, $b - c$, and $a - d$ are all integers. The $\mathcal{O}_0$-coordinates $(x, y, z, w)$ in $\alpha = x + yi + z\frac{i+j}{2} + w\frac{1+k}{2}$ are then $z = 2c$, $w = 2d$, $y = b - c$, $x = a - d$.

(a) $(2 + j)/3 = \tfrac{2}{3} + \tfrac{1}{3} j$, so $c = 1/3$ and $2c = 2/3 \notin \mathbb{Z}$. Not in $\mathcal{O}_0$.

(b) $(1 + i + j + k)/2$ has $a = b = c = d = 1/2$. Then $2c = 2d = 1$ and $b - c = a - d = 0$, all integers, so it is in $\mathcal{O}_0$. Its coordinates are $(x, y, z, w) = (0, 0, 1, 1)$, since $\tfrac{i+j}{2} + \tfrac{1+k}{2} = \tfrac12 + \tfrac{i}{2} + \tfrac{j}{2} + \tfrac{k}{2}$.

(c) $i + (1 + k)/2$ has $a = 1/2$, $b = 1$, $c = 0$, $d = 1/2$. Then $2c = 0$, $2d = 1$, $b - c = 1$, $a - d = 0$, all integers, so it is in $\mathcal{O}_0$ with coordinates $(0, 1, 0, 1)$: it is exactly $1 \cdot i + 1 \cdot (1+k)/2$.

(d) $j/2 = \tfrac{1}{2} j$ has $b = 0$, $c = 1/2$. Then $2c = 1 \in \mathbb{Z}$ but $b - c = -1/2 \notin \mathbb{Z}$: the half-integer on $j$ must be carried with $i$, as $(i+j)/2$, not on its own. Not in $\mathcal{O}_0$.

Exercise 3

The supersingular $j$-invariant count in characteristic $p$ is $\lfloor p/12 \rfloor + \varepsilon$, with $\varepsilon$ set by $p \bmod 12$. At $p = 83$, $83 \bmod 12 = 11$, which gives $\varepsilon = 2$ and a count of $6 + 2 = 8$.

print(83 % 12, 83 // 12 + 2)
# ==> 11 8

Two things about the run are worth reporting, and both differ from what a reader might guess.

The base curve’s $j$-invariant is not $1728$. It is $1728 \bmod 83 = 68$, so BFS starts from $j = 68$, exactly as the chapter’s $p = 431$ run starts from $1728 \bmod 431 = 4$.

The search finishes much faster than at $p = 431$. Walking degree-2 and degree-3 edges from $E_0: y^2 = x^3 + x$ over $\mathbb{F}_{83^2}$, the frontier sizes are 1, 3, 4: all eight $j$-invariants are reached at depth 2, and the diameter of the combined graph is 2. The graph is small enough that almost everything is a neighbour of a neighbour, so there is no room for the four or five levels the $p = 431$ graph needs. A correct implementation prints exactly eight distinct values:

$$0,\quad 17,\quad 28,\quad 50,\quad 67,\quad 68,\quad 38 + 17i,\quad 38 - 17i.$$

Six of the eight lie in $\mathbb{F}_{83}$ and the last two do not. They are a Frobenius-conjugate pair, $38 \pm 17i$ with $-17 \equiv 66 \pmod{83}$, which is the pair $\{j, j^p\}$ that Deuring’s correspondence sends to a single conjugacy class of maximal orders. The chapter’s refinement of the theorem is visible in an eight-vertex graph you can print.

Exercise 4

Signature lengths do not grow, and the exercise is worth running rather than reasoning about, because the natural guess is wrong. Measured on the shipped package at $p = 431$ with the alice key, signing six messages at each setting:

Challenge walk length	Signature path lengths
3	3, 2, 3, 2, 2, 2
5	2, 3, 3, 2, 2, 2
7	2, 3, 2, 2, 2, 2

The reason is that the challenge walk and the signature are measuring different things. A longer challenge walk lands on a different $E_{\mathsf{chal}}$, not a farther one: after a few steps the walk is somewhere effectively arbitrary in a 37-vertex graph, and going further does not push it away from $E_{\mathsf{pk}}$. The signature is then a shortest path found by BFS, so its length is bounded by the diameter of the graph, which is 4 at $p = 431$. That bound does not depend on the challenge walk at all.

Verification still succeeds, on one condition: signing and verification must read the same walk length, because the verifier recomputes $E_{\mathsf{chal}}$ from scratch. Change CHALLENGE_WALK_LENGTH and rerun tests/ch23/test_sqisign_roundtrip.py and the round trip holds. Sign at length 5 and verify at length 3 and verify returns False, because the verifier walks to a different challenge curve and the transmitted path lands nowhere near $E_{\mathsf{pk}}$. That asymmetry, not the signature size, is what the exercise exposes.

The round-2 SQIsign parameter sets fixed the challenge isogeny degree at $D_{\mathsf{chl}} = 2^f$ with $f \approx 2\lambda$, and the challenge space at $2^{e_{\mathsf{chl}}}$ with $e_{\mathsf{chl}} \approx \lambda$ (The SQIsign Team, 2025, sec. 10.2); version 3.0 shortens the challenge walk to length $\lambda$ and gives the response odd degree, the one cryptographically relevant change between the rounds (The SQIsign Team, 2026, sec. 1.4). Modifying either in the toy is a structural exploration, not a deployable change.

Exercise 5

ML-DSA’s public key is a 32-byte seed $\rho$ for the matrix $\mathbf{A}$ plus the vector $\mathbf{t}_1$ of $k$ ring elements in $R_q = \mathbb{Z}_{8380417}[x]/(x^{256} + 1)$. ML-DSA-44 has $(k, \ell) = (4, 4)$, and $\mathbf{t}_1$ keeps 10 bits per coefficient after $d = 13$ bits are dropped, so each ring element packs into $256 \cdot 10 / 8 = 320$ bytes. That gives $32 + 4 \cdot 320 = 1{,}312$ bytes, and the explicit $\mathbf{t}_1$ data is all but 32 of them (Tables 1 and 2 in National Institute of Standards and Technology, 2024). Note the parameter set: ML-DSA-44 is FIPS 204 security category 2, while SQIsign level 1 targets category 1, so this comparison crosses categories.

SQIsign’s public key is one curve. The specification encodes a curve by its Montgomery coefficient $A \in \mathbb{F}_{p^2}$, and appends a one-byte hint used to regenerate a torsion basis faster during verification. At NIST level 1 the round-3 prime is $p = 3 \cdot 2^{324} - 1$, which is 326 bits, so each $\mathbb{F}_p$ element takes $\lceil 326/8 \rceil = 41$ bytes and $A$ takes 82. With the hint byte that is the 83-byte public key (The SQIsign Team, 2026, sec. 5.2 and Chapter 6). The round-2 prime $5 \cdot 2^{248} - 1$ had 251 bits, 32-byte elements and a 65-byte key by the same arithmetic (The SQIsign Team, 2025).

The asymmetry comes from what each scheme has to commit to. ML-DSA commits to enough lattice structure to make forgery hard, which forces a vector with hundreds of coefficients per security level. SQIsign commits only to the endpoint of an isogeny walk, in a graph with about $p/12$ vertices. The secret is the path, not the endpoint. A single point in that graph is one $\mathbb{F}_{p^2}$ element however large the graph is, which is why the key does not grow with the security level the way a lattice key does. Level 3 costs 129 bytes and level 5 costs 169.

The round-3 specification, version 3.0 of 1 September 2026, is the current public source for every SQIsign figure on this page; its parameter increase over round 2 is the response to the heuristic $p^{1/3+o(1)}$ endomorphism-ring algorithm of July 2026, which Chapter 23’s cryptanalysis section covers (The SQIsign Team, 2026).

References

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

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