International Association for Cryptologic Research

International Association
for Cryptologic Research

Transactions on Cryptographic Hardware and Embedded Systems, Volume 2024

Nibbling MAYO: Optimized Implementations for AVX2 and Cortex-M4


Ward Beullens
IBM Research Europe, Zurich, Switzerland

Fabio Campos
RheinMain University of Applied Sciences, Wiesbaden, Germany

Sofía Celi
Brave Software, San Francisco, California

Basil Hess
IBM Research Europe, Zurich, Switzerland

Matthias J. Kannwischer
Quantum Safe Migration Center, Chelpis Quantum Tech, Taipei, Taiwan


Keywords: MAYO, Oil and Vinegar, Arm Cortex-M4, AVX2, NIST PQC


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

Publication

Transactions of Cryptographic Hardware and Embedded Systems, Volume 2024, Issue 2

Paper

Artifact

Artifact number
tches/2024/a14

Artifact published
May 31, 2024

Badge
🏆 IACR CHES Results Reproduced

README

tgz (15762523 Bytes)  

View on Github

View repository

License

Some files in this archive are licensed under a different license. See the contents of this archive for more information.


BibTeX How to cite

Beullens, W., Campos, F., Celi, S., Hess, B., & Kannwischer, M. J. (2024). Nibbling MAYO: Optimized Implementations for AVX2 and Cortex-M4. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(2), 252–275. https://doi.org/10.46586/tches.v2024.i2.252-275. Artifact available at https://artifacts.iacr.org/tches/2024/a14