Chapter 23: SQIsign in a toy setting

Chapter 22 built isogenies as graph walks: each vertex was a supersingular j-invariant in $\mathbb{F}_{p^2}$, each edge a degree-$\ell$ isogeny, and Velu’s formulas computed the codomain. SIDH used this graph for key exchange and was broken in 2022 because it published torsion-point images.

This chapter builds SQIsign, an isogeny-based signature scheme that survives the Castryck-Decru attack because it never publishes torsion-point images taken under its secret isogeny. The signature is an isogeny itself. The secret key is a maximal order in a quaternion algebra. The connection between curves and orders is Deuring’s correspondence, stated as a preview in Chapter 22 and developed here in detail.

The round-3 SQIsign specification, version 3.0 of 1 September 2026, has an 83-byte public key and a 200-byte signature at NIST level 1 (Table 1 in The SQIsign Team, 2026). The round-2 specification of July 2025 had 65 and 148 bytes (Table 1 in The SQIsign Team, 2025), and the round-1 submission listed 64 and 177 (Table 1 in Basso et al., 2023); the round-3 increase is the response to a July 2026 endomorphism-ring algorithm, covered in the cryptanalysis section below. The combined 283 bytes is roughly $13\times$ smaller than ML-DSA-44 at 3,732 B and $28\times$ smaller than SLH-DSA-128s at 7,888 B. Both comparisons are public key plus signature, not signature alone. Those are the smallest ML-DSA parameter set and the smallest-signature SLH-DSA parameter set respectively (ML-DSA-44 pk 1,312 B + sig 2,420 B; SLH-DSA-128s pk 32 B + sig 7,856 B).

ML-DSA-44 is NIST security category 2, so this is a low-end size comparison rather than an exact same-category one. The two standards carry the categories and sizes: FIPS 204 Table 1 puts ML-DSA-44 at category 2 and its Table 2 gives the sizes, and FIPS 205 Table 2 puts SLH-DSA-128s at category 1 (National Institute of Standards and Technology, 2024a, 2024b). SQIsign level 1 also targets category 1. SQIsign is not FIPS-standardized: it advanced to the third round of NIST’s Additional Digital Signatures process in May 2026 (National Institute of Standards and Technology, 2026). Its round-3 specification is the source of every SQIsign figure in this chapter unless the text labels one as round 2 (The SQIsign Team, 2026).

The tradeoff is signing speed (about 28 ms for the round-3 optimized 64-bit Intel implementation (The SQIsign Team, 2026)) against a newer assumption base. The endomorphism ring problem traces to Kohel 1996 in its endomorphism-ring form and to Cervino 2004 in the quaternion-order form (Cerviño, 2004; Kohel, 1996). Round-2 SQIsign proves EUF-CMA security, the game from Chapter 6, under a hint-augmented variant of that problem. The round-2 revision also removed the ad hoc assumptions the round-1 zero-knowledge argument had needed (The SQIsign Team, 2025, sec. 1.1 and 1.3).

The chapter ships a toy at $p = 431$ that demonstrates the keygen-sign-verify flow. The toy substitutes a brute-force breadth-first search for the quaternion-side machinery the real scheme uses to find connecting isogenies. The substitution is flagged at every relevant point.

Not reference-compliant

The toy runs at $p = 431$ instead of the round-3 level-1 prime $p = 3 \cdot 2^{324} - 1$, and it searches the isogeny graph directly instead of working on the quaternion side. It does not attempt byte-for-byte compatibility with the NIST additional-signatures SQIsign submission. The suite at tests/ch23 covers round-trip correctness and quaternion arithmetic, not reference-KAT compliance. The README of the solutions/ch23-sqisign package states the full compliance gap.

Signing with secret paths

ECDSA and ML-DSA both produce signatures from algebraic objects (a discrete log or a short vector). SQIsign produces a signature from an isogeny.

The signer’s secret key is a generator of an ideal connecting $\mathcal{O}_0$ to a secret maximal order $\mathcal{O}_{\mathsf{sec}}$ in the quaternion algebra $B_{p,\infty}$. The public key is the supersingular elliptic curve $E_{\mathsf{sec}}$ associated to $\mathcal{O}_{\mathsf{sec}}$ via Deuring’s correspondence. Real SQIsign is the Fiat-Shamir transform of a three-move identification protocol (De Feo et al., 2020, sec. 3; The SQIsign Team, 2025, sec. 1.2).

The signer first computes a commitment isogeny $\phi_{\mathsf{com}}: E_0 \to E_{\mathsf{com}}$ to a random curve. Hashing the public key, the commitment curve $E_{\mathsf{com}}$, and the message produces a challenge that defines an isogeny $\phi_{\mathsf{chl}}: E_{\mathsf{sec}} \to E_{\mathsf{chl}}$ from the public-key curve. The response is an isogeny $\phi_{\mathsf{rsp}}: E_{\mathsf{com}} \to E_{\mathsf{chl}}$ computed from the secret quaternion-side data. The signer knows $\mathrm{End}(E_{\mathsf{com}})$ from the commitment, and knows $\mathrm{End}(E_{\mathsf{chl}})$ because it knows $\mathrm{End}(E_{\mathsf{sec}})$. It can therefore connect $E_{\mathsf{com}}$ to $E_{\mathsf{chl}}$ without revealing $\mathcal{O}_{\mathsf{sec}}$.

The signature transmits the challenge and a compact description of $\phi_{\mathsf{rsp}}$. Verification checks that $\phi_{\mathsf{rsp}}$ runs from $E_{\mathsf{com}}$ to $E_{\mathsf{chl}}$ with the right degree, closing the commitment-challenge-response square. One condition is doing real work in that check: $\phi_{\mathsf{chl}}$ must not be a sub-isogeny of $\phi_{\mathsf{rsp}}$. Without it, a prover who never knew $\mathrm{End}(E_{\mathsf{com}})$ could commit through a random isogeny out of $E_{\mathsf{sec}}$, then answer with its dual composed with the challenge (The SQIsign Team, 2025, sec. 1.2 and 10.1). Chapter 33 develops the sigma-protocol and Fiat-Shamir machinery in full.

This chapter’s toy collapses that structure: it hashes the message and public key directly to a challenge curve $E_{\mathsf{chal}}$, then finds a connecting isogeny $\sigma: E_{\mathsf{chal}} \to E_{\mathsf{sec}}$ by breadth-first search. There is no commitment phase and no zero-knowledge property. The toy demonstrates the keygen-sign-verify data flow, not the security construction. The toy verifier recomputes $E_{\mathsf{chal}}$ from the message and public key, walks $\sigma$ from $E_{\mathsf{chal}}$, and checks that the resulting curve has the same $j$-invariant as $E_{\mathsf{sec}}$. The signer’s advantage over an attacker is the secret order. Knowing $\mathcal{O}_{\mathsf{sec}}$ moves the search off the curves and onto the quaternion side, where a connecting ideal is cheap to find and cheap to translate back (The SQIsign Team, 2025, sec. 3.2). Without the secret, finding $\sigma$ requires solving the supersingular isogeny path problem, conjectured to be hard (Delfs & Galbraith, 2016).

Figure 23.1 shows the three walks that make up a SQIsign signature at the toy parameters of this chapter. The keygen walk is secret. The challenge walk is derived from the message hash and is therefore public. The connecting isogeny from $E_{\mathsf{chal}}$ to the public-key curve is the signature.

Figure 23.1. The three walks that make up a SQIsign signature. The keygen walk from $E_0$ to $E_{\mathsf{pk}}$ is the signer's secret (dashed purple). The challenge walk from $E_0$ to $E_{\mathsf{chal}}$ is derived from the hash of the message and public key. Anyone can reproduce it (solid blue). The signature $\sigma$ is an isogeny from $E_{\mathsf{chal}}$ to $E_{\mathsf{pk}}$ (solid amber) and is what the signer transmits. This figure shows only the chapter's simplified toy flow ($\sigma: E_{\mathsf{chal}} \to E_{\mathsf{pk}}$, found by BFS at $p = 431$ from public data alone, which makes the toy forgeable by anyone who can run that search and is pedagogical-only). Real SQIsign has a different commitment-challenge-response geometry: the response isogeny runs $E_{\mathsf{com}} \to E_{\mathsf{chl}}$ and is drawn on the quaternion side from a distribution that does not leak the secret.

Finding a path in the isogeny graph

Before the algebra, the computational problem. At $p = 431$ the supersingular graph has 37 vertices ($j$-invariants in $\mathbb{F}_{431^2}$). Each vertex has up to three degree-2 neighbours and up to four degree-3 neighbours. The graph is connected (a classical consequence of strong approximation in $B_{p,\infty}$ (Main Theorem 28.5.3 in Voight, 2021)) and Pizer proved it is Ramanujan, so any two $j$-invariants are joined by a short isogeny chain (Pizer, 1990).

To find a path from $E_0: y^2 = x^3 + x$ to a target curve, enumerate the kernels of small-degree isogenies on the current curve, apply Velu’s formulas to each, and run breadth-first search.

from collections import deque

p = 431

def fp2_add(x, y, p):
    return ((x[0]+y[0]) % p, (x[1]+y[1]) % p)
def fp2_sub(x, y, p):
    return ((x[0]-y[0]) % p, (x[1]-y[1]) % p)
def fp2_mul(x, y, p):
    return ((x[0]*y[0]-x[1]*y[1]) % p, (x[0]*y[1]+x[1]*y[0]) % p)
def fp2_inv(x, p):
    n = (x[0]*x[0]+x[1]*x[1]) % p
    inv = pow(n, -1, p)
    return ((x[0]*inv) % p, ((-x[1])*inv) % p)
def fp2_sqr(x, p):
    return ((x[0]*x[0]-x[1]*x[1]) % p, (2*x[0]*x[1]) % p)
def fp2_neg(x, p):
    return ((-x[0]) % p, (-x[1]) % p)

# 2-torsion: roots of x^3 + ax + b = 0 in F_{p^2}.
def two_torsion(a, b, p):
    pts = []
    for x_re in range(p):
        x = (x_re, 0)
        x3 = fp2_mul(fp2_sqr(x, p), x, p)
        rhs = fp2_add(fp2_add(x3, fp2_mul(a, x, p), p), b, p)
        if rhs == (0, 0):
            pts.append((x, (0, 0)))
    if len(pts) < 3:
        for x_re in range(p):
            for x_im in range(1, p):
                x = (x_re, x_im)
                x3 = fp2_mul(fp2_sqr(x, p), x, p)
                rhs = fp2_add(fp2_add(x3, fp2_mul(a, x, p), p), b, p)
                if rhs == (0, 0):
                    pts.append((x, (0, 0)))
                    if len(pts) >= 3:
                        break
            if len(pts) >= 3:
                break
    return pts

a0, b0 = (1, 0), (0, 0)
print(len(two_torsion(a0, b0, p)))
# ==> 3

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch23/, one file per block. Appendix C covers the clone and the environment they run on.

The base curve $E_0: y^2 = x^3 + x$ has three non-identity 2-torsion points at $x = 0$, $x = i$, and $x = -i$ in $\mathbb{F}_{431^2}$. The cubic factors as $x(x^2+1)$, and $\sqrt{-1}$ lives in $\mathbb{F}_{p^2}$ because $p \equiv 3 \pmod 4$. Each generates a kernel for a distinct degree-2 isogeny, and the same enumeration works on every curve along the walk, applied to its own coefficients $(a, b)$.

The complete BFS produces a chain of degree-2 and degree-3 isogenies connecting any two $j$-invariants.

Quaternion algebras and the Deuring correspondence

The algebra $B_{p,\infty}$

For a prime $p \equiv 3 \pmod 4$, a convenient presentation of the quaternion algebra $B_{p,\infty}$ is the four-dimensional $\mathbb{Q}$-algebra with basis $\{1, i, j, k\}$ and multiplication rules

$$i^2 = -1, \quad j^2 = -p, \quad k = ij = -ji.$$

Using $ji = -ij$ to anticommute factors, $k^2 = (ij)(ij) = i(ji)j = -i(ij)j = -i^2 j^2 = -(-1)(-p) = -p$. The same anticommutation fixes every remaining product of two distinct basis units (Voight, 2021):

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

Reading across each row gives the whole content of non-commutativity here: reversing two distinct basis units flips a sign and changes nothing else.

A general element is $\alpha = a + bi + cj + dk$ with $a, b, c, d \in \mathbb{Q}$. The conjugate is $\overline{\alpha} = a - bi - cj - dk$. The reduced trace and reduced norm are

$$\mathrm{trd}(\alpha) = \alpha + \overline{\alpha} = 2a, \qquad \mathrm{nrd}(\alpha) = \alpha \overline{\alpha} = a^2 + b^2 + p c^2 + p d^2.$$

The reduced norm is multiplicative: $\mathrm{nrd}(\alpha \beta) = \mathrm{nrd}(\alpha)\mathrm{nrd}(\beta)$ (Voight, 2021, sec. 3.3). The notation “ramified at $p$ and $\infty$” means $B_{p,\infty}$ does not split over the $p$-adic numbers $\mathbb{Q}_p$ or the reals $\mathbb{R}$. Up to isomorphism, $B_{p,\infty}$ is the unique quaternion algebra over $\mathbb{Q}$ with this ramification set (Theorem 14.6.1 in Voight, 2021).

Maximal orders

An order in $B_{p,\infty}$ is a $\mathbb{Z}$-lattice of rank 4 that is also a subring containing $1$. An order is maximal if no order properly contains it. Every maximal order has reduced discriminant $p$, matching the discriminant of the algebra (Theorem 15.5.5 in Voight, 2021).

For $p \equiv 3 \pmod 4$, the standard maximal order is

$$\mathcal{O}_0 = \mathbb{Z} \,+\, \mathbb{Z} i \,+\, \mathbb{Z}\,\frac{i+j}{2} \,+\, \mathbb{Z}\,\frac{1+k}{2}.$$

