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, 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 UOV and SNOVA sizes below are from their round-2 submission packages. MAYO’s are from its round-3 specification of 31 August 2026. All of them may change under third-round revision, 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), compare UOV, MAYO, and SNOVA on key and signature sizes, and place multivariate alongside the other four 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. MQ NP-completeness follows from a 3-SAT reduction in the style of (Garey & Johnson, 1979), with subsequent work extending the result to arbitrary finite fields (see (Kipnis et al., 1999, sec. 1) for the cryptographic framing). The best known classical algorithms for random systems at cryptographic parameters (F5, XL, crossbred, hybrid) run in time exponential in . The round-2 UOV specification costs the state-of-the-art variant: a Thomae-Wolf reduction of the underdetermined system, then hybrid Wiedemann-XL (Beullens 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). Modern UOV parameter sets at NIST level 1 use on the order of 160 and on the order of 64, a ratio well above .
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 modelling 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.
Round-2 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 specification tabulates four for UOV-Is (Table 5 in Beullens et al., 2025):
| Attack | Type | Cost (bits) |
|---|---|---|
| Collision | Forgery | 143 |
| Direct | Forgery | 165 |
| Kipnis-Shamir | Key recovery | 154 |
| Intersection | Key recovery | 176 |
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). UOV-Is clears its target on that row with nothing to spare, which is worth remembering when reading the third-round revisions.
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., 2025). 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 opened after 2022, which is distinct from the standardization round that ran from 2017 to 2022 in which 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 UOV and SNOVA parameter sets quoted below are from the round-2 submission packages. MAYO’s are from its round-3 specification of 31 August 2026, which superseded the round-2 figures this chapter carried until then.
UOV. The direct descendant of (Kipnis et al., 1999). Its round-2 submission lists four parameter sets across NIST security levels 1, 3, and 5 (Table 1 in Beullens, Chen, et al., 2025). The level-1 set UOV-Is 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., 2025). The 412 kB figure quoted throughout this chapter is the classic one, which is the number NIST cites when it describes UOV’s cost as “public keys over 200 kilobytes in expanded form” (National Institute of Standards and Technology, 2026).
MAYO. A UOV variant introduced by Beullens in 2021 (Beullens, 2022). 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 evaluations of the small map into one larger map on variables, chosen so that vanishes on a space of dimension . Parameters are set so , at least as many oil variables as equations, which restores a large enough oil space to solve in (Beullens et al., 2026, sec. 1 and §2.1.1). 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 et al., 2026). Round 2 had , 1,420 bytes and 454 bytes, and the team describes the change as a two percent size cost paid for margin against direct attack.
Round 3 changed more than parameters, and the change log is worth reading as a record of what a third round does to a scheme. MAYO2 was reparameterised to after the wedge attack described below, at 2,928 bytes and 239 bytes, with rather than the planned 82 to push a key-recovery attack that Ran and Merz reported privately days before the deadline above . The whipping schedule became an MDS matrix, because the round-2 ordering of the left low-rank submatrices that mildly sped up collision attacks. And the verification equation gained a linear term, with the coefficients of derived from the hash of the message and salt, after three research teams independently reported an improved claw-finding attack in August 2026, all using AI-assisted cryptanalysis. The team reports that the new attack cuts the cost of the previous claw-finding attack by factors of up to , , and for MAYO1, MAYO2, MAYO3 and MAYO5. The resulting estimates land slightly below their targets (change log and §5 in Beullens et al., 2026). The factors measure the speedup over the old attack, not the shortfall against the target, which the specification does not quantify. The linear term is an idea from the original 1999 UOV paper, revived.
SNOVA. An Oil-Vinegar variant defined over a non-commutative matrix ring rather than a finite field (Wang et al., 2025). 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). The round-2 parameter families are named SNOVA- after vinegar count , oil count , field size , and matrix dimension . The NIST level-1 set SNOVA- reports a 1,016-byte public key and a 248-byte signature (Table 6 in Wang et al., 2025). A second level-1 point, SNOVA-, trades a larger 9,842-byte public key for a shorter 124-byte signature. The saving is on the key side alone: both signatures are longer than UOV-Is’s 96 bytes (Table 1 in Beullens, Chen, et al., 2025). Equation counts do not compare directly either, because SNOVA counts equations over the matrix ring. SNOVA- has equations over , which is 80 scalar equations against UOV-Is’s 64 (Wang et al., 2025, sec. 1.3).
Read both figures as historical. They are round-2 numbers, and the wedge-product variant discussed below broke most of the round-2 sets, so neither is safe to quote as a current parameter choice. The team has since proposed a modification 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). SNOVA is described here but kept out of the closing tradeoffs table, because NIST does not see it as having reached a stable form.
Cryptanalysis: MinRank, Grobner bases, and the quantum picture
Section titled “Cryptanalysis: MinRank, Grobner bases, and the quantum picture”Two attacks set the floor for multivariate parameter sizes: the Kipnis-Shamir invariant-subspace attack on balanced schemes, which the UOV specification lists separately from the MinRank family it also prices, and direct Grobner-basis solving of the public system. Grover’s algorithm sets the quantum bound.
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. 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 is . Round 2 refines it and tabulates 154 bits for UOV-Is, against for the search factor alone (Beullens, Chen, et al., 2025, sec. 4.3).
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 round-2 specification costs the direct attack differently and does not use that terminology: it reduces the underdetermined system first, then applies hybrid Wiedemann-XL at an operating degree read off a power-series expansion (Beullens, Chen, et al., 2025, sec. 4.2). The UOV public system’s structure does not justify assuming the generic estimate applies to it, so this figure is heuristic. Round-2 parameters are set by the best known direct forgery and key-recovery attacks, not by the semi-regular estimate alone. MAYO and SNOVA parameter justifications include analogous Macaulay-matrix cost estimates (Beullens, Campos, et al., 2025; Wang et al., 2025).
Quantum picture. No polynomial-time quantum algorithm for random MQ is known. Grover’s algorithm reduces a brute-force search over to roughly oracle queries. The round-2 specification states that every known quantum attack on UOV is a classical attack with some part sped up by Grover, so none of them improves on the classical cost by more than a square-root factor (Beullens, Chen, et al., 2025, sec. 4.6). Round-2 UOV, MAYO, and SNOVA NIST level-1 parameter sets target the Grover cost at or above the NIST level-1 quantum threshold (the quantum cost of AES-128 exhaustive key search) (Beullens, Campos, et al., 2025; Beullens, Chen, et al., 2025; Wang et al., 2025).
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 round-2 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 wedge attack uses exterior products to expose the hidden oil subspace in characteristic 2, and a follow-up exploited small field characteristics.
Which sets fell is worth stating precisely, because the tradeoffs table below quotes two of them. For UOV the two attacks together brought UOV-Ip, UOV-III, and UOV-V below their target security strengths, leaving UOV-Is the one set of four still meeting its target. For MAYO the wedge attack cost MAYO2 roughly 30 bits at category 1, and left MAYO1 unaffected; the round-3 specification reparameterised MAYO2 in response, as the MAYO paragraph above records. NIST attributes the difference to the balance between the number of quadratic forms and the codimension of the secret subspace, not to the whipping structure. 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 the IR’s own reference 10, and it reports breaking 6 of the 11 second-round SNOVA parameter sets and improving the best known result on two more (Bros et al., 2026). So the two multivariate rows in the table below, UOV-Is and MAYO1, are the surviving sets rather than arbitrary picks.
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. QR-UOV is the one whose proposed parameters were untouched, 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.
Two of those margins have narrowed since the IR. A preprint revised on 10 September 2026 reworks the direct attack on the underdetermined MQ problem, computing richer pseudo-oil structures and spreading the algebraic work across more than two Grobner-basis steps, and reports lowering the cost of that attack against the Security Level I parameter sets of MAYO and QR-UOV by 7 and 8 bits (Ostuzzi, 2026). That narrows a margin rather than breaking a set, and it is a direct attack rather than a wedge attack, so NIST’s finding that QR-UOV resists the wedge family and its variants stands. It is also a preprint under community review, and the sizes in the table below are unaffected: the table 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, 2024). 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, the round-2 UOV submission, and the round-3 SQIsign 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 | 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, 2024); SLH-DSA-128s from (Table 2 in National Institute of Standards and Technology, 2024b); UOV-Is from (Table 1 in Beullens, Chen, et al., 2025); MAYO1 from (Table 2.1 in Beullens 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 about 153 kB before verification (Table 2.1 in Beullens et al., 2026). Compared like for like, MAYO1 is roughly 46 times smaller than UOV-Is compact and roughly three 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., 2025) 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 et al., 2026) is small enough for slow-rotating cached-key surfaces where the key is published once and cached. Chapter 23 identifies block-producer rotation 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. At chain-tip 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 (National Institute of Standards and Technology, 2026). Chapter 39 covers the consensus and validator-signature surfaces; Chapter 41 covers the governance multisig 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. The isogeny endomorphism-ring assumption was formalized for cryptographic use in the 2020 SQIsign paper, and SIDH was broken in 2022 (see Chapter 22). The MQ plus Oil-Vinegar assumption base dates from 1999 for UOV, but the specific round-2 parameter sets are from 2024 and 2025. They remain under active third-round revision after recent attacks on several UOV, MAYO, and SNOVA parameter sets (National Institute of Standards and Technology, 2026). 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, unbroken in its binary-Goppa line at suitable parameters since 1978 and paying for it with a 261 kB public key. Chapter 21 built HQC, which NIST selected in March 2025 as an additional code-based KEM and whose standard is still unpublished. 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. McEliece, HQC, UOV, MAYO, and SNOVA appear nowhere in Parts V, VI, or VII, and SQIsign appears once, where Chapter 30 points back at it rather than deploying it. 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. 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: