Skip to content

MAYO Seal

MAYO · NIST PQC On-Ramp

Runs real MAYO keygen, signing and verification over GF(16) so you can watch an oil space with far too few variables to hit a target become workable the moment k copies of the map are whipped together.

Start here

What is a multivariate signature?

A public key here is a bag of quadratic equations in many variables. Signing means finding an input that makes those equations produce exactly the numbers your message hashes to; verifying means plugging the signature in and checking you get those same numbers. Solving such a system is hard in general — that is the security — so the signer needs a secret shortcut. In Oil-and-Vinegar the shortcut is a hidden linear subspace, the oil space, on which every equation collapses to zero.

The catch: the shortcut only works if the oil space is at least as big as the number of equations, and a big oil space forces a big public key. MAYO shrinks the oil space until the shortcut stops working, then repairs it by whipping: it publicly stirs k copies of the same map together, so the signer gets k times as many unknowns to play with while the number of equations stays put.

The whole idea in one picture

The signing system is m rows tall and k·o columns wide. MAYO picks enough columns that a draw almost always has full row rank, with solutions to spare. Turn k and watch the width cross the line — the numbers are the real ones for the parameter set you pick, and both probabilities below are computed.

  1. Secret structure makes it linear. Fixing the vinegar and knowing the oil space O turns the quadratic map into a linear system A·x = y. Whipping does not do this — the trapdoor does.
  2. Whipping supplies enough variables. k copies turn o unknowns into k·o, while every copy keeps the same hidden oil space, so the trapdoor survives.
  3. Both together let the signer solve. Linear and wide enough. Neither one is sufficient: a wide system with no trapdoor is still a hard multivariate problem.

Exhibit 2 then runs this for real: the same relationship, but with an actual key, an actual message and the actual Gaussian elimination.

Jargon, unpacked
GF(16)
The field with 16 elements. Every number in this page is one of 0–f, one hex digit, and MAYO packs two of them per byte. Addition is XOR; multiplication is polynomial multiplication modulo x⁴ + x + 1.
n, m, o, k
n variables, m equations, oil space of dimension o, and k copies whipped together. The whole scheme is a choice of these four numbers.
Vinegar and oil
A signature input splits into n − o "vinegar" coordinates the signer picks at random and o "oil" coordinates it then solves for. Oil never multiplies oil in the public map — that missing term is the trapdoor.
Whipping / the emulsifier
MAYO's new ingredient: fixed public matrices E⁰, E¹, … (multiplication by z, z², … in a finite field) that combine k copies of the map into one map with the same m outputs but k·n inputs.
Rank
The number of genuinely independent equations in a system. Six equations with rank four contain two that add no information. A signer needs the rank to equal m, and MAYO checks rather than assumes it.
"Vanishes on O"
Every point of the secret oil space maps to zero under the public map — all m outputs are zero at once. That is what lets the signer move along the oil space without disturbing the equations, and Exhibit 1 computes it rather than claiming it.
Salt, target t
The message digest plus a per-signature salt are hashed into the target vector t ∈ GF(16)ᵐ. Hitting t is exactly what a valid signature does.

Not production crypto — a teaching demo. Real MAYO1/MAYO2/MAYO3/MAYO5 parameters are implemented and KAT-verified, but this code is not constant-time and makes no side-channel claims.

Your signature

One key, one message, followed all the way through