This is the order the SQIsign specification uses (The SQIsign Team, 2026, sec. 2.2). Closure under multiplication relies on $p \equiv 3 \pmod 4$. Direct expansion gives $\big(\frac{i+j}{2}\big)^2 = -\frac{1+p}{4}$ and $\big(\frac{1+k}{2}\big)^2 = \frac{1-p}{4} + \frac{k}{2} = -\frac{1+p}{4} + \frac{1+k}{2}$, and the chapter’s basis-coordinate test confirms membership in $\mathcal{O}_0$ when $(1+p)/4 \in \mathbb{Z}$, that is when $4 \mid p+1$. The order is maximal because its reduced discriminant is $p$, exactly as for the order $\mathbb{Z}\langle 1, i, (1+j)/2, (i+k)/2 \rangle$ that Voight writes down, which is conjugate to this one by $1 + i$ (Example 15.5.7 and Theorem 15.5.5 in Voight, 2021). The cross products are $\big(\frac{i+j}{2}\big)\big(\frac{1+k}{2}\big) = \frac{1+p}{4}\, i$ and $\big(\frac{1+k}{2}\big)\big(\frac{i+j}{2}\big) = -\frac{1+p}{4}\, i + \frac{i+j}{2}$. Both land in $\mathcal{O}_0$ under the same congruence. At $p = 431$, $(1+p)/4 = 108$.

A left $\mathcal{O}_0$-ideal is a $\mathbb{Z}$-lattice of rank 4 closed under left multiplication by $\mathcal{O}_0$. The principal left ideal generated by $\alpha \in B_{p,\infty}^\times$ is $\mathcal{O}_0 \alpha$, whose reduced norm equals $\mathrm{nrd}(\alpha)$ (Voight, 2021, sec. 16.3).

Deuring’s correspondence

Chapter 22 stated Deuring’s theorem as a preview. Restated here:

Theorem (Deuring 1941 (Deuring, 1941)). The map $E \mapsto \mathrm{End}(E)$ induces a bijection between supersingular $j$-invariants over $\overline{\mathbb{F}_p}$ taken up to Galois conjugacy, that is the pairs $\{j, j^p\}$, and conjugacy classes of maximal orders in $B_{p,\infty}$.

Chapter 22 previewed this form. Two things it leaves out matter here. First, the pairing degenerates. When $j \in \mathbb{F}_p$ the Frobenius pair collapses to a single element, so the conjugacy class corresponds to one curve rather than two. That happens exactly when the unique two-sided ideal of reduced norm $p$ is principal (Lemma 42.4.1 in Voight, 2021). Second, SQIsign uses the operative basepoint-dependent form. Fix $E_0$ with $\mathrm{End}(E_0) \cong \mathcal{O}_0$. Isomorphism classes of supersingular curves then correspond to the left ideal classes of $\mathcal{O}_0$ (Corollary 42.3.7 in Voight, 2021). Left $\mathcal{O}_0$-ideals correspond to isogenies out of $E_0$, and the right order of an ideal is the endomorphism ring of the target curve (Proposition 2.1.2 in Leroux, 2022).

The endomorphism ring of any supersingular curve is therefore a maximal order. For the special curve $E_0: y^2 = x^3 + x$ when $p \equiv 3 \pmod 4$, the four endomorphisms

$$\mathrm{id},\quad \iota: (x, y) \mapsto (-x, iy),\quad \pi: (x, y) \mapsto (x^p, y^p),\quad \iota \pi$$

span the suborder $\mathbb{Z}\langle 1, \iota, \pi, \iota\pi \rangle$ of $\mathrm{End}(E_0)$ at index 4. Here $\iota$ is the CM endomorphism by $\mathbb{Z}[i]$ and $\pi$ is the $p$-power Frobenius. The full endomorphism ring requires the half-integer combinations $(\iota+\pi)/2$ and $(1+\iota\pi)/2$, which act as integer maps even though their formal coordinates carry denominator 2. The test for which halves exist is the 2-torsion: an endomorphism is divisible by 2 exactly when it kills $E_0[2] = \{\infty, (0,0), (i,0), (-i,0)\}$, because it then factors through $[2]$. Since $i^p = -i$ when $p \equiv 3 \pmod 4$, both $\pi$ and $\iota$ swap $(i,0)$ with $(-i,0)$, so $\iota+\pi$ and $1+\iota\pi$ send every 2-torsion point to $\infty$, while $(1+\pi)(i,0) = (i,0) + (-i,0) = (0,0)$, so $(1+\pi)/2$ is not an endomorphism of this model. The relations

$$\iota^2 = [-1], \qquad \pi^2 = [-p], \qquad \iota \pi = -\pi \iota$$

match those of $B_{p,\infty}$ under $\iota \mapsto i$, $\pi \mapsto j$, $\iota \pi \mapsto k$ (Theorem V.3.1 and Exercise III.3.18c in Silverman, 2009).

The relation $\pi^2 = [-p]$ holds at the level of endomorphisms. The characteristic polynomial of the $p$-power Frobenius on a supersingular curve with trace zero is $T^2 + p$, which gives $\pi^2 + [p] = 0$ over $\overline{\mathbb{F}_p}$ (Theorem V.2.3.1 in Silverman, 2009). The construction section below checks it pointwise at $p = 431$.

Under the isomorphism $\mathrm{End}(E_0) \otimes \mathbb{Q} \cong B_{p,\infty}$, the lattice $\mathbb{Z}\langle 1, \iota, (\iota+\pi)/2, (1+\iota\pi)/2 \rangle$ maps to $\mathcal{O}_0$. The constructive direction of Deuring’s correspondence at $E_0$ is therefore explicit (Voight, 2021, sec. 42.2).

KLPT, and what Round 2 replaced it with

KLPT (Kohel, Lauter, Petit, Tignol, 2014 (Kohel et al., 2014)) solves a specific problem in the quaternion algebra. Given a left $\mathcal{O}_1$-ideal $I$ with right order $\mathcal{O}_2$ and a sufficiently smooth target norm $N$, the algorithm outputs an equivalent left ideal $J = I \cdot \beta$ in the same left ideal class with $\mathrm{nrd}(J) = N$. Under the algorithmic Deuring correspondence (Leroux, 2022, sec. 2.2), $J$ corresponds to an isogeny of degree $N$ between the curves $E_1$ and $E_2$ with $\mathrm{End}(E_i) = \mathcal{O}_i$.

KLPT is a probabilistic algorithm: under standard heuristic assumptions on the distribution of primes represented by the relevant quadratic forms, it runs in expected time polynomial in $\log p$, combining a Cornacchia-style two-square decomposition with strong approximation in $B_{p,\infty}$ (Kohel et al., 2014). Both ingredients work entirely on the quaternion side; KLPT never touches the curves themselves.

