Skip to content

Back to the catalog

eprint.iacr.orgpaper

SpreadMAYO: Unlocking Greater Parallelism for Faster MAYO Signatures on GPUs

SpreadMAYO is a GPU implementation of MAYO Round 3, a multivariate post-quantum signature scheme in NIST's additional signature process (ePrint 2026/2705, October 2026). It spreads matrix contractions across rows, output positions and 64-bit limbs of packed GF(16) values. On an RTX 4090 it reports 4.40 to 6.93x faster signing, 3.42 to 5.13x faster verification and 2.33 to 3.71x faster key generation than the baseline, up to 10.75x for repeated-key signing. No constant-time analysis was in the available text.

TL;DR Presents a GPU MAYO signature implementation that speeds up signing, verification and key generation on an RTX 4090 over a prior GPU baseline.
Open original ↗
Document

What it is

SpreadMAYO is a GPU implementation of MAYO Round 3, a multivariate signature candidate in NIST's additional signature process. It is a preprint (ePrint 2026/2705, received 31 October 2026, approved 4 November 2026) by Zhuoyu Xie, Tian Zhou, Fangyu Zheng and co-authors. It is compared against a "Round 3 adapted GPU baseline" on an NVIDIA GeForce RTX 4090.

How it works

The paper says earlier GPU work partitions by equation slice, which serializes independent matrix work, and that signing needs frequent thread synchronization while building and eliminating the linear system. The abstract describes these changes:

  • Matrix contractions are split across rows, output positions and 64-bit limbs, with operands reused in registers.
  • Each limb packs sixteen GF(16) coefficients. Native 32-bit operations handle its two halves, so no lookup tables are needed.
  • In signing, threads accumulate columns privately and defer polynomial reduction. Packed columns are transposed into rows with warp shuffles. Rows below each pivot are then eliminated in parallel.
  • A hybrid AES design is used to suit different workloads.
  • Key expansion is fused with the matrix computations to cut global-memory traffic.

Results

Speedups over the baseline are 2.33 to 3.71x for key generation, 4.40 to 6.93x for signing and 3.42 to 5.13x for verification. Repeated-key server signing reaches up to 10.75x. The best case is therefore a server that signs many messages under one key.

Caveats

The available text is the abstract and metadata only. It gives no absolute throughput or latency, no batch sizes, no parameter-set breakdown, and no GPUs other than the RTX 4090. It does not say which of the changes contributes most to the gain. It says nothing about constant-time behavior. That matters because table-free arithmetic and warp-level elimination are the parts a side-channel review would examine. The work is not peer reviewed, and the paper does not say whether code is released.

Organisations named here

  • NIST

Technologies named here

  • MAYO
  • AES
  • GeForce RTX 4090
  • NVIDIA GeForce RTX 4090
  • SpreadMAYO

Standards and laws named here

  • NIST additional signature process

Techniques named here

  • Deferred polynomial reduction
  • Fused key expansion
  • Hybrid AES design
  • Packed GF(16) arithmetic
  • Parallel row elimination
  • Warp shuffle transposition

Concepts named here

  • GF(16)
  • GPU parallelism
  • Multivariate signatures
  • Repeated-key server signing
  • Zhuoyu Xie

Related in other