Paper 2023/1683

Nibbling MAYO: Optimized Implementations for AVX2 and Cortex-M4

Ward Beullens, IBM Research - Zurich
Fabio Campos, RheinMain University of Applied Sciences
Sofía Celi, Brave Software
Basil Hess, IBM Research - Zurich
Matthias J. Kannwischer, Quantum Safe Migration Center, Chelpis Quantum Tech

MAYO is a popular high-calorie condiment as well as an auspicious candidate in the ongoing NIST competition for additional post-quantum signature schemes achieving competitive signature and public key sizes. In this work, we present high-speed implementations of MAYO using the AVX2 and Armv7E-M instruction sets targeting recent x86 platforms and the Arm Cortex-M4. Moreover, the main contribution of our work is showing that MAYO can be even faster when switching from a bitsliced representation of keys to a nibble-sliced representation. While the bitsliced representation was primarily motivated by faster arithmetic on microcontrollers, we show that it is not necessary for achieving high performance on Cortex-M4. On Cortex-M4, we instead propose to implement the large matrix multiplications of MAYO using the Method of the Four Russians (M4R), which allows us to achieve better performance than when using the bitsliced approach. This results in up to 21% faster signing. For AVX2, the change in representation allows us to implement the arithmetic much faster using shuffle instructions. Signing takes up to 3.2 times fewer cycles and key generation and verification enjoy similar speedups. This shows that MAYO is competitive with lattice-based signature schemes on x86 CPUs, and only a factor 2-6 slower than lattice-based signature schemes on Cortex-M4.

Available format(s)
Publication info
MAYOmultivariate cryptographyAVX2Cortex-M4
Contact author(s)
ward @ beullens com
campos @ sopmac de
cherenkov @ riseup net
bhe @ zurich ibm com
matthias @ kannwischer eu
2023-11-03: approved
2023-10-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ward Beullens and Fabio Campos and Sofía Celi and Basil Hess and Matthias J. Kannwischer},
      title = {Nibbling MAYO: Optimized Implementations for AVX2 and Cortex-M4},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1683},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.