Round-1 SQIsign signed this way. Round 2 does not, and the specification removed the KLPT material outright rather than revising it. Prescribing a smooth norm is what made the round-1 response awkward: the resulting distribution was sampled in an ad hoc way that was hard to analyze, and it forced the degree of $\phi_{\mathsf{rsp}}$ high enough to dominate the signing cost. Round 2 instead draws a quaternion of bounded norm from the lattice $I_{\mathsf{com}} \cap I_{\mathsf{sk}} I_{\mathsf{chl}}$. That is a uniform draw from the isogenies $E_{\mathsf{com}} \to E_{\mathsf{chl}}$ below a degree bound, and the result is carried as interpolation data instead of as a smooth path. Translating that ideal into its isogeny needs isogenies between abelian surfaces, the two-dimensional analogue of elliptic curves (The SQIsign Team, 2025, sec. 1.3 and 4.4).

Both versions do their work on the quaternion side, and that is what the toy gives up. For the toy at $p = 431$, the supersingular graph has 37 vertices and breadth-first search on the graph itself solves the same connecting-isogeny problem in time $O(p)$.

Building SQIsign from scratch

Quaternion arithmetic

Elements of $B_{p,\infty}$ are 4-tuples of rationals. Integer-coefficient quaternions suffice for the construction; the maximal order needs half-integers, handled below with Python’s Fraction.

from fractions import Fraction

p = 431

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

def quat_add(x, y):
    return (x[0]+y[0], x[1]+y[1], x[2]+y[2], x[3]+y[3])

def quat_neg(x):
    return (-x[0], -x[1], -x[2], -x[3])

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

def quat_conj(x):
    return (x[0], -x[1], -x[2], -x[3])

def quat_norm(x, p):
    a, b, c, d = x
    return a*a + b*b + p*c*c + p*d*d

i = quat(0, 1, 0, 0)
j = quat(0, 0, 1, 0)
k = quat(0, 0, 0, 1)

print(quat_mul(i, i, p)[0])
# ==> -1
print(quat_mul(j, j, p)[0])
# ==> -431
print(quat_mul(i, j, p))
# ==> (Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(1, 1))
print(quat_mul(j, i, p))
# ==> (Fraction(0, 1), Fraction(0, 1), Fraction(0, 1), Fraction(-1, 1))
print(quat_norm(quat(2, 3, 1, 0), p))
# ==> 444

The basis relations $i^2 = -1$, $j^2 = -p$, $ij = k$, $ji = -k$ are verified by direct evaluation. The norm of $\alpha = 2 + 3i + j$ is $4 + 9 + 431 = 444$, matching the formula $a^2 + b^2 + pc^2 + pd^2$.

The maximal order $\mathcal{O}_0$

For $p \equiv 3 \pmod 4$, the basis $\{1,\, i,\, (i+j)/2,\, (1+k)/2\}$ generates $\mathcal{O}_0$. Membership reduces to a coordinate check: $\alpha = a + bi + cj + dk$ lies in $\mathcal{O}_0$ if and only if $2c$, $2d$, $b-c$, and $a-d$ are all integers.

from fractions import Fraction

def in_O0(x):
    a, b, c, d = x
    u0 = a - d
    u1 = b - c
    u2 = 2 * c
    u3 = 2 * d
    return all(u.denominator == 1 for u in (u0, u1, u2, u3))

# (i + j) / 2 lies in O_0; j/2 alone does not.
half_i_plus_j = (Fraction(0), Fraction(1, 2), Fraction(1, 2), Fraction(0))
half_j = (Fraction(0), Fraction(0), Fraction(1, 2), Fraction(0))
print(in_O0(half_i_plus_j))
# ==> True
print(in_O0(half_j))
# ==> False

# i and j are also in O_0 (j = 2*(i+j)/2 - i).
print(in_O0((Fraction(0), Fraction(1), Fraction(0), Fraction(0))))
# ==> True
print(in_O0((Fraction(0), Fraction(0), Fraction(1), Fraction(0))))
# ==> True

The lattice $\mathcal{O}_0$ contains the suborder $\mathbb{Z}\langle 1, i, j, k\rangle$ with index 4. The half-integer combinations $(i+j)/2$ and $(1+k)/2$ enlarge the suborder to a maximal one. Discriminants confirm the index: $\mathbb{Z}\langle 1, i, j, k\rangle$ has discriminant $16p^2$ and $\mathcal{O}_0$ has discriminant $p^2$, with $\mathrm{disc}(\mathrm{sub}) = [\mathcal{O}_0 : \mathrm{sub}]^2 \cdot \mathrm{disc}(\mathcal{O}_0)$ giving $16 = 4^2$ (Voight, 2021, sec. 15.5).

The endomorphisms of $E_0$

The CM endomorphism $\iota$ uses the embedding of $\mathbb{Z}[i]$ into $\mathrm{End}(E_0)$. In $\mathbb{F}_{p^2} = \mathbb{F}_p[i]/(i^2+1)$ the field element $i$ is the pair $(0, 1)$. The endomorphism is

$$\iota(x, y) = (-x, i \cdot y), \qquad \iota(\mathcal{O}) = \mathcal{O}.$$

The relation $\iota^2 = [-1]$ holds pointwise: $\iota(\iota(x, y)) = \iota(-x, iy) = (x, i \cdot iy) = (x, -y) = -(x, y)$.

p = 431

def fp2_add(x, y, p):
    return ((x[0]+y[0]) % p, (x[1]+y[1]) % p)
def fp2_sub(x, y, p):
    return ((x[0]-y[0]) % p, (x[1]-y[1]) % p)
def fp2_mul(x, y, p):
    return ((x[0]*y[0]-x[1]*y[1]) % p, (x[0]*y[1]+x[1]*y[0]) % p)
def fp2_neg(x, p):
    return ((-x[0]) % p, (-x[1]) % p)
def fp2_pow(x, n, p):
    if n == 0: return (1, 0)
    r = (1, 0)
    base = x
    while n:
        if n & 1: r = fp2_mul(r, base, p)
        base = fp2_mul(base, base, p)
        n >>= 1
    return r

def iota(P, p):
    if P is None: return None
    x, y = P
    return (fp2_neg(x, p), fp2_mul((0, 1), y, p))

def pi_frob(P, p):
    if P is None: return None
    x, y = P
    return (fp2_pow(x, p, p), fp2_pow(y, p, p))

# A point on E_0: y^2 = x^3 + x at p = 431.
G = ((13, 0), (290, 0))

# Verify iota^2 = [-1] on G.
once = iota(G, p)
twice = iota(once, p)
print(twice == (G[0], fp2_neg(G[1], p)))
# ==> True

# Verify that iota and pi anticommute on G: iota(pi(G)) = -pi(iota(G)).
left = iota(pi_frob(G, p), p)
right = pi_frob(iota(G, p), p)
neg_right = (right[0], fp2_neg(right[1], p))
print(left == neg_right)
# ==> True

The relation $\pi^2 = [-p]$ admits a pointwise check on $\mathbb{F}_{p^2}$-rational points. The group $E_0(\mathbb{F}_{p^2})$ has order $(p+1)^2 = 432^2$ and is isomorphic to $(\mathbb{Z}/(p+1)\mathbb{Z})^2$, so the order of every $\mathbb{F}_{p^2}$-rational point divides $p+1$. Then $\pi^2$ acts as the identity since $x^{p^2} = x$ in $\mathbb{F}_{p^2}$, and $[-p]$ acts as multiplication by $-p \bmod (p+1) = 1$, also the identity. Both sides agree on every $\mathbb{F}_{p^2}$-rational point.

What the pointwise check does not establish

Agreement on $\mathbb{F}_{p^2}$-rational points is weaker than equality in $\mathrm{End}(E_0)$, and for a reason worth seeing: both sides collapse to the identity there, so the check confirms a coincidence rather than the relation. Separating them needs points of order coprime to $p+1$, which live in higher extensions. The relation itself follows from the Frobenius characteristic polynomial $T^2 + p$ on a trace-zero supersingular curve (Theorem V.2.3.1 in Silverman, 2009).

Under the map $\iota \mapsto i,\; \pi \mapsto j,\; \iota \pi \mapsto k$, the lattice $\mathbb{Z}\langle 1, \iota, (\iota+\pi)/2, (1 + \iota \pi)/2 \rangle$ inside $\mathrm{End}(E_0) \otimes \mathbb{Q}$ corresponds to $\mathcal{O}_0$. The construction works at any prime $p \equiv 3 \pmod 4$.

BFS over the isogeny graph

A breadth-first search through degree-2 and degree-3 isogenies finds connecting paths between $j$-invariants. At $p = 431$ the supersingular graph has diameter 4: any two $j$-invariants are connected by at most four degree-2 or degree-3 isogenies.

from collections import deque

p = 431

def fp2_add(x, y, p):
    return ((x[0]+y[0]) % p, (x[1]+y[1]) % p)
def fp2_sub(x, y, p):
    return ((x[0]-y[0]) % p, (x[1]-y[1]) % p)
def fp2_mul(x, y, p):
    return ((x[0]*y[0]-x[1]*y[1]) % p, (x[0]*y[1]+x[1]*y[0]) % p)
def fp2_inv(x, p):
    n = (x[0]*x[0]+x[1]*x[1]) % p
    inv = pow(n, -1, p)
    return ((x[0]*inv) % p, ((-x[1])*inv) % p)
def fp2_sqr(x, p):
    return ((x[0]*x[0]-x[1]*x[1]) % p, (2*x[0]*x[1]) % p)
def fp2_neg(x, p):
    return ((-x[0]) % p, (-x[1]) % p)

def j_invariant(a, b, p):
    a3 = fp2_mul(fp2_sqr(a, p), a, p)
    four_a3 = ((4*a3[0]) % p, (4*a3[1]) % p)
    b2 = fp2_sqr(b, p)
    den = fp2_add(four_a3, ((27*b2[0]) % p, (27*b2[1]) % p), p)
    return fp2_mul(((1728*four_a3[0]) % p, (1728*four_a3[1]) % p), fp2_inv(den, p), p)

a0, b0 = (1, 0), (0, 0)
print(j_invariant(a0, b0, p))
# ==> (4, 0)

The base curve $E_0: y^2 = x^3 + x$ has $j(E_0) = 1728 \bmod 431 = 4$ in the constant component, zero in the imaginary part. The full BFS uses Velu’s formulas to compute the codomain of each candidate isogeny, then continues the search from the new vertex. The standalone implementation is find_path in the ch23-sqisign package under solutions/.

Toy SQIsign: keygen

A secret key is a walk from $E_0$ encoded as a list of (degree, kernel-index) pairs. The walk is derived deterministically from a seed so the toy is reproducible.

import hashlib

# Stand-in for the standalone package's keygen.
# The chapter shows the structure; the full keygen lives in
# the ch23-sqisign package under solutions/.

SECRET_WALK_LENGTH = 4

def derive_walk(seed, length):
    h = hashlib.sha256(seed).digest()
    while len(h) < length:
        h = h + hashlib.sha256(h).digest()
    walk = []
    for i in range(length):
        byte = h[i]
        degree = 2 if (byte & 0x80) == 0 else 3
        kernel_index = byte & 0x7F
        walk.append((degree, kernel_index))
    return walk

walk = derive_walk(b"alice", SECRET_WALK_LENGTH)
print(walk)
# ==> [(2, 43), (3, 88), (2, 6), (3, 73)]

The four-step walk for the seed b"alice" chooses two degree-2 and two degree-3 steps with deterministic kernel selections. Walking this from $E_0$ produces the public-key curve. At $p = 431$ breadth-first search to depth 4 reaches every supersingular $j$-invariant, since the diameter of the graph is 4. The toy’s fixed-length deterministic keygen walk is a single reproducible path through that graph, not a uniform sample of the supersingular set. Cryptographic primes need walks of length proportional to $\log p$ to mix uniformly over the supersingular set. The bound follows from the Ramanujan property (Pizer, 1990). Real SQIsign packs the walk choices into a secret order representative; the toy uses the explicit walk.

Toy SQIsign: sign

Signing derives a deterministic walk from the message and public key, walks it from $E_0$ to obtain a challenge curve $E_{\mathsf{chal}}$, then runs BFS to find a connecting isogeny from $E_{\mathsf{chal}}$ to the public-key curve. The signature is the resulting path.

# Pedagogical sketch of the signing routine.
# The runnable sign lives in the ch23-sqisign package under solutions/
# and is exercised by tests/ch23/test_sqisign_roundtrip.py.

import hashlib

CHALLENGE_WALK_LENGTH = 3

def hash_to_walk(message, pk_a, pk_b, length):
    h = hashlib.sha256()
    h.update(message)
    for fp2 in (pk_a, pk_b):
        h.update(fp2[0].to_bytes(2, "big"))
        h.update(fp2[1].to_bytes(2, "big"))
    digest = h.digest()
    while len(digest) < length:
        digest = digest + hashlib.sha256(digest).digest()
    out = []
    for i in range(length):
        byte = digest[i]
        degree = 2 if (byte & 0x80) == 0 else 3
        out.append((degree, byte & 0x7F))
    return out

# Use the actual public-key coefficients (a, b) for the alice keypair
# computed by sqisign.keygen(b"alice"): a = (137, 0), b = (0, 375).
# The j-invariant of this curve is (143, 0).
walk = hash_to_walk(b"hello", (137, 0), (0, 375), CHALLENGE_WALK_LENGTH)
print(walk)
# ==> [(3, 60), (2, 60), (3, 30)]

The challenge derivation uses SHA-256 over the message and the public-key coefficients. Each output byte selects one isogeny step. The challenge walk has fixed length so that the verifier reproduces $E_{\mathsf{chal}}$ deterministically. The connecting isogeny that follows is the secret-dependent part. Real SQIsign draws one from a distribution chosen so that its form does not leak the secret order. The toy uses BFS from public data alone, so anyone who can reproduce the search produces a valid signature without holding the secret. That is a failure of unforgeability rather than a demonstration that the secret walk itself is recovered.

