Performances

The MQOM scheme has two variants, the sigma variant (-3r suffix) and the 5-round variant (-5r suffix), and it has two trade-offs, the trade-off for short signatures and the trade-off for fast timings. The proposed instances target 3 security levels defined by NIST: L1 (security of AES-128), L3 (security of AES-192), L5 (security of AES-256). For each variant, each trade-off, and each security level, three instances are proposed: an instance with base field GF(2), an instance with base field GF(16), and an instance with base field GF(256). The following benchmark has been performed on a modern laptop supporting AVX2, AES-NI and GFNI (Intel Core Ultra 7 265U). See the specifications for more details and additional benchmarks.

Security Level L1

Instance Public Key (bytes) Secret Key (bytes) Signature (bytes) Key Generation (cycles) Sign (cycles) Verify (cycles)
MQOM2-L1-gf2-short-3r 52 72 2868 0.96M 6.24M 6.02M
MQOM2-L1-gf2-short-5r 52 72 2820 0.94M 6.32M 6.01M
MQOM2-L1-gf16-short-3r 60 88 3060 0.25M 5.29M 5.04M
MQOM2-L1-gf16-short-5r 60 88 2916 0.25M 4.98M 4.77M
MQOM2-L1-gf256-short-3r 80 128 3540 0.21M 5.91M 5.74M
MQOM2-L1-gf256-short-5r 80 128 3156 0.21M 5.29M 5.14M
MQOM2-L1-gf2-fast-3r 52 72 3212 0.99M 3.44M 3.14M
MQOM2-L1-gf2-fast-5r 52 72 3144 0.98M 3.55M 3.04M
MQOM2-L1-gf16-fast-3r 60 88 3484 0.24M 1.95M 1.56M
MQOM2-L1-gf16-fast-5r 60 88 3280 0.24M 1.91M 1.54M
MQOM2-L1-gf256-fast-3r 80 128 4164 0.21M 2.29M 1.91M
MQOM2-L1-gf256-fast-5r 80 128 3620 0.22M 2.27M 1.81M

Security Level L3

Instance Public Key (bytes) Secret Key (bytes) Signature (bytes) Key Generation (cycles) Sign (cycles) Verify (cycles)
MQOM2-L3-gf2-short-3r 78 108 6388 4.83M 34.07M 30.36M
MQOM2-L3-gf2-short-5r 78 108 6280 4.77M 33.60M 30.01M
MQOM2-L3-gf16-short-3r 90 132 6820 1.03M 29.39M 26.20M
MQOM2-L3-gf16-short-5r 90 132 6496 1.01M 27.13M 23.58M
MQOM2-L3-gf256-short-3r 120 192 7900 0.99M 34.60M 31.41M
MQOM2-L3-gf256-short-5r 120 192 7036 0.99M 29.32M 26.32M
MQOM2-L3-gf2-fast-3r 78 108 7576 4.25M 14.51M 13.59M
MQOM2-L3-gf2-fast-5r 78 108 7414 4.33M 15.21M 13.50M
MQOM2-L3-gf16-fast-3r 90 132 8224 0.95M 7.69M 7.31M
MQOM2-L3-gf16-fast-5r 90 132 7738 0.91M 7.29M 6.78M
MQOM2-L3-gf256-fast-3r 120 192 9844 0.96M 9.86M 9.52M
MQOM2-L3-gf256-fast-5r 120 192 8548 0.96M 8.41M 8.35M

Security Level L5

Instance Public Key (bytes) Secret Key (bytes) Signature (bytes) Key Generation (cycles) Sign (cycles) Verify (cycles)
MQOM2-L5-gf2-short-3r 104 144 11764 7.39M 50.33M 48.78M
MQOM2-L5-gf2-short-5r 104 144 11564 7.49M 50.93M 48.23M
MQOM2-L5-gf16-short-3r 122 180 12664 1.88M 37.79M 36.85M
MQOM2-L5-gf16-short-5r 122 180 12014 1.89M 34.86M 33.89M
MQOM2-L5-gf256-short-3r 160 256 14564 1.57M 42.36M 42.27M
MQOM2-L5-gf256-short-5r 160 256 12964 1.56M 36.27M 36.28M
MQOM2-L5-gf2-fast-3r 104 144 13412 6.88M 27.92M 28.92M
MQOM2-L5-gf2-fast-5r 104 144 13124 6.77M 26.95M 26.03M
MQOM2-L5-gf16-fast-3r 122 180 14708 1.66M 13.18M 12.52M
MQOM2-L5-gf16-fast-5r 122 180 13772 1.66M 12.60M 12.21M
MQOM2-L5-gf256-fast-3r 160 256 17444 1.57M 16.11M 15.60M
MQOM2-L5-gf256-fast-5r 160 256 15140 1.57M 15.14M 14.48M

Main features

Conservative security

MQOM relies on fully random unstructured instances of the MQ problem which is believed to be a conservative hardness assumption.

Adaptive and tunable parameters

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.

Small communication

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.8 KB to 4.1 KB.

Small key sizes

Both the secret key and public key sizes are small. The public key, which is often transported with the signature, is between 52-160 bytes across all security levels.

Embedded friendly

MQOM is an embedded friendly scheme: some variants can fit in less than 10 KB of SRAM internal usage for the signature and verification, with decent performance. In addition, many trade-offs are possible to balance SRAM usage and performance in terms of cycles.