Pick a parameter set and a message once, here, and every exhibit below uses them. The key you generate is the key that signs; the signature you watch being assembled is the one the verifier accepts and the one you break. Nothing on this page is a re-enactment of something computed elsewhere.

    Exhibit 1

    Keygen: a needle small enough to shrink the haystack

    A MAYO public key is a 16-byte seed plus one block, P⁽³⁾. Everything else — P⁽¹⁾ and P⁽²⁾, hundreds of kilobytes of it — is expanded from the seed by AES-128-CTR, identically by signer and verifier, so it never travels. Only P⁽³⁾ must be shipped, and P⁽³⁾ is m·o(o+1)/2 field elements: quadratic in the oil dimension. Shrink o and the key shrinks with the square.

    Exhibit 2 — the headline mechanism

    Sign: watch too few oil variables become enough

    This is the whole idea in three beats. With one copy of the map the signer faces m equations in only o unknowns and almost always fails; whip k copies together and it is the same m equations in k·o unknowns. Start on the toy parameters, where every number fits on screen, then run the identical walkthrough on real MAYO1 or MAYO2 — the matrices are drawn as a corner there, but every number in them is the real one. The five spec operations behind these three beats are one disclosure away, and they run the same computation.

    1. 1

      One copy misses

      Waiting

      Fixing the vinegar makes the map linear in the oil coordinates — that is the trapdoor, and it is the only reason the signer can solve anything at all. But one copy offers only o unknowns against m equations, so elimination runs out of unknowns and the last row reads 0 = something.

    2. 2

      Whipping adds room

      Waiting

      Stir k copies of the same map together, each with its own vinegar and its own power of z. The oil unknowns become k·o while the equation count stays at m, and every copy keeps the same hidden oil space — so the system gets wider without losing the trapdoor.

    3. 3

      Solve and check

      Waiting

      Now elimination finds oil coordinates, the signature is assembled from them, and the public whipped map evaluated on that signature lands exactly on the target the message hashed to.

    Show the full signing algorithm

    The same run, opened out into the five operations the spec names. Nothing here is recomputed — these panels and the three beats above are two views of one signature.

    1. 1

      Hash the message into a target t

      Waiting

      The salt and the target both come from SHAKE256. A signature is valid exactly when the whipped map lands on this t.

    2. 2

      Fix the vinegar, then try one unwhipped copy

      Waiting

      With the vinegar frozen, the remaining unknowns are the o oil coordinates and the system is linear. It is also over-determined, so echelon form usually ends in a row that reads 0 = something.

    3. 3

      Whip k copies together

      Waiting

      Each unordered pair (i, j) of copies contributes its term multiplied by a different power of z. The grid below is the spec's Z matrix: the exponent ℓ used for each pair.

    4. 4

      Solve the whipped system

      Waiting

      Same m rows, now k·o columns. Gaussian elimination over GF(16), then back-substitution.

    5. 5

      Assemble the signature and check it lands on t

      Waiting

      Each block is sᵢ = (vᵢ + O·xᵢ ‖ xᵢ). Evaluating the public whipped map on s must reproduce t exactly.

    Exhibit 3 — break it yourself

    Verify: compute both sides, then try to fool it

    Verification recomputes t from the message and salt, evaluates the public whipped map on the signature, and compares the two vectors coordinate by coordinate. Nothing is asserted here — both sides are shown. Then tamper with any input you like and watch the real verifier answer.

    Exhibit 4 — try to forge one

    Forge it without the trapdoor

    Tampering breaks a signature; forging means making one from nothing. Two honest attempts are available here, and both run the real code. Guess s and the salt at random and count how close you get — each of the m coordinates lands by luck one time in sixteen. Or keep the real key material and change only the oil space: the linear algebra still succeeds and the signature is still the right length, but the public map vanishes on the real oil space alone, so the verifier still says no.

    Exhibit 5

    UOV versus MAYO, by the byte

    Classic Oil-and-Vinegar is the k = 1 corner of this same construction: one copy means the signer must solve m equations in o unknowns, so o has to be at least m. Feed o = m into MAYO's own public-key formula and the key explodes. Every number in the first table is computed here from the size formulas, not quoted.

    The same security level, nine different (o, k) splits

    Spec Table 2.2, NIST level 1. Reading down the table the oil space grows, k shrinks, the public key grows and the signature shrinks. The top row is MAYO1; the bottom row, k = 2, is nearly UOV.

    Proof lab

    Everything above teaches the idea. What follows answers a different question — how do you know this page is telling you the truth? None of it is required to understand MAYO.

    Exhibit 6 — proof lab

    The real thing: reference vectors and preconditions, checked here

    The same code that drives the toy exhibits runs the shipped MAYO parameter sets. Pick a vector from the round-2 submission's KAT files: the page seeds NIST's AES-256-CTR-DRBG exactly as the KAT harness does, derives the keypair and the signature, and compares its own bytes against the reference hex.

    The preconditions, checked in your browser

    MAYO only works if several structural facts hold: f(z) irreducible, f not dividing det Z, every non-trivial combination of the E matrices at full rank, the public map vanishing on the oil space and the whipped map on Oᵏ, and the sizes matching Table 2.1. The test suite asserts all of them in CI — but a page that merely claims them is asking to be trusted, so here they are recomputed on demand.

    Recap

    MAYO in four lines

    If you remember nothing else from this page, remember these. Each one is something you watched happen above, not something you were told.

    1 · The problem

    Oil-and-Vinegar signing needs at least as many oil unknowns as there are equations, so o ≥ m. The shipped part of the public key grows with o², which is why classic UOV keys run to tens of kilobytes.

    2 · The compression

    MAYO shrinks o far below m. That makes the key small — and it breaks signing, because one copy of the map no longer offers enough unknowns to hit a target.

    3 · The repair

    Whipping stirs k copies together with fixed public matrices. The signer now has k·o unknowns against the same m equations, and because every copy keeps the same hidden oil space, the trapdoor survives intact.

    4 · The cost

    A compact public key, paid for with a longer signature: k blocks of n field elements instead of one. Each shipped set picks the smallest k with k·o > m, so it buys room and nothing more.

    One thing the picture can mislead you about: a wide system is not automatically an easy one. Width only helps because the secret oil space already turned the quadratic map into a linear one. Without the trapdoor, k·o unknowns would leave you facing exactly the multivariate problem MAYO's security rests on.

    Honest scoping

    What this demo does and does not prove

    Real here

    Hand-rolled GF(16), the spec's encodings, echelon form and SampleSolution, the whipping construction, and MAYO.CompactKeyGen / ExpandSK / ExpandPK / Sign / Verify. Every verdict on this page — including every failed forgery — is the real MAYO.Verify answering. SHAKE256 and AES-128-CTR come from @noble. Six reference KAT vectors across MAYO1, MAYO2, MAYO3 and MAYO5 pass byte for byte.

    Not proven here

    Nothing about MAYO's security. Exhibit 4 lets you attempt a forgery and watch it fail, but that is a demonstration of the odds, not cryptanalysis: no key-recovery attack and no attack with any advantage over guessing is implemented or claimed. The only way a signature verifies on this page is by being made with the real oil space. The toy parameter set is breakable by hand and is labelled as such wherever it appears.

    Not built: classic UOV internals

    MAYO is UOV's successor, so this page shows the delta, not the ancestor. For the Oil-and-Vinegar trapdoor itself — and for the Rainbow / Beullens break that reshaped this whole family — see crypto-lab-multivariate.

    Not built: side channels

    This implementation is not constant-time. Fault and side-channel attacks on multivariate signing are a real threat and a separate subject; see crypto-lab-lattice-fault for how that genre of attack works on a post-quantum signer.

    Not built: the other on-ramp candidates

    QR-UOV and SNOVA are also multivariate on-ramp submissions with their own structure. They are out of scope; nothing here should be read as a comparison against them.

    Not production

    Keys live in memory for the length of a page view and are never persisted or transmitted; there is no backend. Use a reviewed implementation for anything real — the reference code is at PQCMayo/MAYO-C.