Toy SQIsign: verify

The verifier recomputes $E_{\mathsf{chal}}$ from the message and public key, walks the signature path from $E_{\mathsf{chal}}$, and checks the result against the public key.

# Verification structure: walk the signature from the challenge curve,
# compare j-invariants. The runnable verify is in
# the ch23-sqisign package under solutions/.

p = 431

def check_match(j_walked, j_pk, p):
    return j_walked[0] % p == j_pk[0] % p and j_walked[1] % p == j_pk[1] % p

# After walking, suppose the path lands at j = (143, 0).
j_walked = (143, 0)
j_pk = (143, 0)
print(check_match(j_walked, j_pk, p))
# ==> True

# A path that lands elsewhere is rejected.
print(check_match((19, 0), j_pk, p))
# ==> False

The check is intentionally simple: the signature is valid exactly when its walk lands at a curve isomorphic to the public key.

Round-trip demonstration

The full keygen-sign-verify cycle exercises every layer: deterministic key derivation, hash-to-challenge, BFS connecting isogeny, signature verification.

# Run the standalone toy. Imports use the package layout, but the
# inline blocks above re-derive every helper from standard library
# primitives so each block is self-contained.

import sys, pathlib
PKG = pathlib.Path("solutions/ch23-sqisign/src").resolve()
sys.path.insert(0, str(PKG))

from sqisign.sqisign import keygen, sign, verify

sk = keygen(b"alice")
print(sk.pk.j())
# ==> (143, 0)

sig = sign(b"the quick brown fox", sk)
print(verify(b"the quick brown fox", sig, sk.pk))
# ==> True
print(verify(b"different message", sig, sk.pk))
# ==> False

The signature is a list of (degree, kernel-generator) pairs. At $p = 431$ the path is at most 4 steps, the diameter of the supersingular graph. At cryptographic primes a real signature encodes the response isogeny as compact interpolation data: the images of a few torsion points through the isogeny, carried as a change-of-basis matrix alongside an auxiliary curve, rather than as an explicit path. All of it fits into 200 bytes at NIST level 1 (Table 1 and Chapter 6 in The SQIsign Team, 2026).

Simplifications, restated

The toy departs from real SQIsign in three places, each flagged where it occurs above.

First, BFS over the supersingular graph replaces the scheme’s quaternion-side ideal search. BFS runs in $O(p)$ time and is infeasible for cryptographic primes. The real search runs in expected time polynomial in $\log p$ under heuristic assumptions, and it never touches the curves until the chosen ideal is translated back (The SQIsign Team, 2025, sec. 3.2 and 4.4).

Second, the signature is a list of explicit kernel generators. Real Round-2 SQIsign instead represents the response isogeny with compact interpolation data (point images encoded as a change-of-basis matrix), at a degree that is bounded rather than prescribed and need not be smooth (The SQIsign Team, 2025, sec. 1.3 and 10.2).

Third, the toy has no zero-knowledge structure. SQIsign is built from a sigma protocol made non-interactive by Fiat-Shamir (formalized in Chapter 33), and the signing procedure must not reveal the secret order through the response isogeny (The SQIsign Team, 2025, sec. 10.1).

Hardness assumptions and known attacks

SQIsign’s security rests on the presumed hardness of computing the endomorphism ring of a supersingular curve (a hint-augmented variant), together with the zero-knowledge and Fiat-Shamir analysis of the signing protocol (The SQIsign Team, 2025, sec. 10.1).

The endomorphism ring problem

EndRing: given a supersingular elliptic curve $E$ over $\mathbb{F}_{p^2}$, compute (a $\mathbb{Z}$-basis for) $\mathrm{End}(E)$.

The best classical algorithm for the related isogeny path problem ran in time $\widetilde{O}(p^{1/2})$ for three decades, using meet-in-the-middle on the supersingular isogeny graph (Delfs & Galbraith, 2016). In July 2026 Wesolowski gave a heuristic algorithm in $p^{1/3+o(1)}$ time and memory, still exponential in $\log p$; the round-3 SQIsign specification bases its security estimates on it, priced through the time-memory tradeoff $t^2 w = \widetilde{O}(p)$ that its exponential memory forces, and raised every parameter set in response (The SQIsign Team, 2026, sec. 8.2; Wesolowski, 2026). No subexponential classical algorithm is known. Quantumly, Biasse, Jao and Sankar reach $\widetilde{O}(p^{1/4})$ by a Grover search over short isogeny walks for a curve defined over $\mathbb{F}_p$, followed by a class-group computation in that curve’s $\mathbb{F}_p$-endomorphism ring that is subexponential under the generalized Riemann hypothesis: a quadratic speedup over the classical meet-in-the-middle bound (Biasse et al., 2014). No polynomial-time quantum algorithm is known.

Wesolowski proved that the supersingular $\ell$-isogeny path problem (given $E_1, E_2$ and a fixed small prime $\ell$, find a path from $E_1$ to $E_2$ in the $\ell$-isogeny graph) and EndRing are equivalent under reductions of expected polynomial time for supersingular curves over $\mathbb{F}_{p^2}$, assuming the generalized Riemann hypothesis (Wesolowski, 2022). SQIsign’s hardness rests on this equivalence, extended in 2024 to isogenies of arbitrary degree (Chapter 3): a forger who could find connecting isogenies could compute endomorphism rings, and conversely.

Why Castryck-Decru does not apply

The 2022 attack on SIDH used the published torsion-point images $\phi(P_B), \phi(Q_B)$ to reconstruct Alice’s secret kernel through Kani’s theorem (Chapter 22). The Castryck-Decru paper gives a heuristic polynomial-time attack for a starting curve with known endomorphism ring (Castryck & Decru, 2023). Robert later removed that condition and the heuristic, in polynomial time from the torsion images and the factored smooth degrees alone (Robert, 2022). Round-2 SQIsign does publish torsion-point images, but only of the public response isogeny $\phi_{\mathsf{rsp}}$, so the verifier can evaluate it (The SQIsign Team, 2025, sec. 1.3). It never publishes the secret isogeny’s action on a torsion basis. The public key is the curve $E_{\mathsf{sec}}$ together with a one-byte hint that speeds up regenerating a torsion basis anyone could compute unaided, and no point images at all (The SQIsign Team, 2025, sec. 4.3 and 4.6). SIDH’s break needed images of a torsion basis taken under the secret isogeny. With no such data tied to the secret, the Kani-Frey gluing construction has no input.

The SQIsign specification reaches the same conclusion at the problem level. The endomorphism-ring problem underlying SQIsign is unaffected by the SIDH attacks: SIDH relied on an easier variant of the fundamental isogeny problems (The SQIsign Team, 2025, sec. 1.1 footnote 2).

Response leakage and zero knowledge

