params and times

Parameters:

The parameter sets below are the ones of our round-3 submission.

We select and implement four parameter sets: For NIST security level 1, we select two parameter sets: MAYO_one and MAYO_two, where MAYO_one has smaller public keys but larger signatures and conversely MAYO_two has smaller signatures but larger public keys. For NIST security level 3 and NIST security level 5, we select one parameter set each, which we refer to as MAYO_three and MAYO_five, respectively. The parameter sets and the corresponding key and signature sizes are displayed below. All sizes are reported in bytes -B-.

Parameter set	`MAYO_one`	`MAYO_two`	`MAYO_three`	`MAYO_five`
security level	1	1	3	5
$(n,m,o,k,q)$	(88, 80, 8, 10, 16)	(86, 64, 13, 5, 16)	(118, 108, 10, 11, 16)	(154, 142, 12, 12, 16)
secret key size	24 B	24 B	32 B	40 B
public key size	1456 B	2928 B	2986 B	5554 B
signature size	464 B	239 B	681 B	964 B

Our specification also lists a range of additional parameter sets that showcase the possible trade-offs between public key size and signature size at each security level.

Cycle counts:

The fastest results on Intel x86-64 are on the 2.0 GHz Ice Lake platform, on which MAYO_two performs KeyGen in 26.9 μs, Signing (+ExpandSK) in 50.6 μs, and Verifying (+ExpandPK) in 20.9 μs with the GFNI/AVX-512 implementation. Batch signing (without ExpandSK) takes 31.3 μs, and batch verification (without ExpandPK) takes 11.4 μs.

All builds use -O3 compiler optimization level and -march=native build architecture. Turbo Boost was deactivated to achieve consistent timings. We report the CPU cycles using AES-NI. More results can be found in our specification.

Cycle counts for our GFNI/AVX-512 optimized implementation:

The GFNI implementation requires the AVX-512F, AVX-512BW, and GFNI instruction set extensions, available on Intel server architectures since Ice Lake and on AMD architectures since Zen 4. It was therefore evaluated on Ice Lake only.

On Intel Xeon Gold 6338 CPU (Ice Lake) with 2.0 GHz:

Scheme	KeyGen	ExpandSK + Sign	ExpandPK + Verify
`MAYO_one`	66,210	166,390	73,926
`MAYO_two`	53,874	101,126	41,890
`MAYO_three`	149,334	337,246	152,066
`MAYO_five`	325,646	752,656	348,120

The library was compiled on Ubuntu with clang version 18.1.8. Results are the median of 1000 benchmark runs.

Cycle counts for our AVX2 optimized implementation:

On Intel Xeon Gold 6338 CPU (Ice Lake) with 2.0 GHz for the AVX2 optimized implementation:

Scheme	KeyGen	ExpandSK + Sign	ExpandPK + Verify
`MAYO_one`	87,002	289,238	119,452
`MAYO_two`	72,552	140,176	49,064
`MAYO_three`	197,720	597,392	244,284
`MAYO_five`	571,546	1,515,402	639,410

The library was compiled on Ubuntu with clang version 18.1.8. Results are the median of 1000 benchmark runs.

On Intel Xeon E3-1225 v3 CPU (Haswell) at 3.20GHz for the AVX2 optimized implementation:

Scheme	KeyGen	ExpandSK + Sign	ExpandPK + Verify
`MAYO_one`	190,996	466,134	242,382
`MAYO_two`	152,835	232,389	112,449
`MAYO_three`	451,465	1,015,330	528,461
`MAYO_five`	1,137,678	2,390,175	1,254,135

The library was compiled on Ubuntu with clang version 18.1.3. Results are the median of 1000 benchmark runs.

On Intel i7-6700T CPU (Skylake) at 2.80GHz for the AVX2 optimized implementation:

Scheme	KeyGen	ExpandSK + Sign	ExpandPK + Verify
`MAYO_one`	149,119	363,653	188,988
`MAYO_two`	123,843	175,504	86,956
`MAYO_three`	361,791	789,086	407,824
`MAYO_five`	890,231	1,852,715	969,107

The library was compiled on Debian with clang version 19.1.7. Results are the median of 1000 benchmark runs.

Cycle counts for our optimized implementation:

On Intel Xeon Gold 6338 CPU (Ice Lake) with 2.0 GHz for the optimized implementation:

Scheme	KeyGen	ExpandSK + Sign	ExpandPK + Verify
`MAYO_one`	890,892	2,531,962	320,660
`MAYO_two`	1,599,408	909,718	98,106
`MAYO_three`	3,424,220	6,945,436	802,626
`MAYO_five`	6,943,014	15,877,932	1,558,240

The library was compiled on Ubuntu with clang version 18.1.8. Results are the median of 1000 benchmark runs.

On Intel Xeon E3-1225 v3 CPU (Haswell) at 3.20GHz for the optimized implementation:

Scheme	KeyGen	ExpandSK + Sign	ExpandPK + Verify
`MAYO_one`	944,171	2,349,559	471,308
`MAYO_two`	977,728	1,052,726	169,372
`MAYO_three`	2,754,470	6,245,908	1,158,512
`MAYO_five`	8,485,033	18,541,749	2,137,340

The library was compiled on Ubuntu with clang version 18.1.3. Results are the median of 1000 benchmark runs.

On Intel i7-6700T CPU (Skylake) at 2.80GHz for the optimized implementation:

Scheme	KeyGen	ExpandSK + Sign	ExpandPK + Verify
`MAYO_one`	839,914	1,831,210	370,396
`MAYO_two`	765,983	817,049	131,986
`MAYO_three`	2,478,116	4,789,861	894,661
`MAYO_five`	6,595,713	14,340,039	1,696,101

The library was compiled on Debian with clang version 19.1.7. Results are the median of 1000 benchmark runs.

Arm Cortex-M4 implementation:

We use the ST NUCLEO-L4R5ZI development board which comes with a STM32L4R5ZI Cortex-M4 CPU with $2$MB of flash memory and $640$KB of SRAM.

All builds use -O3 compiler optimization level using the Arm GNU toolchain.

Scheme	KeyGen	ExpandSK + Sign	ExpandPK + Verify
`MAYO_one`	9,631,297	19,223,231	11,539,985
`MAYO_two`	8,898,780	10,312,833	6,888,289
`MAYO_three`	27,169,341	43,708,718	28,475,402

The library was compiled with the Arm GNU toolchain (arm-none-eabi-gcc 13.2.1). Results are the average of 1000 benchmark runs.

Arm Neon implementation:

The NEON implementation is built with CMake option -DMAYO_BUILD_TYPE=neon. AES acceleration is used by default, if available. We report results on an Apple M3 processor.

Scheme	KeyGen	ExpandSK + Sign	ExpandPK + Verify
`MAYO_one`	123,271	381,390	213,224
`MAYO_two`	112,322	214,151	128,003
`MAYO_three`	334,458	892,572	512,092
`MAYO_five`	795,090	1,789,597	1,033,879

The library was compiled with the Apple clang toolchain (clang-1700.4.4.1). Results are the average of 1000 benchmark runs.