Whipping the Multivariate-based MAYO Signature Scheme using Hardware Platforms

NIST issued a new call in 2023 to diversify the portfolio of quantumresistant digital signature schemes since the current portfolio relies on lattice problems. The MAYO scheme, which builds on the Unbalanced Oil and Vinegar (UOV) problem, is a promising candidate for this new call. MAYO introduces emulsifier maps and a novel 'whipping' technique to significantly reduce the key sizes compared to previous UOV schemes. This paper provides a comprehensive analysis of the implementation aspects of MAYO and proposes several optimization techniques that we use to implement a high-speed hardware accelerator. The first optimization technique is the partial unrolling of the emulsification process to increase parallelization. The second proposed optimization is a novel memory structure enabling the parallelization of significant bottlenecks in the MAYO scheme. In addition to this, we present a flexible transposing technique for the data format used in MAYO that can be expanded to other UOV-based schemes. We use these techniques to design the first high-speed ASIC and FPGA accelerator that supports all operations of the MAYO scheme for different NIST security levels. Compared with state-of-the-art, like HaMAYO [24] and UOV [7], our FPGA design shows a performance benefit of up to three orders of magnitude in both latency and area-time-product. Furthermore, we lower the BRAM consumption by up to 2.8× compared to these FPGA implementations. Compared to high-end CPU implementations, our ASIC design allows between 2.81× and 60.14× higher throughputs. This increases the number of signing operations per second from 483 to 13424, thereby fostering performant deployment of the MAYO scheme in time-critical applications. CCS Concepts • Hardware → VLSI design; • Security and privacy → Cryptography; • Computer systems organization → Architectures.