The signature carries the response isogeny $\phi_{\mathsf{rsp}}: E_{\mathsf{com}} \to E_{\mathsf{chl}}$, and the signer computes it from secret-side data, so the question is whether its distribution reveals $\mathcal{O}_{\mathsf{sec}}$. The original 2020 SQIsign paper answered in two steps, in the section numbering of its full version on ePrint. Its Section 7.2, Proposition 10, characterises the SigningKLPT output set exactly. Its Section 7.3 then states Assumption 2, that the corresponding ideal classes are statistically close to uniform, and Problem 2, a computational assumption under which the response is indistinguishable from a uniform isogeny of the same degree. That second assumption is the ad hoc step the round-2 revision set out to remove (De Feo et al., 2020, sec. 7.2 and 7.3; The SQIsign Team, 2025, sec. 1.3). Round 2 answers differently. The response is a uniform draw from the isogenies $E_{\mathsf{com}} \to E_{\mathsf{chl}}$ under a degree bound, and the proof runs in a Fiat-Shamir-with-hints framework where the simulator is handed extra isogenies as hints (The SQIsign Team, 2025, sec. 10.1).

That framework moves the assumption rather than discharging it. Zero knowledge now rests on distinguishing two hint distributions: one samples the far curve uniformly, the other samples it as the codomain of a bounded-degree isogeny. Conditioned on the same codomain the two are identical, so an attack has to separate the codomain distributions instead. A degree bound above $p^2$ would make them statistically close, and SQIsign’s bound is $O(\sqrt{p})$, so the specification claims only computational indistinguishability (The SQIsign Team, 2025, sec. 10.2.4). Unforgeability then reduces to finding one non-scalar endomorphism given those hints, and under the uniform hint distribution that problem carries a worst-case-to-average-case self-reduction (The SQIsign Team, 2025, sec. 10.1). No key-recovery attack on the scheme is known, and the best known attack on the hint variant discards the hints and costs what the plain endomorphism ring problem costs (The SQIsign Team, 2025, sec. 10.2.3).

Adaptive attacks on the interactive variant

Interactive isogeny-based identification protocols are vulnerable to adaptive attacks: an attacker who can choose challenges adaptively can extract information about the secret over many queries, as first demonstrated for SIDH-style key encapsulation (Galbraith et al., 2016). The SQIsign sigma protocol’s soundness and zero-knowledge properties are analyzed in (The SQIsign Team, 2025, sec. 10.1). The Fiat-Shamir transform closes the chosen-challenge interface of the interactive protocol: the challenge is derived deterministically from a hash of the public key, the commitment curve, and the message, so an attacker cannot choose protocol challenges adaptively. Signature-level security then rests on the Fiat-Shamir analysis in the random-oracle model together with the soundness and zero-knowledge of the underlying sigma protocol (The SQIsign Team, 2025, sec. 10.1). Chosen-message security is a separate model. The point here is only that the interactive chosen-challenge surface is removed.

Tradeoffs: SQIsign, ML-DSA, and SLH-DSA

SQIsign trades signing speed and assumption maturity for size. The comparison below uses low-end parameter sets: SQIsign level 1 and SLH-DSA-128s are NIST security category 1, while ML-DSA-44 is category 2, so this is a practical size comparison rather than an exact same-category one. The data sources are the FIPS specifications and the round-3 SQIsign specification.

Property	SQIsign (level 1)	ML-DSA-44	SLH-DSA-128s
Public key	83 B	1,312 B	32 B
Signature	200 B	2,420 B	7,856 B
pk + sig	283 B	3,732 B	7,888 B
NIST category	1	2	1
Hard problem	Supersingular EndRing	Module-LWE + Module-SIS	Hash-function assumptions
NIST status	Additional sigs, Round 3	FIPS 204	FIPS 205
Sign time	~28 ms	no cited figure	~208 ms
Verify time	~3.6 ms	no cited figure	~0.3 ms

Sources: SQIsign sizes from the round-3 specification (Table 1 in The SQIsign Team, 2026); ML-DSA sizes from (Table 2 in National Institute of Standards and Technology, 2024a); SLH-DSA sizes and category from (Table 2 in National Institute of Standards and Technology, 2024b); NIST round status from (National Institute of Standards and Technology, 2026). The two timing columns come from two different machines, so read them as an order-of-magnitude comparison rather than as a benchmark. SQIsign is the optimized 64-bit Intel implementation on an Intel Core i7-13700K at a 3.4 GHz nominal clock, at 93.9M cycles to sign and 12.1M to verify (Table 2 in The SQIsign Team, 2026); the round-2 code verified in 5.1M cycles, and the round-3 parameter increase cost verification most. The SLH-DSA-128s cells carry a measurement of the predecessor. It is the round-3 SPHINCS+-SHA-256-128s-simple instance, with the AVX2 code on one core of a 3.1 GHz Intel Xeon E3-1220, at 645M cycles to sign and 0.86M to verify (Aumasson et al., 2020). FIPS 205 carries that instance’s parameters as SLH-DSA-SHA2-128s but not its algorithm: Appendix A lists two new address types, PK.seed added as an input to PRF, and a changed method for extracting FORS indices from the message digest, none of them confined to the higher categories (Appendix A in National Institute of Standards and Technology, 2024b). The figure also says nothing about the SHAKE instantiation. The ML-DSA-44 cells carry no timing: FIPS 204 specifies none, and the benchmark suite this book cites elsewhere, SUPERCOP 20260831, lists the scheme only under its round-3 name dilithium2, which is not a measurement of the final algorithm (Bernstein & Lange, 2026).

The 283-byte combined size reduces per-signature bandwidth in protocols that carry signatures inline with each message, such as TLS certificate chains and DNSSEC responses. At roughly 28 ms per signature, a single CPU core produces on the order of thirty-five signatures per second, which bounds real-time signing throughput. SLH-DSA has the most conservative assumption (hash function security), but its signatures are nearly 40 times larger.

SQIsign is not the slowest signer in the table. The SPHINCS+ instance behind the SLH-DSA-128s column spends about 208 ms per signature, roughly seven times SQIsign’s 28 ms, because signing walks the hypertree authentication path (Aumasson et al., 2020). The small-signature parameter set is the one that pays most for it. Verification runs the other way: it verifies in about 0.3 ms against SQIsign’s 3.6 ms, so the two schemes are slow at opposite ends.

Applications: governance keys

Governance keys on a Layer-1 blockchain rotate on the order of weeks to years and sign on the order of days to months. Block-producer rotation in proof-of-stake systems and treasury multisig under k-of-n authorization share this slow-path profile. A governance public key is fetched once per signer and cached by every full node, so its byte cost is amortized across many verifications. The signature byte cost is still paid per signed governance action. The size figures in the tradeoffs table above show SQIsign-I’s 283-byte combined footprint at NIST level 1.

