Paper 2026/2577

Back to the Bits: Revisiting MAYO’s Data Representation for GPU and Tensor-Core Acceleration

Abstract

MAYO, a multivariate quadratic signature scheme with small public keys and signatures, is a third-round candidate in the additional signature standardization process of the National Institute of Standards and Technology. Cloud and application servers receiving many independent signing requests need to batch them on Graphics Processing Units (GPUs). MAYO's nibble-sliced representation suits CPU shuffle instructions or multiplication tables, but on GPUs it costs a memory access or several instructions per $\mathbb{F}_{16}$ multiplication. The existing GPU implementation cuMAYO (CHES 2026) uses the second-round nibble-sliced representation and looks up a shared-memory table per $\mathbb{F}_{16}$ multiplication. Our GPU implementation keeps all keys and intermediate values in the bitsliced representation yet matches the official Known Answer Test vectors. Its bitsliced multiply-accumulate circuit computes matrix products $32$ coefficients at a time with only word-wide AND and XOR. One thread block handles one instance; KeyGen, Sign, and Verify each run as a single kernel from the expansion of the compact key to the output; and representation conversion is confined to reading and writing specification-defined byte strings. For same-key batches, an additional tensor path decomposes $\mathbb{F}_{16}$ matrix products into binary ones and computes the large Sign and Verify matrix products on Tensor Cores. To our knowledge, the tensor path is the first use of Tensor Cores for MAYO, and ours is the first GPU implementation of the third-round specification. On an RTX 4090, the bitsliced implementation achieves $2.75\times$ to $6.73\times$ higher throughput and $6.99\times$ to $34.35\times$ lower single-shot latency than cuMAYO for all three operations of the four parameter sets. In same-key batches, the tensor path, including key preparation, reaches $13.75\times$ to $30.62\times$ the throughput of cuMAYO on distinct-key batches.