Paper 2026/2705

SpreadMAYO: Unlocking Greater Parallelism for Faster MAYO Signatures on GPUs

Abstract

Quantum computing threatens public-key cryptography, motivating post-quantum signature standardization. MAYO, a multivariate Round 3 candidate in NIST's additional signature process, offers compact keys and signatures. However, prior GPU implementations do not fully exploit parallelism within each MAYO operation: equation-slice partitioning serializes independent matrix work, while signing requires frequent synchronization among threads during linear-system construction and elimination. We present SpreadMAYO, a high-throughput GPU implementation of MAYO Round 3 that exposes greater parallelism and reduces synchronization through finer task partitioning and a revised signing pipeline. SpreadMAYO distributes matrix contractions across rows, output positions, and 64-bit limbs while reusing operands in registers. Each limb packs sixteen GF(16) coefficients; native 32-bit operations process its halves without lookup tables. For signing, threads privately accumulate columns with deferred polynomial reduction, transpose packed columns into rows using warp shuffles, and eliminate rows below each pivot in parallel. Additionally, we employ a hybrid AES design to accommodate different workloads and fuse key expansion with matrix computations to reduce global-memory traffic. On an NVIDIA GeForce RTX 4090, SpreadMAYO outperforms the Round 3 adapted GPU baseline by 2.33–3.71× in key generation, 4.40–6.93× in signing, and 3.42–5.13× in verification, reaching up to 10.75× in repeated-key server signing.