The roughly 28 ms signing time of the round-3 SQIsign optimized 64-bit Intel implementation (The SQIsign Team, 2026) is far slower than the microsecond-class ECDSA and Schnorr signing that wallets rely on. That makes SQIsign unattractive for high-throughput per-transaction signing, though it does not categorically rule it out. Ethereum’s 12-second slot and Bitcoin’s 10-minute block interval set the per-transaction inclusion window that wallets sign-and-submit into, where microsecond-class signing on commodity hardware is the operating point of pre-quantum ECDSA and Schnorr. Governance keys tolerate tens-of-milliseconds signing latency comfortably; high-throughput per-transaction paths do not. Chapter 39 covers the consensus and staking signature surfaces (validator-key rotation cadence, committee reshuffling) and Chapter 41 covers the governance multisig surface (treasury proposals, hard-fork coordination). SQIsign’s slow signing path is acceptable on both.

Chapter 24 closes Part IV with the one family Parts II through IV have not built from scratch, and it extends the table above with two multivariate rows. The comparison does not survive intact. UOV-Is signs in 96 bytes against SQIsign’s 200, so what SQIsign holds is specifically the smallest combined public key plus signature: UOV pays for the shorter signature with a 412 kB public key, about five thousand times SQIsign’s 83 bytes. The cached-key argument above is the axis that separates the two.

Exercises

Exercise 1. Compute the products $(2 + 3i + j) \cdot (1 - i + k)$ and $(1 - i + k) \cdot (2 + 3i + j)$ in $B_{431,\infty}$ by hand. Verify that the two products share the same scalar coefficient (the trace component must match) but differ in the $i$, $j$, and $k$ components, confirming non-commutativity. Reproduce both products with the quat_mul function from the chapter.

Exercise 2. Determine which of the following lie in the standard maximal order $\mathcal{O}_0$ at $p = 431$:

(a) $(2 + j)/3$, (b) $(1 + i + j + k)/2$, (c) $i + (1 + k)/2$, (d) $j/2$.

For each, either give the integer coordinates in the $\mathcal{O}_0$ basis or explain why it fails the membership condition.

Exercise 3. At $p = 83$ (also $\equiv 3 \pmod 4$), the supersingular graph has 8 $j$-invariants. Adapt the BFS code to enumerate the graph: starting from $E_0: y^2 = x^3 + x$ over $\mathbb{F}_{83^2}$, walk all degree-2 and degree-3 edges and list every reachable $j$-invariant. Confirm the count.

Exercise 4. Modify the ch23-sqisign package under solutions/ so that signing derives a challenge walk of length 5 instead of 3. Signing and verification read the same walk length: sign(message, sk) returns a Signature derived at that length, and verify(message, signature, pk) recomputes the challenge walk at the same length and returns a bool. The round trip holds only when both read the same length. Rerun the test test_sqisign_roundtrip.py. Report whether the signature lengths change and whether verification still succeeds.

Exercise 5. SQIsign’s 83-byte public key is roughly $16\times$ smaller than ML-DSA-44’s 1,312-byte public key. Explain in two sentences what the public key represents in each scheme, and why an isogeny-based public key can be so much smaller than a lattice-based one. Reference the parameter sets in (The SQIsign Team, 2026) and (Table 2 in National Institute of Standards and Technology, 2024a), and note that ML-DSA-44 is NIST category 2 while SQIsign level 1 targets category 1, so the comparison is across security categories.

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

References

Aumasson, J.-P., Bernstein, D. J., Beullens, W., Dobraunig, C., Eichlseder, M., Fluhrer, S., Gazdag, S.-L., Hülsing, A., Kampanakis, P., Kölbl, S., Lange, T., Lauridsen, M. M., Mendel, F., Niederhagen, R., Rechberger, C., Rijneveld, J., Schwabe, P., & Westerbaan, B. (2020). SPHINCS+: Submission to the NIST Post-Quantum Cryptography Standardization Process. NIST PQC Round 3 submission; SPHINCS+ specification v3, 1 October 2020. https://sphincs.org/data/sphincs+-round3-specification.pdf

Basso, A., De Feo, L., Dartois, P., Leroux, A., Maino, L., Pope, G., Robert, D., & Wesolowski, B. (2023). SQIsign: Algorithm Specifications and Supporting Documentation. NIST Post-Quantum Cryptography Additional Signatures, Round 1 submission. https://sqisign.org

Bernstein, D. J., & Lange, T. (2026). eBACS: ECRYPT Benchmarking of Cryptographic Systems, SUPERCOP results for amd64-hertz (AMD Ryzen 7 7700, Zen 4). eBACS amd64-hertz results, sign, kem and dh pages; supercop-20260831, read 14 September 2026. https://bench.cr.yp.to/results-sign/amd64-hertz.html

Biasse, J.-F., Jao, D., & Sankar, A. (2014). A quantum algorithm for computing isogenies between supersingular elliptic curves. Progress in Cryptology, INDOCRYPT 2014, 428–442. https://doi.org/10.1007/978-3-319-13039-2_25

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

Cerviño, J. M. (2004). Supersingular elliptic curves and maximal quaternionic orders. In Y. Tschinkel (Ed.), Mathematisches Institut, Georg-August-Universität Göttingen: Seminars Summer Term 2004 (pp. 53–60). Universitätsdrucke Göttingen. https://doi.org/10.17875/gup2004-46

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

Deuring, M. (1941). Die Typen der Multiplikatorenringe elliptischer Funk\-tion\-enkörper. Abhandlungen Aus Dem Mathematischen Seminar Der Universität Hamburg, 14, 197–272. https://doi.org/10.1007/BF02940746

Galbraith, S. D., Petit, C., Shani, B., & Ti, Y. B. (2016). On the Security of Supersingular Isogeny Cryptosystems. Advances in Cryptology – ASIACRYPT 2016, Part I, 10031, 63–91. https://doi.org/10.1007/978-3-662-53887-6_3

Kohel, D. (1996). Endomorphism rings of elliptic curves over finite fields [Phdthesis, University of California, Berkeley]. https://math.berkeley.edu/publications/endomorphism-rings-elliptic-curves-over-finite-fields

Kohel, D., Lauter, K., Petit, C., & Tignol, J.-P. (2014). On the quaternion ℓ-isogeny path problem. LMS Journal of Computation and Mathematics, 17(A), 418–432. https://doi.org/10.1112/S1461157014000151

Leroux, A. (2022). Quaternion Algebras and Isogeny-Based Cryptography [Phdthesis, École Polytechnique]. https://www.lix.polytechnique.fr/page/index.php?path=manuscrit_these.pdf&username=aleroux

National Institute of Standards and Technology. (2024a). 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. (2024b). 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. (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

Pizer, A. K. (1990). Ramanujan graphs and Hecke operators. Bulletin of the American Mathematical Society, 23(1), 127–137. https://doi.org/10.1090/S0273-0979-1990-15918-X

Robert, D. (2022). Breaking SIDH in polynomial time. Cryptology ePrint Archive, Paper 2022/1038. https://eprint.iacr.org/2022/1038

Silverman, J. H. (2009). The Arithmetic of Elliptic Curves (2nd ed., Vol. 106). Springer. https://doi.org/10.1007/978-0-387-09494-6

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

Voight, J. (2021). Quaternion Algebras (Vol. 288). Springer. https://doi.org/10.1007/978-3-030-56694-4

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