The MQOM scheme comes in two variants: the correlated-tree variant (-ct suffix) and the one-tree variant (-ot suffix). It also offers three performance trade-offs: one optimized for shorter signatures, one providing a balanced trade-off, and one optimized for fast timings. The proposed instances target the three security levels defined by NIST: L1 (AES-128 security), L3 (AES-192 security), and L5 (AES-256 security). The following benchmarks were obtained on a modern laptop supporting AVX2, VAES, and GFNI (Intel Core Ultra 7 265U). See the specification for further details and additional benchmarks.
| Instance | Public Key (bytes) | Secret Key (bytes) | Signature (bytes) | Key Generation (cycles) | Sign (cycles) | Verify (cycles) |
|---|---|---|---|---|---|---|
| MQOM3-L1-gf2-shorter-ct | 52 | 72 | 2492 | 0.21M | 15.3M | 7.47M |
| MQOM3-L1-gf2-shorter-ot | 52 | 72 | 2492 | 0.21M | 19.1M | 18.6M |
| MQOM3-L1-gf16-short-ct | 64 | 96 | 2932 | 0.07M | 3.76M | 3.70M |
| MQOM3-L1-gf16-short-ot | 64 | 96 | 2932 | 0.07M | 4.79M | 4.85M |
| MQOM3-L1-gf16-fast-ct | 64 | 96 | 3316 | 0.09M | 1.15M | 1.12M |
| MQOM3-L1-gf16-fast-ot | 64 | 96 | 3316 | 0.09M | 1.39M | 1.26M |
| Instance | Public Key (bytes) | Secret Key (bytes) | Signature (bytes) | Key Generation (cycles) | Sign (cycles) | Verify (cycles) |
|---|---|---|---|---|---|---|
| MQOM3-L3-gf2-shorter-ct | 78 | 108 | 5932 | 1.59M | 38.8M | 32.6M |
| MQOM3-L3-gf2-shorter-ot | 78 | 108 | 5890 | 1.59M | 48.6M | 43.9M |
| MQOM3-L3-gf16-short-ct | 96 | 144 | 6556 | 0.43M | 19.0M | 18.2M |
| MQOM3-L3-gf16-short-ot | 96 | 144 | 6556 | 0.44M | 25.3M | 24.7M |
| MQOM3-L3-gf16-fast-ct | 96 | 144 | 7564 | 0.48M | 5.07M | 4.88M |
| MQOM3-L3-gf16-fast-ot | 96 | 144 | 7660 | 0.47M | 5.79M | 5.53M |
| Instance | Public Key (bytes) | Secret Key (bytes) | Signature (bytes) | Key Generation (cycles) | Sign (cycles) | Verify (cycles) |
|---|---|---|---|---|---|---|
| MQOM3-L5-gf2-shorter-ct | 104 | 144 | 10836 | 2.74M | 57.3M | 53.1M |
| MQOM3-L5-gf2-shorter-ot | 104 | 144 | 10804 | 2.73M | 70.1M | 65.9M |
| MQOM3-L5-gf16-short-ct | 128 | 192 | 12100 | 0.74M | 26.6M | 25.6M |
| MQOM3-L5-gf16-short-ot | 128 | 192 | 11716 | 0.73M | 33.2M | 32.3M |
| MQOM3-L5-gf16-fast-ct | 128 | 192 | 13540 | 0.78M | 8.75M | 8.32M |
| MQOM3-L5-gf16-fast-ot | 128 | 192 | 13380 | 0.78M | 11.3M | 9.33M |
MQOM relies on fully random unstructured instances of the MQ problem which is believed to be a conservative hardness assumption.
Using MPCitH enables us to tailor parameters, in particular the number of parties, meaning that we can provide a variety of parameter sets suited for different use cases.
MPCitH-based signature schemes in the literature have signature sizes ranging from 2.5 KB to 10 KB (for 128-bit of security). MQOM is on the lower side of this range, with 2.5 KB to 3.3 KB.
Both the secret key and public key sizes are small. The public key, which is often transported with the signature, is between 52-128 bytes across all security levels.
MQOM is an embedded friendly scheme: some variants can fit in less than 14 KB of SRAM internal usage for the signature and verification for all security levels, with decent performance. In addition, many trade-offs are possible to balance SRAM usage and performance in terms of cycles.