UOV and MAYO
UOV and MAYO are post-quantum digital signatures from the multivariate family, and both advanced to the third round of NIST’s additional-signatures process in May 2026. UOV, Unbalanced Oil and Vinegar, is the decades-old baseline of the multivariate signature line, valued for very short signatures but burdened by a public key that runs into the hundreds of kilobytes. MAYO is a modern UOV variant that keeps the tiny signature while cutting the public key down to a few kilobytes using a technique its authors call whipping. Neither is a finished standard, so both belong in the “track closely” pile. Their reason for existing is diversity: they give the signing world a hard-math basis that has nothing to do with the lattices under the finalized standards.
The short version:
- UOV and MAYO are multivariate signatures, resting on the difficulty of solving systems of multivariate quadratic equations, a problem Shor’s algorithm doesn’t solve.
- Their defining tradeoff is inverted size: signatures are tiny, on the order of a couple hundred bytes, while public keys are large, the opposite of most lattice signatures.
- UOV is the 1999-era baseline with a huge public key, about 272 KB at NIST level 1 in its classic form, and roughly 43 KB in a compressed variant.
- MAYO shrinks UOV’s public key to a few kilobytes with a whipping transformation while keeping a sub-200-byte signature, which is what fits it into hard byte budgets like broadcast frames.
- Both advanced to Round 3 of NIST’s additional-signatures effort in May 2026, so they’re research candidates, not FIPS standards, and the multivariate family carries extra caution because earlier schemes in it were broken.
Picture a lock with an enormous instruction manual and a one-word password. The manual is the public key: bulky, awkward to hand out, sometimes hundreds of pages. The password is the signature: short enough to say out loud. Multivariate signatures are built that way on purpose. The bulk lives in the key, which you can publish once and reuse, and the thing that travels on every message stays tiny.
UOV is the original design in this style, and its manual is genuinely huge. MAYO is the clever redraft that keeps the one-word password but slims the manual down to a pamphlet, which is what makes it usable in places where even the key has to fit somewhere small.
What are UOV and MAYO?
UOV and MAYO are digital signature schemes in the multivariate family, both submitted to NIST’s additional-signatures process. Their job is the standard signature job: a signer produces a value anyone holding the public key can verify came from that signer and wasn’t altered, which is authentication and integrity, not key establishment or confidentiality.
The two are closely related:
- UOV stands for Unbalanced Oil and Vinegar. It was proposed in 1999 by Aviad Kipnis, Jacques Patarin, and Louis Goubin as an unbalanced refinement of the earlier Oil and Vinegar design, and it’s the well-studied baseline of the multivariate signature line. Its current submission carries an expanded international team.
- MAYO is a newer scheme, designed by Ward Beullens and collaborators, that takes the UOV structure and adds a whipping transformation to expand a small secret map at signing time. The point of whipping is to keep UOV’s tiny signature while dramatically shrinking the public key.
Source: UOV submission team, project overview (design origin and team), uovsig.org; MAYO submission team, “Practical Post-Quantum Signatures from Oil-and-Vinegar Maps,” project overview, pqmayo.org.
How do UOV and MAYO work?
Both schemes sign using a secret trapdoor hidden inside a public system of quadratic equations, and both verify by checking that the signature satisfies that public system. The security rests on the fact that solving a random multivariate quadratic system is hard, while the signer’s trapdoor makes their specific system easy to solve. The flow has the same three moves as any signature scheme:
- Key generation. The signer builds a public multivariate quadratic map, the public key, together with a secret internal structure (in oil-and-vinegar terms, a hidden “oil” subspace) that makes the map invertible for the holder. That secret structure is the private key.
- Signing. To sign a message, the signer hashes it to a target, then uses the secret structure to find an input that the public map sends to that target. Finding that input is easy with the trapdoor and hard without it. The input is the signature. MAYO’s whipping step expands a small secret map at this point, which is how it keeps the public key small.
- Verification. Anyone with the public key evaluates the public quadratic map on the signature and checks that the result matches the hashed message. That confirms the signer held the trapdoor without revealing it.
Source: uovsig.org and pqmayo.org, scheme overviews.
A quantum computer doesn’t help an attacker here the way it helps against classical public-key cryptography. Shor’s algorithm breaks RSA and elliptic-curve schemes by solving factoring and discrete logarithms, and the multivariate quadratic problem these schemes rest on is neither of those. The MQ problem is NP-hard in general, and no quantum algorithm analogous to Shor’s is known against it, which is why the family sits in the post-quantum toolbox.
Why are multivariate public keys so large?
The public key is large because it has to spell out an entire system of quadratic equations, and a system big enough to resist cryptanalysis has many equations in many variables, so the coefficient table that becomes the public key grows quickly with the security parameters. The signature, by contrast, is just a single solution vector to that system, so it stays short no matter how large the key gets. This is the same inverted-size story as Classic McEliece in the KEM world, where the security lives in a big published object and only a tiny artifact crosses the wire per use.
That inversion is where UOV and MAYO differ, and it decides where each is usable.
| Scheme | NIST level | Public key | Signature |
|---|---|---|---|
| UOV (classic) | 1 | ~272 KB | Very short (about 100 bytes) |
| UOV (compressed) | 1 | ~43 KB | Very short (about 100 bytes) |
| MAYO (MAYO-2) | 1 | 4,912 bytes | 186 bytes |
Source: UOV public-key figures from uovsig.org (272 KB classic, 43 KB compressed, at NIST level 1); MAYO-2 figures (4,912-byte public key, 186-byte signature, NIST Level I) from Darzi et al. 2026, arXiv:2606.30542. [OPERATOR VERIFY the exact UOV signature byte counts (uov-Ip / uov-Is) and the full MAYO parameter table (MAYO-1/2/3/5) against the current Round 3 specifications on uovsig.org and pqmayo.org before any of these become canonical in a client deliverable; the UOV signature is described here qualitatively as “very short, about 100 bytes” rather than an exact figure, and only the MAYO-2 row is source-verified.]
The reading of the table: UOV’s classic public key is genuinely enormous, which is fine only where the key is provisioned once and reused, and its compressed variant trades some verification cost for a smaller key. MAYO’s whole contribution is getting the public key down to a few kilobytes while holding the signature under 200 bytes, which is what lets it fit surfaces that can’t budget hundreds of kilobytes for a key.
Where do UOV and MAYO actually fit?
Both fit the narrow set of cases where a signature has to be tiny and the public key can be delivered or reused separately, and where a signature basis independent of lattices is worth carrying. MAYO’s compact key widens that set. Three situations describe most of the real interest:
- Hard per-message size ceilings. Where a signature must fit inside a fixed-size frame or constrained transport block, the sub-200-byte multivariate signature fits where a lattice or hash signature would force fragmentation. The worked example that put MAYO on the map is 5G base-station broadcast authentication, where the signature must fit a roughly 372-byte broadcast information block and MAYO’s 186-byte signature does.
- Out-of-band-provisioned root anchors. Where the public key can be loaded once, into an eSIM, secure element, or firmware, and then reused, the large key is paid for a single time and only the tiny signature travels afterward. That pattern suits UOV’s classic key and MAYO alike.
- Signature-side mathematical diversity. In a crypto-agility program that doesn’t want an all-lattice signature roadmap, a multivariate scheme provides an independent failure surface, the same instinct that keeps HQC as a code-based backup on the KEM side.
Source: MAYO-2 5G broadcast worked example, Darzi et al. 2026, arXiv:2606.30542.
The property to keep in mind is that the small-signature advantage only holds when the public key doesn’t have to travel the same tight channel. On any surface that must transmit the key or a certificate on that channel, the large key erases the benefit, and a lattice scheme is usually simpler.
What is the standardization status of UOV and MAYO?
Both are Round 3 candidates in NIST’s additional digital signature schemes process, and neither is a finished standard. NIST opened that process in 2022 to add post-quantum signatures beyond the finalized ML-DSA, SLH-DSA, and FN-DSA, with a preference for designs built on math other than structured lattices. UOV and MAYO both advanced to the third round when NIST published its second-round status report, NIST IR 8610, on May 14, 2026. The multivariate family is heavily represented in that round, with four of the nine candidates being UOV or a close variant: UOV, MAYO, QR-UOV, and SNOVA.
Source: NIST IR 8610, Status Report on the Second Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process, May 14, 2026, csrc.nist.gov.
Two things shape the correct posture:
- Not FIPS, not a deployment default. Neither has a finalized standard, a CMVP validation path, or a long production track record. Both are candidates under active cryptanalysis.
- The family carries caution. Earlier multivariate signatures were broken during the standardization era, most notably Rainbow, an earlier UOV descendant. During Round 2, a series of attacks hit oil-and-vinegar designs hard and forced parameter changes on UOV, MAYO, and SNOVA to restore their claimed security. That’s the process working as intended, sustained public attack is how a scheme earns trust, but it’s also why multivariate designs are scrutinized harder than lattice or hash designs.
Source: NIST IR 8610, csrc.nist.gov; NIST, “Round 3 Additional Signatures,” csrc.nist.gov.
How do UOV and MAYO compare to the standardized signatures?
The cleanest way to place them is against the finalized-or-drafted signatures they’d eventually sit beside. All do the same signing job; they differ on math family, status, and size profile.
| Property | UOV | MAYO | ML-DSA | FN-DSA |
|---|---|---|---|---|
| Math family | Multivariate (MQ) | Multivariate (whipped UOV) | Lattice (Module-LWE) | Lattice (NTRU) |
| NIST status | Round 3 candidate | Round 3 candidate | Final (FIPS 204) | Draft |
| Public key | Very large (~43 to 272 KB) | Moderate (~4.9 KB) | ~1.3 KB and up | ~897 bytes and up |
| Signature | Very short (~100 bytes) | Very short (~186 bytes) | ~2.4 KB and up | ~666 bytes and up |
| Best fit | Out-of-band-keyed, size-critical | Compact key plus tiny signature | General-purpose default | Compact lattice option |
Source: NIST IR 8610 (statuses), csrc.nist.gov; uovsig.org and Darzi et al. 2026 arXiv:2606.30542 (multivariate sizes); NIST FIPS 204/206 (standardized sizes).
The practical reading: ML-DSA is what almost every program deploys, the balanced finalized default. UOV and MAYO are specialists for the narrow case where signature size is the hard binding constraint and the public key can be provisioned out of band, with MAYO the more deployable of the two because its key is small enough to fit far more surfaces.
Common misconceptions
- “UOV or MAYO is a NIST standard you can use.” Neither is. Both are Round 3 candidates in the additional-signatures process, with no finalized FIPS and no validation path yet.
- “The multivariate family is broken because Rainbow fell.” Rainbow, an earlier UOV descendant, was broken during the NIST process, which is exactly why the family is scrutinized hard. UOV and MAYO are distinct designs that survived into Round 3, though both had to change parameters after Round 2 attacks.
- “MAYO and UOV are interchangeable.” They share a family and a tiny-signature profile, but UOV’s classic public key runs to hundreds of kilobytes while MAYO’s whipping brings it to a few kilobytes, which is a large practical difference in where each fits.
- “The small signature makes it the best choice.” The signature is tiny, but the public key is large, so the advantage only holds where the key is provisioned out of band. Where the key has to travel the same channel, the benefit disappears.
- “These fix harvest-now-decrypt-later.” They don’t touch it. Harvest-now-decrypt-later is a key-establishment risk solved by ML-KEM. Signatures only fail once a quantum computer exists.
Questions people ask
Are UOV and MAYO NIST standards? No. Both are third-round candidates in NIST’s additional digital signature schemes process, advanced in May 2026, with no finalized standard. The finalized post-quantum signatures are ML-DSA and SLH-DSA, with FN-DSA in draft.
What’s the difference between UOV and MAYO? They share the multivariate oil-and-vinegar structure and the tiny-signature profile, but UOV’s classic public key is very large, hundreds of kilobytes at level 1, while MAYO uses a whipping transformation to cut the public key to a few kilobytes while keeping a sub-200-byte signature.
Why are the public keys so large? Because the public key has to describe a whole system of quadratic equations, and a system strong enough to resist attack needs many equations in many variables, which produces a big coefficient table. The signature is just one solution to that system, so it stays short.
When would anyone use them? Where a signature must fit a hard byte budget, like a fixed-size broadcast frame, and the public key can be provisioned once and reused. The worked example is 5G broadcast authentication, where MAYO’s 186-byte signature fits a frame that a lattice signature couldn’t.
Are they quantum-safe? Their security rests on solving multivariate quadratic systems, a problem Shor’s algorithm doesn’t address and for which no analogous quantum speedup is known. The caution is cryptanalytic maturity, not a quantum weakness.
Why does NIST want multivariate signatures at all? Because its finalized signatures lean heavily on lattices, and concentrating on one math family is a risk. A multivariate scheme gives a signature basis independent of lattices, so a future lattice break wouldn’t leave the signature world without an option.
Should my organization deploy UOV or MAYO now? No. For any signing today, use the finalized standards, ML-DSA by default. UOV and MAYO are research candidates to track and, at most, pilot on size-critical surfaces, adopted later through crypto-agility if one becomes a standard.
UOV and MAYO are what you reach for when the signature has to be a single word and the manual can live somewhere else. Everything here is the map, given freely. When your team needs to decide whether a multivariate signature belongs anywhere on your roadmap, that’s what an alignment briefing is for.
Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.