Paper 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.

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.SAC 2021
Keywords
post-quantum cryptographydigital signaturesmultivariate quadratic cryptography
Contact author(s)
ward @ beullens com
History
2021-10-14: last of 2 revisions
2021-09-10: received
See all versions
Short URL
https://ia.cr/2021/1144
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1144,
      author = {Ward Beullens},
      title = {MAYO: Practical Post-Quantum Signatures from Oil-and-Vinegar Maps},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1144},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1144}},
      url = {https://eprint.iacr.org/2021/1144}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.