Cryptology ePrint Archive: Report 2021/1144

MAYO: Practical Post-Quantum Signatures from Oil-and-Vinegar Maps

Ward Beullens

Abstract: The Oil and Vinegar signature scheme, proposed in 1997 by Patarin, is one of the oldest and best understood multivariate quadratic signature schemes. It has excellent performance and signature sizes but suffers from large key sizes on the order of 50 KB, which makes it less practical as a general-purpose signature scheme. To solve this problem, this paper proposes MAYO, a variant of the UOV signature scheme whose public keys are two orders of magnitude smaller. MAYO works by using a UOV map with an unusually small oil space, which makes it possible to represent the public key very compactly. The usual UOV signing algorithm fails if the oil space is too small, but MAYO works around this problem by ``whipping up'' the base oil and vinegar map into a larger map, that does have a sufficiently large oil space. With parameters targeting NISTPQC security level I, MAYO has a public key size of only 614 Bytes and a signature size of 392 Bytes. This makes MAYO more compact than state-of-the-art lattice-based signature schemes such as Falcon and Dilithium. Moreover, we can choose MAYO parameters such that, unlike traditional UOV signatures, signatures provably only leak a negligible amount of information about the private key.

Category / Keywords: public-key cryptography / post-quantum cryptography, digital signatures, multivariate quadratic cryptography

Original Publication (with minor differences): SAC 2021

Date: received 9 Sep 2021, last revised 14 Oct 2021

Contact author: ward at beullens com

Available format(s): PDF | BibTeX Citation

Note: 14/10/2021: The new version has a tighter security proof

Version: 20211014:152159 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]