Paper 2023/1267

Whipping the MAYO Signature Scheme using Hardware Platforms

Abstract

NIST recently issued a new call to diversify the portfolio of quantum-resistant digital signature schemes since the current portfolio solely relies on lattice problems. A promising candidate for this new call is the MAYO scheme that builds on the Unbal- anced Oil and Vinegar (UOV) problem. The MAYO scheme introduces emulsifier maps and a novel whipping technique to significantly reduce the signature and key sizes compared to previous UOV schemes. This paper provides a comprehensive analysis of the MAYO scheme and proposes multiple adaption and optimization techniques for an efficient hardware accelerator. The first proposed adaption is that we sample data on-the-fly and immediately use it for computation which saves a significant amount of memory. The second adaption is the replacement of the slow data sampling via Aes128 by the faster Shake128. This improves the overall performance of data sampling in hardware while reducing resource consumption. We further increase the performance of our architecture via a novel memory structure capable of parallelizing major computations in the MAYO scheme. In addition, we also present a flexible transposing technique for the data format used in MAYO. We use these techniques to design a hardware accelerator that supports all operations of the MAYO scheme. The supported operations include key generation, signing, and verification for different NIST security levels. Comparisons show that our design massively outperforms HaMAYO [SMA + 23] and UOV [BCH + 23] by one to three orders of magnitude. HaMAYO has a 83× and 71× higher latency for key generation and signature generation, respectively. Comparisons with UOV show a performance increase of 1016×, 460×, and 607× in key generation for NIST security levels 1, 3, and 5, respectively. Furthermore, our signature generation and verification show a performance benefit of two orders of magnitude compared to both works. In addition to performance improvement, the presented optimized memory management shows a 2× to 3× lower BRAM consumption for multivariate schemes on FPGA platforms.