Mayo Multivariate Signature Scheme

Short answer: MAYO is a post-quantum signature scheme from the multivariate family. It is a variant of the Oil and Vinegar scheme, which dates to 1997 and has small signatures but large public keys. MAYO shrinks the public key by using an unusually small oil space and then "whipping up" the map to a larger one. The authors report a 614-byte public key and 392-byte signature at the first NIST security level, which they describe as more compact than Falcon and Dilithium. These figures are the designers' own.

The Oil and Vinegar background

The MAYO specification explains that since 1985 various authors have proposed public-key schemes in which the public key is a set of multivariate quadratic equations over a small finite field. Solving such equations in general is NP-hard and is considered a good basis for post-quantum cryptography. The Oil and Vinegar scheme, proposed by Patarin in 1997, is one of the earliest signature schemes in this framework. The specification says it has withstood the test of time remarkably well despite considerable cryptanalytic efforts, with very small signatures and good performance, but somewhat larger public keys.

In the scheme, the public key is a trapdoored map made of quadratic polynomials. The trapdoor is a secret subspace, the oil space, on which the map evaluates to zero. To sign, the signer takes a salted hash of the message, picks a random vector, and then solves for a vector in the oil space so that the map hits the hash value. The specification notes that this solving step is easy because the relevant equation becomes linear in the oil vector.

What MAYO changes

The 2021 paper introducing MAYO says Oil and Vinegar has excellent performance and signature sizes but suffers from key sizes on the order of 50 KB, which makes it less practical as a general-purpose signature scheme. MAYO is a variant of UOV whose public keys are two orders of magnitude smaller. It works by using a UOV map with an unusually small oil space, which lets the public key be represented very compactly. The usual UOV signing algorithm fails if the oil space is too small, so MAYO whips up the base oil and vinegar map into a larger map that does have a sufficiently large oil space.

Reported sizes

With parameters targeting NISTPQC security level I, the paper reports a public key of 614 bytes and a signature of 392 bytes. It says this makes MAYO more compact than state-of-the-art lattice-based signature schemes such as Falcon and Dilithium. It also says MAYO parameters can be chosen so that, unlike traditional UOV signatures, signatures provably leak only a negligible amount of information about the private key.

Revisions

The paper's notes record later versions. An October 2021 version has a tighter security proof. An August 2022 version fixes certain values at design time instead of at signing time, which allows a simpler implementation, and changes the definition of the whipped map so that fields of characteristic 2 can be used. The specification credits the scheme to Beullens. Because of these revisions, check the current specification for parameters.

What this does not tell you

The size comparison is limited to public key and signature sizes at one security level, and does not cover signing speed. Multivariate schemes have a history of cryptanalysis, and the specification's remark that Oil and Vinegar has withstood scrutiny does not extend automatically to MAYO. These documents do not say MAYO is standardized or deployed.

FAQ

What family is MAYO in?

Multivariate quadratic signatures, as a variant of Oil and Vinegar.

What problem does it solve?

Oil and Vinegar has large public keys, about 50 KB, which MAYO reduces by two orders of magnitude.

How does it shrink the key?

By using a small oil space and whipping up the map to a larger one for signing.

How big are the keys and signatures?

614-byte public key and 392-byte signature at level I, per the authors.

Is it standardized?

These documents do not report that.