Appendix D: Solutions for Chapter 24

This page collects solutions and editorial notes for the exercises in Chapter 24: Multivariate signature schemes. 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 multivariate package under solutions/ch24-multivariate. From a clone of the companion repository, pytest tests/ch24 runs its suite. Appendix C has the setup.

Exercise 1

Upper-triangular entries: $\binom{n}{2} + n = n(n+1)/2$. At $n = 5$: $15$ entries. At $n = 160$: $160 \cdot 161 / 2 = 12{,}880$ entries per form. With $m = 64$ forms and two GF(16) elements per byte: total bytes $= 64 \cdot 12{,}880 / 2 = 412{,}160$ bytes $\approx 412$ KB.

n_toy = 5
n = 160
m = 64
print(n_toy * (n_toy + 1) // 2)
print(n * (n + 1) // 2)
print(m * n * (n + 1) // 2 // 2)
# ==> 15
# ==> 12880
# ==> 412160

Exercise 2

The structural answer: every entry $F_i[j][k]$ with both $j$ and $k$ in the oil index set $\{N_V, \ldots, N-1\}$ is zero by construction in keygen (this is the oil-oil block that defines the trapdoor). The public map is $P_i = T^\top \cdot F_i \cdot T$, which is the substitution $P(x) = F(Tx)$ written in quadratic-form notation, since $x^\top (T^\top F_i T) x = (Tx)^\top F_i (Tx)$. It mixes the oil and vinegar coordinates through the secret transformation, so each entry of $P_i$ is a combination of $F_i$ entries drawn from all four blocks and is in general nonzero.

The inverse $T^{-1}$ appears in signing, not in the public map: the signer solves for $y$ in central coordinates and returns $x = T^{-1} y$, so that $P(x) = F(T T^{-1} y) = F(y)$ hits the target. Printing both sets of entries makes the trapdoor visible: the secret coordinate system has zeros where the public one does not, and finding the secret is equivalent to recovering the basis transformation that aligns those zeros.

Exercise 3

When $n = 2m$ the preimage $T^{-1}(O)$ of the oil space is a common invariant subspace of every pencil map $M_{ij}$, and Kipnis-Shamir recover it in polynomial time from the invariant subspaces of those maps, up to a basis ambiguity inside it. When $n > 2m$ it stops being invariant, so there is nothing to read off the pencil directly and the attack becomes a search. Until round 12 this answer described that search as an $(n - 2m)$-dimensional family of candidate subspaces with about $q^{n - 2m}$ members. No source supports that family, and the claim is withdrawn.

The exponent is an expected number of trials. The round-2 specification states the mechanism directly: finding a single vector of the oil subspace is dominated by computing an average of $q^{n-2m}$ characteristic polynomials of $n \times n$ matrices and solving as many linear systems, giving $O(q^{n-2m} n^{\omega} \log n)$ field multiplications. The older literature figure is $O(q^{n-2m} n^4)$. The specification says that figure overestimates the cost and traces its $n^4$ to a cruder accounting at $\omega = 3$, where the refined bound reads $n^3 \log n$ (Beullens et al., 2025, sec. 4.3). The remaining basis vectors are then cheaper to reach, so repeating the search $m$ times does not multiply the cost by $m$.

Two things are worth getting right here. The $q^{n-2m}$ is an expected number of characteristic-polynomial computations, not a count of subspaces: the number of all $m$-dimensional subspaces of $\mathrm{GF}(q)^n$ is the Gaussian binomial $\binom{n}{m}_q$, very much larger, and an attack that enumerated subspaces would be far slower than the one Kipnis-Shamir give. And the security margin comes from the gap $n - 2m$, not from the ratio $n/m$: UOV-Is takes $n = 160$, $m = 64$, a ratio of only $2.5$, but a gap of $32$, which at $q = 16$ is $16^{32} = 2^{128}$.

import math

for name, q, n, m in [("balanced", 16, 128, 64), ("uov-Is", 16, 160, 64)]:
    gap = n - 2 * m
    print(f"{name}: gap={gap} search=2^{gap * int(math.log2(q))}")
# ==> balanced: gap=0 search=2^0
# ==> uov-Is: gap=32 search=2^128

Exercise 4

(a) Inline signed message at a 500-byte budget per packet, public key cached: UOV-Is. Both multivariate rows clear the budget (UOV-Is at 96 B, MAYO1 at 464 B), as does SQIsign-I at 200 B, but UOV-Is wins on the constraint that repeats: the signature is paid per packet and 96 bytes is the smallest in the table. The public key is fetched once, so its size sits outside the per-packet budget.

Disadvantage: the key cost is deferred, not removed. Any flow that re-fetches (key rotation, a new client, a cache eviction) pays 412 kB in the classic version, or 66,576 B in pkc, which is still two orders of magnitude above ML-DSA-44’s 1,312 B. A strong answer also notes that UOV is a round-3 candidate with no standard, so this choice is not available to a deployment that needs a FIPS algorithm today.

(b) Code-signing scheme, large public key acceptable, low-power verifier: SLH-DSA-128s. Public keys are 32 bytes, signatures are 7,856 bytes (large, but distributed once per release), and the security assumption is hash-only, which matters most for a signing root that must stay trustworthy for years. Verification is well-supported on any microcontroller with SHA-2 acceleration, and it is FIPS-standardized today, which in this table is true of ML-DSA-44 as well and of nothing else. The hash-only assumption is what separates the two for a signing root.

Disadvantage: signing is slow. Chapter 23’s table puts SLH-DSA-128s at roughly 208 ms per signature, from 645M cycles on a 3.1 GHz core, which is about seven times SQIsign’s 28 ms and the slowest signer in the book. That is fine at one signature per release and prohibitive for a high-volume signing service, which is the tradeoff the small-signature parameter set buys.

References

Beullens, W., Chen, M.-S., Ding, J., Gong, B., Kannwischer, M. J., Patarin, J., Peng, B.-Y., Schmidt, D., Shih, C.-J., Tao, C., & Yang, B.-Y. (2025). UOV: Unbalanced Oil and Vinegar — Algorithm Specifications and Supporting Documentation. NIST Post-Quantum Cryptography Additional Signatures, Round 2 submission. https://www.uovsig.org