eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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
Abstract

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.2x 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 a factor of 2-6 slower than lattice-based signature schemes on Cortex-M4 (which can still be considered competitive).

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in TCHES 2024
Keywords
MAYOmultivariate cryptographyAVX2Cortex-M4
Contact author(s)
ward @ beullens com
campos @ sopmac de
cherenkov @ riseup net
bhe @ zurich ibm com
matthias @ kannwischer eu
History
2024-01-15: revised
2023-10-30: received
See all versions
Short URL
https://ia.cr/2023/1683
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1683,
      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{https://eprint.iacr.org/2023/1683}},
      url = {https://eprint.iacr.org/2023/1683}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.