Chapter 24: Multivariate signature schemes
Parts II through IV build four families from scratch: lattice (LWE, Ring-LWE, ML-KEM), hash-based (Lamport, WOTS+, FORS, SLH-DSA), code-based (McEliece, HQC), and isogeny-based (SIDH, SQIsign). One family remains. Multivariate signatures rest on a different hard problem: given a random system of quadratic equations over a finite field, find a common solution. Chapter 1 frames this chapter as a survey rather than a from-scratch construction. UOV, MAYO, QR-UOV, and SNOVA advanced to the third round of NIST’s Additional Digital Signatures process in May 2026 (National Institute of Standards and Technology, 2026). The multivariate sizes below are from their round-3 specifications of August 2026, and SNOVA’s sizes are the same in its Version 3.1 of September (Beullens, Campos, et al., 2026; Beullens, Chen, et al., 2026; Furue et al., 2026; Wang et al., 2026a, 2026b). They can still change before anything is standardized, since recent cryptanalysis has affected several parameter sets.
The pedagogical goal here is narrower. The reader should finish this chapter able to describe the Oil-Vinegar trapdoor and explain why the Kipnis-Shamir invariant-subspace attack on the balanced scheme does not carry over unchanged to the unbalanced variant (Kipnis & Shamir, 1998). They should also be able to say what the extended attack costs there (Sections 3 and 4 in Kipnis et al., 1999). Finally, they should be able to compare UOV, MAYO, and SNOVA on key and signature sizes, and place multivariate alongside the other three signature families in a concrete decision table.
A worked Oil-Vinegar at GF(7)
Section titled “A worked Oil-Vinegar at GF(7)”The Oil-Vinegar trick is structural. Split the variables into two groups. In every quadratic equation, a term either multiplies two “vinegar” variables or multiplies one vinegar variable by one “oil” variable. No term multiplies two oil variables. The signer knows the split. The verifier does not, because the public map is a linear mixture that hides the split.
Fix the vinegar values. Every quadratic equation collapses to an affine expression in the oil variables alone. The signer solves a small linear system to find oil values that hit the target, then reports the combined vinegar-oil vector as the signature. The verifier only sees the mixed public equations and cannot perform the same collapse.
The toy below uses one vinegar variable and two oil variables over , with two quadratic equations. The central map has no , , or terms. Those monomials are the oil-oil block, and Oil-Vinegar forces that block to zero.
Q = 7
def F_1(v, o1, o2): return (v*v + v*o1 + 2*v*o2 + 3) % Qdef F_2(v, o1, o2): return (4*v*v + 2*v*o1 + v*o2 + 5) % Q
target = [2, 5]
# Signer picks a vinegar value.v = 3
# With v fixed, each F_i is linear in (o1, o2). Build the 2x2 coefficient matrix# and the right-hand side, then solve over GF(7) by Cramer's rule.A = [[v, 2*v], [2*v, v]]c = [(v*v + 3) % Q, (4*v*v + 5) % Q]b = [(target[i] - c[i]) % Q for i in range(2)]
det = (A[0][0]*A[1][1] - A[0][1]*A[1][0]) % Qassert det != 0, f"singular system for v={v}; pick a different vinegar value"det_inv = pow(det, Q - 2, Q) # Fermat inversion: x^(Q-2) == x^(-1) in GF(Q)o1 = (A[1][1]*b[0] - A[0][1]*b[1]) * det_inv % Qo2 = (-A[1][0]*b[0] + A[0][0]*b[1]) * det_inv % Q
print("vinegar v =", v)print("oil (o1, o2) =", (o1, o2))print("F(v, o1, o2) =", [F_1(v, o1, o2), F_2(v, o1, o2)])print("target =", target)# ==> vinegar v = 3# ==> oil (o1, o2) = (4, 1)# ==> F(v, o1, o2) = [2, 5]# ==> target = [2, 5]Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch24/, one file per block. Appendix C covers the clone and the environment they run on.
The trapdoor is only useful if the oil-oil block really is zero, which the verifier cannot check because the public map hides the algebraic structure.
The MQ problem and the Oil-Vinegar trapdoor
Section titled “The MQ problem and the Oil-Vinegar trapdoor”The multivariate quadratic (MQ) problem is the following. Given quadratic polynomials in variables over a finite field , and a target vector , find with for every . The decision version asks whether such an exists. Decision-MQ is -complete over every finite field. Over it is the quadratic case of Garey and Johnson’s problem AN9, which they list as -complete even when no term involves more than two variables (Problem AN9 in Garey & Johnson, 1979, p. 251).
The same holds over any finite field, by a direct reduction from 3-SAT. Each Boolean variable gets the equation , which in a field forces to be or , read as false or true. A literal is then or . Each clause with literals gets a fresh variable and two equations, and . The first makes exactly when and are both false, and the second then forces true. So the system has a solution exactly when the formula is satisfiable. Every equation is quadratic, and the system grows linearly with the formula. A claimed solution is checked by evaluating the polynomials, which puts the problem in .
-completeness is a worst-case statement, and it says nothing directly about random systems or about the structured system a signature scheme publishes. For the underdetermined systems such schemes publish, with more variables than equations, the best known classical algorithms (F5, XL, crossbred, hybrid) take time exponential in the number of equations rather than the number of variables. The round-2 UOV specification’s state-of-the-art estimate shows why: a Thomae-Wolf reduction turns the system into equations in variables, which hybrid Wiedemann-XL then solves (Beullens, Chen, et al., 2025, sec. 4.2).
Oil-Vinegar uses a trapdoor over this problem. Fix a finite field , a number of equations , a number of oil variables , and a number of vinegar variables with . The secret central map is a collection of quadratic forms where each has zero coefficients on every monomial that multiplies two oil variables. With split into vinegar and oil , every is a quadratic in plus a bilinear term coupling to . No pure oil-oil quadratic term appears.
The secret transformation is a uniformly random invertible matrix. The public map is . In quadratic-form notation, if is represented by the (not necessarily symmetric) matrix so that , then , and this matrix in general has every block nonzero. The oil-oil structure that enabled the collapse above is no longer visible. The invariant-subspace analysis below runs on the polar form rather than on itself, in every characteristic: an upper-triangular coefficient matrix whose oil-oil block is zero has zero rows and is never invertible, while the polar form is generically invertible, and its oil-oil block is zero whenever the oil-oil block of is. Over characteristic-2 fields (the UOV case for and ) the polar form is alternating, so it drops the diagonal and is invertible only for even . The trapdoor structure survives the choice of representation either way.
Signing reverses the composition. Given a target , the signer picks vinegar values uniformly at random. It evaluates the vinegar-only part of each to get a constant and extracts the bilinear-in-oil coefficients to form a matrix . Solving gives the oil values. If is singular, the signer resamples the vinegar and tries again. Otherwise it computes and returns as the signature.
Verification evaluates and checks componentwise equality with . The verifier never sees , , or the vinegar-oil split. The structure is absorbed into the opaque public map.
Figure 24.1 shows the Oil-Vinegar trapdoor structure from both the signer’s and the verifier’s perspective: on the left the signer holds the central map with the oil-oil block zeroed; on the right the verifier sees the public map , dense after the secret transformation is applied.
The balanced choice , meaning , is the original 1997 scheme of Patarin. Kipnis and Shamir showed in 1998 that balanced Oil-Vinegar admits a polynomial-time attack that recovers the oil subspace through an invariant-subspace search on the pencil of public quadratic forms (Kipnis & Shamir, 1998). Kipnis, Patarin, and Goubin answered in 1999 with the unbalanced scheme , also called UOV, and observed that taking sufficiently larger than raises the attack cost to exponential in (Kipnis et al., 1999). UOV-Is, a parameter set at NIST level 1, takes and (Table 1 in Beullens, Chen, et al., 2026). The ratio is only , and the margin against this attack comes from the gap , in which the attack’s cost is exponential.
Direct solving of the public system without using the trapdoor is the other main attack. Grobner-basis algorithms such as F4 and F5 reduce random quadratics in variables to a triangular basis in time , where is the degree of regularity and is the matrix-multiplication exponent. The formula is not unconditional. It prices under the semi-regular heuristic, which is a modeling assumption about the system rather than a theorem about dense ones. Whether it is reasonable turns on the ratio of equations to variables, the field, and any preprocessing applied first. UOV public systems are structured, which is not itself a proof that the heuristic fails for them. What it means is that the structure gives no ground for assuming the generic estimate applies. Either way a semi-regular Grobner estimate is heuristic guidance, not a proof or a universal lower bound.
Parameters are instead set against the best known attacks, each with its own cost model, and the binding constraint is whichever comes out lowest. The round-3 specification tabulates five for UOV-Is (Table 5 in Beullens, Chen, et al., 2026):
| Attack | Type | Cost (bits) | Added under MEM-2D (bits) |
|---|---|---|---|
| Collision | Forgery | 143 | not assigned |
| Direct | Forgery | 162 | 8 |
| Kipnis-Shamir | Key recovery | 153 | not assigned |
| Intersection | Key recovery | 176 | 24 |
| Wedge | Key recovery | 158 | 22 |
The collision attack binds at 143 bits, and that is exactly the bar. NIST’s call for proposals puts level 1 at classical gates, the cost of an AES-128 key search, with and for levels 3 and 5 (Beullens, Campos, et al., 2025, sec. 5; Wang et al., 2025). That 143 is not a RAM-model count. The specification’s formula gives 142.7 in the RAM model, and the table prints 143 because the attack needs a large memory whose cost the specification leaves unquantified, while also setting aside possible tricks worth a speedup (§4.1 in Beullens, Chen, et al., 2026). Round 2 had tabulated four attacks, with the direct attack at 165 bits and Kipnis-Shamir at 154 (Table 5 in Beullens, Chen, et al., 2025). Round 3 adds the wedge attack described below and a second way of costing the direct attack.
The last column prices memory access. Except on the collision row, the cost column counts binary gates in the usual RAM model, which charges nothing extra for reaching memory. The specification adds a model it calls MEM-2D and cites Ding, Guo and Yang’s ePrint 2026/1819 for it (Beullens, Chen, et al., 2026, sec. 4.7). In MEM-2D a random access to bits of memory costs , and the specification reports the extra cost for the three attacks that run a parallelized Wiedemann XL solver (§4.7 in Beullens, Chen, et al., 2026). It keeps the RAM figure as its “primary metric” and calls MEM-2D “model-dependent, not a replacement for RAM or a lower bound”. The collision and Kipnis-Shamir rows get no entry because neither attack runs that solver.
Toy UOV at (n, m, q) = (5, 2, 7)
Section titled “Toy UOV at (n, m, q) = (5, 2, 7)”The toy below expands the motivating example to matrix form with vinegar variables and oil variables over . The block is self-contained: it samples the secret transformation and the central map , builds the public map , then signs a toy target and verifies the signature. The oil-oil block of each is forced to zero; the oil-oil block of in general is not.
Real UOV-Is uses total variables with vinegar and oil, over with equations (Beullens, Chen, et al., 2026). The toy is several orders of magnitude too small to resist MinRank or Grobner attacks and is not a cryptographic scheme. The toy also takes prime, so field inversion is the Fermat power pow(x, Q - 2, Q). Real UOV parameter sets work over extension fields such as or , where elements are polynomials and inversion needs extension-field arithmetic rather than integer arithmetic modulo the field size.
import random
Q, N, M, N_V = 7, 5, 2, 3 # field, total vars, equations, vinegar vars
def matmul(A, B): n, k, m = len(A), len(A[0]), len(B[0]) return [[sum(A[i][t] * B[t][j] for t in range(k)) % Q for j in range(m)] for i in range(n)]
def transpose(A): return [list(row) for row in zip(*A)]
def mat_vec(A, v): return [sum(A[i][k] * v[k] for k in range(len(v))) % Q for i in range(len(A))]
def quadratic_eval(Mat, x): return sum(Mat[i][j] * x[i] * x[j] for i in range(len(x)) for j in range(len(x))) % Q
def is_invertible(A): n = len(A); mat = [row[:] for row in A] for c in range(n): p = next((r for r in range(c, n) if mat[r][c] != 0), None) if p is None: return False mat[c], mat[p] = mat[p], mat[c] inv = pow(mat[c][c], Q - 2, Q) for r in range(c + 1, n): if mat[r][c]: f = mat[r][c] * inv % Q for k in range(c, n): mat[r][k] = (mat[r][k] - f * mat[c][k]) % Q return True
def invert_mat(A): n = len(A) mat = [row[:] + [1 if j == i else 0 for j in range(n)] for i, row in enumerate(A)] for c in range(n): p = next((r for r in range(c, n) if mat[r][c] != 0), None) assert p is not None, "matrix is singular over GF(Q); inversion undefined" mat[c], mat[p] = mat[p], mat[c] inv = pow(mat[c][c], Q - 2, Q) for k in range(2 * n): mat[c][k] = mat[c][k] * inv % Q for r in range(n): if r != c and mat[r][c]: f = mat[r][c] for k in range(2 * n): mat[r][k] = (mat[r][k] - f * mat[c][k]) % Q return [row[n:] for row in mat]
def solve_linear(A, b): m = len(A); aug = [A[i][:] + [b[i]] for i in range(m)] for c in range(m): p = next((r for r in range(c, m) if aug[r][c] != 0), None) if p is None: return None aug[c], aug[p] = aug[p], aug[c] inv = pow(aug[c][c], Q - 2, Q) for k in range(m + 1): aug[c][k] = aug[c][k] * inv % Q for r in range(m): if r != c and aug[r][c]: f = aug[r][c] for k in range(m + 1): aug[r][k] = (aug[r][k] - f * aug[c][k]) % Q return [aug[i][m] for i in range(m)]
# KeyGen. Sample T invertible; sample F with oil-oil block zero; build P.rng = random.Random(0)while True: T = [[rng.randrange(Q) for _ in range(N)] for _ in range(N)] if is_invertible(T): break
F = []for _ in range(M): F_i = [[rng.randrange(Q) for _ in range(N)] for _ in range(N)] for r in range(N_V, N): for c in range(N_V, N): F_i[r][c] = 0 F.append(F_i)
P = [matmul(matmul(transpose(T), F_i), T) for F_i in F]
# Sign. Target = toy hash. Fix vinegar; solve linear system in oil.target = [3, 5]rng2 = random.Random(1)while True: vinegar = [rng2.randrange(Q) for _ in range(N_V)] L, rhs = [], [] for i, F_i in enumerate(F): c_i = sum(F_i[j][k] * vinegar[j] * vinegar[k] for j in range(N_V) for k in range(N_V)) % Q row = [sum((F_i[j][N_V + l] + F_i[N_V + l][j]) * vinegar[j] for j in range(N_V)) % Q for l in range(M)] L.append(row); rhs.append((target[i] - c_i) % Q) oil = solve_linear(L, rhs) if oil is not None: break
y = vinegar + oilsignature = mat_vec(invert_mat(T), y)
# Verify. Evaluate P on the signature and check componentwise against target.p_eval = [quadratic_eval(P_i, signature) for P_i in P]
print("target: ", target)print("signature:", signature)print("P(sig): ", p_eval)print("verify: ", p_eval == target)# ==> target: [3, 5]# ==> signature: [4, 4, 4, 2, 3]# ==> P(sig): [3, 5]# ==> verify: TrueThe block runs the full keygen, sign, and verify loop. The signer used to collapse two quadratic constraints into a linear system once three vinegar entries were fixed. The verifier only needed and the signature, and matched both target coordinates exactly.
Three multivariate candidates: UOV, MAYO, and SNOVA
Section titled “Three multivariate candidates: UOV, MAYO, and SNOVA”UOV, MAYO, and SNOVA share the Oil-Vinegar trapdoor and differ in how the public map is compressed or inflated. UOV uses the central map directly. MAYO multiplies a smaller central map through a public emulsifier. SNOVA promotes scalars to matrices. All three are candidates in NIST’s Additional Digital Signatures process, the signature on-ramp NIST opened in September 2022, which is distinct from the original standardization process, in whose first three rounds (2017 to 2022) Rainbow competed. NIST IR 8610 (May 2026) advanced UOV, MAYO, and SNOVA, together with SQIsign and five other schemes, to the third round of that on-ramp (National Institute of Standards and Technology, 2026). The parameter sets quoted below are from the three teams’ round-3 specifications of August 2026.
UOV. The direct descendant of (Kipnis et al., 1999). Its round-3 specification lists four parameter sets across NIST security levels 1, 3, and 5 (Table 1 in Beullens, Chen, et al., 2026). The level-1 set UOV-Is is the same as in round 2: it uses , vinegar and oil variables (so ). Sizes at those parameters are 412,160 B for the expanded public key, 348,704 B for the expanded secret key (32 B in seed-only form), and 96 bytes for the signature (160 packed nibbles plus a 16-byte salt). The signature is small because each field element fits in half a byte. The public key is large because it stores the coefficients of quadratic forms in variables, which grows as half-byte entries.
The submission ships three versions of each parameter set, and the size that matters depends on which one is deployed. The classic version stores the expanded key. The pkc version stores a compact public key instead, 66,576 B at UOV-Is, and expands it inside verification. The pkc+skc version compresses the secret key as well (Table 1 in Beullens, Chen, et al., 2026). The 412 kB figure quoted throughout this chapter is the classic one, the expanded form NIST means when it describes UOV’s cost as “public keys over 200 kilobytes in expanded form” (National Institute of Standards and Technology, 2026, sec. 3.11).
MAYO. A UOV variant introduced by Beullens in 2021 (Beullens, 2022b). MAYO takes an oil space deliberately too small for UOV, with . That makes recovering the oil space harder, so the other parameters can shrink, but it also breaks signing: solving becomes linear equations in only unknowns, which usually has no solution (Beullens, Campos, et al., 2025, sec. 1).
The fix is to whip up the map. A public set of fixed matrices combines the evaluations of the small map with the cross terms between each pair of inputs. The result is one larger map on variables, chosen so that vanishes on a space of dimension . Here is the differential of (Beullens, Campos, et al., 2026, sec. 1). Its -th component is , the polar form the trapdoor section uses. Parameters are set so , at least as many oil variables as equations, which restores a large enough oil space to solve in (§1 and §2.1.1 in Beullens, Campos, et al., 2026). MAYO1 takes the equality case, . Both signer and verifier evaluate , so both pay for the expansion.
The specification names the parameter sets MAYO1, MAYO2, MAYO3, and MAYO5, at NIST security levels 1, 1, 3, and 5. In the round-3 specification of 31 August 2026, MAYO1 takes variables and against equations with whipping parameter , and reports a 1,456-byte public key and a 464-byte signature (Table 2.1 in Beullens, Campos, et al., 2026). Round 2 had and , 1,420 bytes and 454 bytes (Table 2.1 in Beullens, Campos, et al., 2025). The team calls the change a slight gain in security against the direct attack, for a two percent increase in size (change log in Beullens, Campos, et al., 2026).
Round 3 also changed MAYO2 and the whipping. MAYO2 was reparameterized to , at 2,928 bytes and 239 bytes, to raise the cost of key recovery after the wedge attack described below (change log and Table 2.1 in Beullens, Campos, et al., 2026). Its is 86 rather than the planned 82, to push above the cost of a key-recovery attack that Merz and Ran reported privately days before the submission deadline (change log in Beullens, Campos, et al., 2026). The whipping schedule became an MDS matrix, because the round-2 ordering of the left the whipping schedule with submatrices of unusually low rank, which could be exploited to mildly speed up collision attacks (change log in Beullens, Campos, et al., 2026).
The verification equation also gained a linear term, with the coefficients of derived from the hash of the message and salt (change log in Beullens, Campos, et al., 2026). The linear term, an idea from the original 1999 UOV paper revived (change log in Beullens, Campos, et al., 2026; Kipnis et al., 1999, sec. 8), answers improved claw-finding attacks reported to the team in August 2026, which the table in the cryptanalysis section lists (§5.4 in Beullens, Campos, et al., 2026).
SNOVA. An Oil-Vinegar variant defined over a non-commutative matrix ring rather than a finite field (Wang et al., 2026a). Coefficients in the quadratic forms are matrices over , so every scalar multiplication in UOV becomes a matrix product in SNOVA. The designers attribute the small public keys to that matrix ring together with key-randomness alignment, which shifts randomness out of the private key into the public key, and seeded regeneration of the rest (Wang et al., 2025, sec. 1.4). Round 2 counted SNOVA’s equations over the matrix ring. Its set SNOVA-, named for vinegar count , oil count , field size and matrix dimension , had equations over , which is 80 scalar equations against UOV-Is’s 64 (Wang et al., 2025, sec. 1.3). Round 3 counts them over , as : 96, 96 and 80 for the three level-1 sets (Table 5 in Wang et al., 2026a).
The round-3 specification of August 2026 recommends nine parameter sets, three per security level, all over with a 96-byte secret key. It labels them for a smaller public key, a balance, or a smaller signature (Table 5 in Wang et al., 2026a). At level 1 the public key and signature run from 376 B and 528 B to 1,016 B and 272 B. Every one of those signatures is longer than UOV-Is’s 96 bytes (Table 1 in Beullens, Chen, et al., 2026), so the saving is on the key side alone. The smaller-signature set keeps round 2’s 1,016-byte public key but is a different set, with 27 vinegar variables rather than 24, described by seven parameters rather than four.
This chapter’s SNOVA parameters and cost tables are from Version 3.0, the version NIST’s round-3 page still served on 19 October 2026 (Wang et al., 2026a). The team’s Version 3.1, described below, leaves them unchanged: its change log lists corrected typos, an updated reference, and a new way of sampling vinegar values for the odd-characteristic alternative sets (p. 2 in Wang et al., 2026b).
The round-2 sets are history: the wedge-product variant discussed below broke most of them. NIST’s May 2026 report described a modification the team had proposed, over odd-characteristic fields with symmetric quadratic forms, at a category-1 set whose public key and signature are both smaller than Falcon’s (National Institute of Standards and Technology, 2026). Round 3 did not adopt it. All its recommended and alternative sets use asymmetric public matrices, the alternatives over odd-characteristic fields included, and it keeps symmetric ones “experimental until they have undergone sufficiently broad and mature cryptanalysis” (§6.2 in Wang et al., 2026a). SNOVA is described here but kept out of the closing tradeoffs table, because NIST’s May report did not see it as having reached a stable form.
In Version 3.0 the odd-characteristic alternatives fell to their signing procedure rather than their algebra. Version 3.0’s signer samples vinegar values by reducing uniform bytes modulo a power of , and Beullens and Hess show that the resulting bias leaks secret-key information for all six of those sets. The nine recommended sets use and are unaffected (Beullens & Hess, 2026). The table in the cryptanalysis section gives the attack’s costs. Beullens and Hess note that sampling the vinegar values uniformly would stop the attack (Beullens & Hess, 2026). The team’s Version 3.1 does that: for odd its signer uses rejection sampling so that the vinegar values are uniformly distributed over (Wang et al., 2026b, p. 24). Announcing it on 28 September 2026, the team wrote that its round-3 submission to NIST remains unchanged, because none of the recommended sets is affected (SNOVA Team, 2026).
Cryptanalysis: MinRank, Grobner bases, and the quantum picture
Section titled “Cryptanalysis: MinRank, Grobner bases, and the quantum picture”No single attack sets the floor for the round-3 parameter sets. The paragraphs below take four attack families in turn and say what each does to an Oil-Vinegar key: the invariant-subspace attack, direct solving, the wedge attack and MinRank. The quantum picture and Rainbow’s history follow them, then a table of the main results up to 19 October 2026 and what those results leave standing.
Invariant-subspace attack on balanced Oil-Vinegar. Kipnis and Shamir observed a structural property that the attacker can exploit using only the public matrices. For balanced Oil-Vinegar with , the preimage of the oil subspace is a common invariant subspace of the pencil maps whenever is invertible, where each here is the polar form of the public matrix, as the trapdoor section set up (Kipnis & Shamir, 1998). The order matters under the chapter’s column convention : the product preserves the annihilator of instead. The reversed product is the right one only in a row-vector convention, where the secret map acts on the right, which is how the unbalanced paper writes it (Section 3 in Kipnis et al., 1999). Kipnis and Shamir themselves write column vectors and the inverse-first pencil. The attacker sees , computes the pencil, and searches for the common invariant subspace. When that preimage is a common invariant subspace of every pencil map, and Kipnis and Shamir recover it in polynomial time from the invariant subspaces of those maps. Recovering the oil subspace lets the attacker construct an equivalent signing key by choosing a basis of that subspace and any complementary basis.
For the unbalanced choice , the preimage of the oil space is no longer invariant under the pencil maps, and the attack becomes a search whose cost grows as . The specification puts the mechanism concretely: finding a single vector of the oil subspace costs an average of characteristic-polynomial computations on matrices, with the remaining basis vectors then cheaper to reach (Beullens, Chen, et al., 2026, sec. 4.3). The exponent is that expected number of trials. It is not the dimension of a family of candidate subspaces, and no such family is claimed here. The literature figure, stated for even or odd, is . The specification refines it and tabulates 153 bits for UOV-Is, against for the search factor alone (Table 5 in Beullens, Chen, et al., 2026).
Direct solving by Grobner basis. The public system is quadratic polynomials in variables. F4 and F5 compute a Grobner basis of the ideal they generate. The cost is dominated by linear algebra over a Macaulay matrix whose size depends on the degree of regularity . Model the system as semi-regular and grows roughly linearly in in the regime where the equation count tracks the variable count, which makes the overall cost exponential in . The UOV public system’s structure does not justify assuming that generic estimate applies to it, so the estimate is heuristic.
The round-3 specification costs the direct attack two ways. One reduces the underdetermined system to equations in variables, then applies hybrid Wiedemann-XL at the solving degree read off a power-series expansion. The other is Hashimoto’s approach for underdetermined systems, and the specification takes the smaller of the two costs (Beullens, Chen, et al., 2026, sec. 4.2). Parameters are set by the best known direct forgery and key-recovery attacks, not by the semi-regular estimate alone. MAYO’s and SNOVA’s round-2 justifications include analogous Macaulay-matrix cost estimates (Beullens, Campos, et al., 2025; Wang et al., 2025).
The direct attack on MAYO has become cheaper since NIST’s May 2026 report, through two papers that extend Hashimoto’s algorithm independently (§1.2 in Asanuma et al., 2026). Asanuma, Chen, Furue, Sakata and Takagi split the variables into more groups than Hashimoto’s three (Asanuma et al., 2026). Ostuzzi, in a paper accepted at ASIACRYPT 2026, computes richer pseudo-oil structures and spreads the algebraic work across more than two Grobner-basis steps (Ostuzzi, 2026b). Asanuma et al. leave UOV out of their evaluation, because its system is too little underdetermined for their method to be expected to help (§1.1 in Asanuma et al., 2026). The table below gives what each paper does to MAYO1 as round 2 defined it.
The wedge attack. Ran proposed it in 2025, for fields of characteristic 2 (§4.6 in Beullens, Chen, et al., 2026). It exploits the shape of the central map. Every monomial of each contains a vinegar variable, so every public polynomial lies in the ideal generated by the hidden linear forms whose common zeros are the oil space . In characteristic 2 each polar form is alternating, a 2-vector in the exterior algebra, whose product is the wedge product. In the same algebra, the span of the hidden forms is represented by one decomposable -vector, the wedge product of a basis. Working there rather than in the polynomial ring, the attack makes the condition that the public forms vanish on the oil space linear in that vector’s coordinates. Linear algebra then recovers the hidden forms, and with them the oil space (Beullens, Chen, et al., 2026, sec. 4.6; Merz & Ran, 2026, sec. 1).
The attack is a variation on the XL algorithm that does linear algebra on one huge matrix (§5.4 in Beullens, Campos, et al., 2026). It needs a large enough oil space (§5.4 in Beullens, Campos, et al., 2026): it applies at a threshold the parameters fix, or not at all (Merz & Ran, 2026). Later work carried it to odd characteristic, where it remains less efficient (§5.4 in Beullens, Campos, et al., 2026), and combined it with the intersection attack in truncated polynomial rings (§4.6 in Beullens, Chen, et al., 2026). The cost estimates of these variants rest on heuristic conjectures that counterexamples show do not always hold (§4.6 in Beullens, Chen, et al., 2026). Merz and Ran’s extension of September 2026 removes the threshold and covers odd characteristic, resting on a Hilbert series it conjectures and checks experimentally (Merz & Ran, 2026). The table below gives its reach.
MinRank. MinRank asks, given matrices over and a bound , for coefficients in , not all zero, with . A MinRank attack builds a family of matrices from the public map and looks for a member of low rank.
In UOV the secret guarantees a low-rank member. Take oil vectors and form the rows , one for each vector and each of the public forms, with each the polar form again. Each row vanishes on the whole oil space, because and vanishes there. So the rows, at least of them, span at most dimensions.
The specification’s MinRank attack on UOV searches for oil vectors that cause that drop. It writes each with its last coordinates set to a different column of the identity matrix, which keeps them independent, and those fixed coordinates add a fixed matrix to the combination, the form in which the specification states MinRank. Finding the vectors recovers the key, at a cost much larger than the other attacks’ for its four sets (§4.5 in Beullens, Chen, et al., 2026).
MinRank gives forgeries as well as key recoveries. SNOVA’s MinRank-based forgery first makes a matrix built from the public map drop rank, a generalized MinRank problem, and then solves a smaller MQ system (Wang et al., 2026a, sec. 5.2.2).
Quantum picture. The quantum attacks the sources below describe are classical attacks with Grover’s algorithm applied to their search steps. Grover’s algorithm reduces a brute-force search over to roughly oracle queries. The round-3 specification states that the known quantum attacks on UOV apply Grover’s algorithm to the exhaustive-search parts of classical attacks, and that none gives more than a quadratic speedup over the classical attack (Beullens, Chen, et al., 2026, sec. 4.8). For MAYO, QR-UOV and SNOVA, May, Ostuzzi and Ressler turn forgery into an exhaustive search that Grover’s algorithm speeds up (May et al., 2026), and the table below gives their estimate for MAYO1. MAYO’s round-3 specification, which cites them, still counts every known quantum attack on MAYO as a classical one sped up by at most a square root (§5.4 in Beullens, Campos, et al., 2026).
Historical context. Rainbow was a multi-layer Oil-Vinegar variant submitted to round 3 of the NIST standardization process that ran from 2017 to 2022. Beullens published a direct key-recovery attack in 2022 that gave an expected 53-hour laptop key-recovery cost for Rainbow’s second-round level-1 parameters, with the third-round set estimated at a further factor of (Beullens, 2022a). NIST’s third-round status report records the attack and did not select Rainbow for standardization (Sections 2.3 and 4.5.3 in Alagic et al., 2022). The Rainbow attack exploited the layered central-map structure, not the single-layer Oil-Vinegar structure. It does not directly generalize to the single-layer UOV setting or to the UOV-derived candidates discussed here. HFE and GeMSS are earlier multivariate designs not covered here.
Recent cryptanalysis. The Rainbow break does not mean the surviving multivariate candidates are settled. During the second round, NIST recorded new attacks affecting several parameter sets of UOV, MAYO, and SNOVA (National Institute of Standards and Technology, 2026). The results table below gives the main ones and the main results that followed them up to 19 October 2026, each dated by its first appearance. Each figure is its source’s estimate, in that source’s cost model, and several price round-2 sets that round 3 replaced.
| Year and work | Attack | Sets | Result |
|---|---|---|---|
| 2025, Ran | Wedge (§4.6 in Beullens, Chen, et al., 2026) | UOV and MAYO, round 2 | Three of UOV’s four sets lose from a few bits (category 1) to about 20 (category 5), and MAYO2 falls roughly 30 bits short of its target (National Institute of Standards and Technology, 2026, sec. 3.11 and 3.12) |
| 2025, May, Ostuzzi and Ressler (May et al., 2026) | Quantum forgery, an exhaustive search sped up by Grover’s algorithm | MAYO, QR-UOV and SNOVA, round 2 | Round-2 MAYO1’s quantum estimate falls to , from for Hashimoto’s algorithm (Table 3 in May et al., 2026) |
| 2026, Furue and Ikematsu | Wedge, combined with the intersection attack in truncated polynomial rings (§4.6 in Beullens, Chen, et al., 2026) | UOV, round 2 | With Ran’s attack, takes UOV-Ip, UOV-III and UOV-V below their targets (National Institute of Standards and Technology, 2026, sec. 3.11) |
| 2026, Bros et al. (Bros et al., 2026) | Wedge, using SNOVA’s block-ring structure | SNOVA, round 2 | Breaks 6 of the 11 sets and improves the best known result on 2 more |
| 2026, Asanuma et al. (Asanuma et al., 2026) | Direct | Round-2 MAYO1 | , against for Hashimoto’s algorithm in their cost model (Table 3 in Asanuma et al., 2026) |
| 2026, Ostuzzi (Ostuzzi, 2026b) | Direct | Round-2 MAYO1, and a QR-UOV set over GF(7) | for MAYO1, against for Hashimoto’s algorithm in the constant memory-access model, and against for the QR-UOV set (Tables 1 and 2 in Ostuzzi, 2026b) |
| August 2026, three teams, independently (§5.4 in Beullens, Campos, et al., 2026) | Claw finding, all “using AI cryptanalysis” | MAYO1, MAYO2, MAYO3 and MAYO5, without the linear term | Up to , , and faster than the previous claw-finding attack, which the team says brings the attacks slightly below the targets |
| September 2026, Beullens and Hess (Beullens & Hess, 2026) | Key recovery from Version 3.0’s biased vinegar sampling | SNOVA’s six odd-characteristic alternative sets | A naive attack costs to small-field operations, against the 170 to 331 bits claimed. A refined one recovered four keys in practice from 9 million to 180 million signatures, in 22 seconds to just over 16 minutes on one 16-core server |
| September 2026, Merz and Ran (Merz & Ran, 2026) | Wedge, extended with divided powers and Schur-Macaulay matrices | Every round-2 set of UOV, MAYO, SNOVA and QR-UOV but one | Puts 7 of SNOVA’s 11 sets below their claimed level, and leaves QR-UOV’s above theirs, at 191 to 229 bits at level 1 (Table 10 in Merz & Ran, 2026) |
| 30 September 2026, Ostuzzi (Ostuzzi, 2026a) | Structural forgery on the whipped map, with the pseudo-oil technique | Round-3 MAYO | MAYO2 falls from , the cost the preprint gives a generic forgery, to , below the target. MAYO1 falls from to (Table 2 in Ostuzzi, 2026a) |
Which sets fell is worth stating precisely, because the tradeoffs table below quotes one UOV set and one MAYO set. After the attacks of Ran and of Furue and Ikematsu, UOV-Is was the one set of UOV’s four still meeting its target (National Institute of Standards and Technology, 2026, sec. 3.11). Round 3 enlarged the other three and left UOV-Is as it was (change log in Beullens, Chen, et al., 2026).
For MAYO the wedge attack applied to MAYO2, a category-1 set, and to none of MAYO’s other three proposed sets (§5.4 in Beullens, Campos, et al., 2026). The round-3 specification reparameterized MAYO2 in response, as the MAYO paragraph above records. NIST, citing Ran’s analysis of the attack, suggests it hit MAYO harder than category-1 UOV because of the balance between the number of quadratic forms and the codimension of the secret subspace, not because of the whipping structure (National Institute of Standards and Technology, 2026, sec. 3.12). That judgment concerns the wedge attack. Ostuzzi’s preprint of 30 September, the results table’s last row, attacks the whipping structure itself (Ostuzzi, 2026a).
The two multivariate columns in the tradeoffs table below are therefore surviving sets rather than arbitrary picks: UOV-Is, and MAYO1 as round 3 redefined it. Round 3 made MAYO1 two equations and two variables larger for margin against the direct attack, and gave it, like every round-3 MAYO set, the linear term that blocks the August claw-finding attack (change log and §5.4 in Beullens, Campos, et al., 2026). The claw-finding factors in the results table above measure the speedup over the old attack, not the shortfall against the target, which the specification does not quantify.
SNOVA fared worst: a wedge-product variant “broke most of SNOVA’s proposed parameter sets, often by a large margin” (National Institute of Standards and Technology, 2026). That variant is NIST IR 8610’s own reference 10, the paper of Bros et al. in the results table.
NIST advanced UOV, MAYO, QR-UOV, and SNOVA to the third round because each retains unbroken parameter sets and the family contributes small signatures, reduced public keys, and algorithmic diversity. In that May assessment QR-UOV was the one of the four with none of its proposed parameter sets broken, and NIST records it as resistant to the wedge attack and its variants. NIST also anticipates a longer timeline before any multivariate scheme is standardized (National Institute of Standards and Technology, 2026), and says it does not see SNOVA as having reached a stable form.
QR-UOV, which shrinks UOV’s public key by working over a quotient ring (National Institute of Standards and Technology, 2026), changed its parameters in round 3 all the same. Its specification of 31 August 2026 keeps its main sets over with , adds sets with that trade a smaller public key for a longer signature, and moves the others to an appendix. At level 1 the public key and signature are 24,256 B and 200 B with , against 11,041 B and 541 B with (Table 4 in Furue et al., 2026).
Round 3 also changed QR-UOV’s signing. It now outputs the lexicographically smaller of and , and verification checks it. That closes a trivial forgery against strong unforgeability, since was a second valid signature on a message already signed, not a signature on a new one. A rank threshold added to signing is a performance change, there to bound its retries. The specification also reports new analyses keeping every proposed set at its claimed level against the wedge attack and two other recent key-recovery attacks (change log in Furue et al., 2026).
Among the attacks each round-3 specification prices, the cheapest is the collision attack for UOV-Is and the wedge attack for UOV’s other three sets (Table 5 in Beullens, Chen, et al., 2026). It is the direct attack for every MAYO set, at for MAYO2 (Table 5.1 in Beullens, Campos, et al., 2026). For SNOVA’s nine recommended sets it is the direct attack, the collision attack or a MinRank-based forgery, depending on the set (Tables 9 to 11 in Wang et al., 2026a). The Kipnis-Shamir invariant-subspace attack, which forced the unbalanced shape, is the cheapest for none of the three schemes’ sets. MAYO’s table leaves out Merz and Ran’s attack, which the team says puts above against MAYO2 (change log in Beullens, Campos, et al., 2026). The specification also predates Ostuzzi’s preprint of 30 September, which says round 3’s linear term blocks its multi-target step, and that the term and the new whipping schedule weaken its structural one (§7.2 in Ostuzzi, 2026a).
Both direct-attack papers in the results table price MAYO1 as round 2 defined it, with , not the round-3 set in the tradeoffs table (Table 2.1 in Beullens, Campos, et al., 2025). MAYO’s round-3 specification cites both and prices the direct attack with the method of Asanuma et al.: on the new MAYO1, the cheapest attack it lists against that set (§5.4 and Table 5.1 in Beullens, Campos, et al., 2026). Round 2 priced the old set at with Hashimoto’s own algorithm (Table 5.1 in Beullens, Campos, et al., 2025), so the two specifications’ figures differ in method as well as in set. The QR-UOV set Ostuzzi prices, , is one QR-UOV lists as additional rather than recommended, and round 3 keeps it unchanged in its appendix (Table 16 in Furue et al., 2026).
Neither paper’s direct-attack figures break a set. Ostuzzi’s ASIACRYPT paper says its reduction “does not immediately threaten the security of MAYO or QR-UOV” (Ostuzzi, 2026b, sec. 7), and the specification’s for round-3 MAYO1 is above the its team sets as the level-1 target (§5.4 in Beullens, Campos, et al., 2026). Of the MAYO results in the results table, only his structural forgery of 30 September claims a set as round 3 specifies it below target, and its MAYO1 figure also falls below that . Both papers’ attacks are direct attacks and leave NIST’s wedge finding for QR-UOV alone. That finding also survives the wedge-family attack that does reach QR-UOV, Merz and Ran’s, which leaves each round-2 QR-UOV set above its target. The sizes in the tradeoffs table are unaffected: it quotes keys and signatures, not security margins.
Tradeoffs: four families at the low end
Section titled “Tradeoffs: four families at the low end”The following table extends the Chapter 23 three-family comparison (SQIsign, ML-DSA, SLH-DSA) by adding two multivariate columns. It compares the smallest size-relevant parameter set in each family. The security categories are not perfectly aligned. SLH-DSA-128s, UOV-Is, MAYO1, and SQIsign-I target NIST category 1, while ML-DSA-44 is FIPS 204 security category 2 (Table 1 in National Institute of Standards and Technology, 2024a). The ML-DSA-44 column is therefore a low-end size point, not an exact same-category comparison. The figures come from the FIPS standards and the round-3 SQIsign, UOV and MAYO specifications.
| Property | SQIsign-I | ML-DSA-44 | SLH-DSA-128s | UOV-Is | MAYO1 |
|---|---|---|---|---|---|
| Family | Isogeny | Lattice | Hash | Multivariate | Multivariate |
| NIST category | 1 | 2 | 1 | 1 | 1 |
| Public key | 83 B | 1,312 B | 32 B | 412 kB | 1,456 B |
| Signature | 200 B | 2,420 B | 7,856 B | 96 B | 464 B |
| pk + sig | 283 B | 3,732 B | 7,888 B | 412 kB | 1,920 B |
| Hard problem | Supersingular EndRing | Module-LWE + Module-SIS | Hash-function assumptions | MQ + Oil-Vinegar | Whipped MQ + Oil-Vinegar |
| NIST status | Additional sigs, Round 3 | FIPS 204 | FIPS 205 | Additional sigs, Round 3 | Additional sigs, Round 3 |
| First proposed | 2020 | 2017 (as Dilithium) | 2015 (as SPHINCS) | 1999 | 2021 |
Sources: SQIsign-I figures from the round-3 specification (Table 1 in The SQIsign Team, 2026), matching the Chapter 23 table; ML-DSA-44 from (Tables 1 and 2 in National Institute of Standards and Technology, 2024a); SLH-DSA-128s from (Table 2 in National Institute of Standards and Technology, 2024b); UOV-Is from (Table 1 in Beullens, Chen, et al., 2026); MAYO1 from (Table 2.1 in Beullens, Campos, et al., 2026); NIST round status from (National Institute of Standards and Technology, 2026). The first-proposed row gives each design’s original publication year, sourced separately: SQIsign (De Feo et al., 2020), Dilithium (Ducas et al., 2018), SPHINCS (Bernstein et al., 2015), UOV (Kipnis et al., 1999), and MAYO (Beullens, 2022b). FIPS 204 records only that ML-DSA is derived from CRYSTALS-DILITHIUM, and FIPS 205 that SLH-DSA is based on SPHINCS+, whose own antecedent is the 2015 SPHINCS paper. Neither standard gives a date.
One caveat on the two multivariate public keys, because they are not the same kind of number. UOV-Is’s 412 kB is the expanded key of the classic version. The pkc version of the same parameter set stores 66,576 B and expands inside verification. MAYO1’s 1,456 B is already a compact key, a 16-byte seed plus one block, which MAYO.ExpandPK expands to 156,640 B, the specification’s 153 KB, before verification (§2.1.1 and Table 2.1 in Beullens, Campos, et al., 2026). Compared like for like, MAYO1 is roughly 46 times smaller than UOV-Is compact and about 2.6 times smaller expanded, not the 280-fold gap the row implies. MAYO’s public-key advantage over UOV is real in every representation; the size of it is not what a straight reading of the row gives.
The multivariate columns inherit the MQ assumption and add the Oil-Vinegar trapdoor. UOV-Is produces the smallest signature in the table (96 B, smaller than SQIsign-I at 200 B) and the largest public key (412 kB, about five thousand times the SQIsign-I public key). MAYO1 trades most of that signature-size advantage for a public key of 1,456 B, in the lattice range. The smaller key comes from the small oil space and the whipping construction, which lets the stored key be a seed plus one block.
The choice between them is set by which cost repeats. When the public key is fetched once and cached and the signature dominates per-message cost, UOV-Is’s 96-byte signature undercuts SQIsign-I’s 200 bytes. MAYO1’s 464-byte signature is larger than SQIsign-I’s, but still well below ML-DSA-44 and SLH-DSA. When the public key must be distributed to every client or stored in a constrained location, UOV-Is is ruled out at 412 kB and marginal even at its 66,576-byte compact size. Figure 24.2 below is a narrower router: it branches on standardization status, on whether a hash-only assumption is required, and on whether the public key fits under 2 kB. Which byte cost repeats is not one of its questions, and the tradeoffs table above is where that comparison sits.
Layer-1 transactions and per-block payloads carry a tight byte budget that scales with the global node count. UOV-Is at 412 kB per public key (Beullens, Chen, et al., 2026) is not realistic for per-transaction public-key publication on current L1 designs. It fits only where the key is published rarely, cached aggressively, or kept off the hot transaction path. MAYO1 at 1,456 B per public key (Beullens, Campos, et al., 2026) is small enough for slow-rotating cached-key surfaces where the key is published once and cached. Chapter 23 identifies governance keys and treasury multisig as sharing that slow-path profile. Its 464 B signature is roughly one-fifth of ML-DSA-44’s 2,420 B (Table 2 in National Institute of Standards and Technology, 2024a), the smallest ML-DSA parameter set.
None of that makes a multivariate scheme deployable today. As of 19 October 2026, ML-DSA and SLH-DSA are FIPS-standardized; UOV, MAYO, and SNOVA are round-3 candidates in NIST’s Additional Digital Signatures process, with no draft standard and a timeline NIST expects the recent attacks to lengthen. NIST says it is “unlikely to standardize them without a further round of evaluation” (National Institute of Standards and Technology, 2026). Chapter 39 covers the consensus and validator-signature surfaces; Chapter 41 covers the governance surface, where a committee signs treasury proposals, parameter changes, and protocol upgrades.
The lattice and hash-based assumptions have accumulated roughly a decade of dedicated NIST-process cryptanalysis (2016 onward), plus the longer history of their underlying problems. SQIsign, the signature built on the isogeny endomorphism-ring problem, dates from 2020. SIDH was broken in 2022 (see Chapter 22), and SQIsign’s round-3 sizes grew mainly because a larger prime prices a July 2026 endomorphism-ring algorithm (see Chapter 23).
The MQ plus Oil-Vinegar assumption base dates from 1999 for UOV, but the parameter sets are recent. MAYO also rests on a second, newer assumption, the multi-target whipped MQ problem, which its specification calls “tailored to the MAYO signature scheme” (§5.1 in Beullens, Campos, et al., 2026). The 30 September preprint above attacks that whipped structure directly (Ostuzzi, 2026a). After the second-round attacks NIST records (National Institute of Standards and Technology, 2026), round 3 changed three of UOV’s four sets (change log in Beullens, Chen, et al., 2026) and two of MAYO’s four (change log in Beullens, Campos, et al., 2026), and replaced all of SNOVA’s (change log in Wang et al., 2026a). Rainbow, a layered Oil-Vinegar variant, was broken in 2022 (Beullens, 2022a).
Where Part IV ends and Part V picks up
Section titled “Where Part IV ends and Part V picks up”Part IV spent six chapters on the assumptions that are not lattices and not hashes. Chapter 19 set up coding theory and the decoding problem. Chapter 20 built McEliece, whose binary-Goppa line no practical attack has broken at suitable parameters since 1978, and whose public key runs to 261 kB. Chapter 20’s cryptanalysis section reports, as of October 2026, the structural analyses that call for a fresh assessment of the submitted parameters. Chapter 21 built HQC, which NIST selected in March 2025 as an additional code-based KEM and whose standard had not been published by 19 October 2026.
Chapters 22 and 23 turned to isogenies and built SQIsign, whose 283-byte public key plus signature is the smallest combined footprint in the table above. This chapter surveyed the multivariate family, which holds both ends of that table: UOV-Is’s 96-byte signature is the shortest in it and its 412 kB public key the largest.
Now the uncomfortable part of the handoff. Part V deploys none of it. None of McEliece, HQC, SQIsign, UOV, MAYO or SNOVA is deployed in Parts V, VI, or VII: Chapter 30 points back at SQIsign, and Chapter 41 names all six only to record that no chapter proposes them. The schemes that get inventoried, negotiated, and rolled out there are ML-KEM, ML-DSA, and SLH-DSA, the three that Parts II and III built and FIPS standardized, plus the stateful LMS and XMSS that Chapter 29 uses for firmware. Chapter 25 builds a CycloneDX inventory over an application. Chapter 26 is the architectural discipline for replacing an algorithm without rearchitecting the code around it. Chapter 27 covers hybrids, Chapter 28 a TLS 1.3 rollout on X25519MLKEM768, Chapter 29 a PKI and code-signing migration on Ed25519 plus ML-DSA-65, and Chapter 30 the program that runs all of it against external deadlines.
That gap is the reason to have read Part IV rather than an argument against it. Every scheme here exists because one of the standardized three might not survive, and a reader who has to answer “what if ML-DSA falls” needs to have met the alternatives and their prices. The narrower threads do resurface: Chapter 26’s agility work is what would make adopting one of these schemes a configuration change rather than a rewrite, and Chapter 33 takes up the Fiat-Shamir transform in the quantum random oracle model, the transform Chapter 23’s SQIsign relied on. The multivariate thread itself stops here, and it stops because nothing in the family is standardized yet.
Exercises
Section titled “Exercises”Exercise 1. UOV-Is public maps are homogeneous quadratic: each form is stored as an upper-triangular coefficient matrix over , one coefficient per degree-2 monomial with , and no linear or constant terms. A symmetric-matrix representation is the wrong model here: has characteristic 2, so the polar form is alternating and the diagonal coefficients are not recoverable from it, which is why the round-2 spec uses the upper-triangular form (Beullens, Chen, et al., 2025, sec. 3.2). Count the upper-triangular entries of one matrix (the diagonal entries plus the strictly upper-triangular entries). Evaluate the count for (the toy) and (UOV-Is). Compute the total public key size in bytes for UOV-Is with forms and two elements packed per byte, and verify that you recover the 412 kB quoted in the tradeoffs table.
Exercise 2. In the keygen block, each secret quadratic form has its oil-oil block zeroed. Modify the block to print the four matrix entries with , for , and confirm that all eight entries are zero. Then print the same block for the public map and observe that the entries are in general nonzero.
Exercise 3. Balanced Oil-Vinegar takes . Kipnis-Shamir 1998 recovers the oil subspace in polynomial time for balanced parameters by searching for a common invariant subspace of the pencil maps built from the polar forms of the public matrices. State in one sentence what the oil space’s preimage is to the pencil maps when , and what it stops being when . Explain in a second sentence why the unbalanced case raises the attack cost to , and say what kind of number that exponent counts.
Exercise 4. Consider two deployment scenarios. (a) A signed-message protocol carries one signature inside every packet, with a bandwidth budget of 500 bytes per packet for the signature. The public key is fetched once and cached. (b) A code-signing scheme distributes a public key to every client at install time and produces one signature per software release. The client has no inline bandwidth constraint but verifies on low-power hardware. Pick one scheme from the tradeoffs table for each scenario, argue for your choice using specific numbers from the table, and name one disadvantage the choice inherits.
Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 24. A separate track, for rebuilding rather than reading. Chapter 24 prints its whole toy, so the package exercises/ch24-multivariate hands you every function the chapter prints and stubs only the six it explains without printing: the oil-oil block extraction, the unbalance predicate, the two public-key size computations, and the two Kipnis-Shamir cost models. Grade your version against the suite that proves the reference one with PQC_IMPL=exercises pytest tests/ch24.
References
Section titled “References”Last updated: