Performances

The MQOM scheme has two variants, the sigma variant (-r3 suffix) and the 5-round variant (-r5 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, two instances are proposed: an instance with base field GF(2) and an instance with base field GF(256).

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 — M* — M* — M*
MQOM2-L1-gf2-short-5r 52 72 2820 — M* — M* — M*
MQOM2-L1-gf256-short-3r 80 128 3540 — M* — M* — M*
MQOM2-L1-gf256-short-5r 80 128 3156 — M* — M* — M*
MQOM2-L1-gf2-fast-3r 52 72 3212 — M* — M* — M*
MQOM2-L1-gf2-fast-5r 52 72 3144 — M* — M* — M*
MQOM2-L1-gf256-fast-3r 80 128 4164 — M* — M* — M*
MQOM2-L1-gf256-fast-5r 80 128 3620 — M* — M* — M*

Security Level L3

Instance Public Key (bytes) Secret Key (bytes) Signature (bytes) Key Generation (cycles) Sign (cycles) Verify (cycles)
MQOM2-L3-gf2-short-r3 78 108 6388 — M* — M* — M*
MQOM2-L3-gf2-short-r5 78 108 6280 — M* — M* — M*
MQOM2-L3-gf256-short-r3 120 192 7900 — M* — M* — M*
MQOM2-L3-gf256-short-r5 120 192 7036 — M* — M* — M*
MQOM2-L3-gf2-fast-r3 78 108 7576 — M* — M* — M*
MQOM2-L3-gf2-fast-r5 78 108 7414 — M* — M* — M*
MQOM2-L3-gf256-fast-r3 120 192 9844 — M* — M* — M*
MQOM2-L3-gf256-fast-r5 120 192 8548 — M* — M* — M*

Security Level L5

Instance Public Key (bytes) Secret Key (bytes) Signature (bytes) Key Generation (cycles) Sign (cycles) Verify (cycles)
MQOM2-L5-gf2-short-r3 104 144 11764 — M* — M* — M*
MQOM2-L5-gf2-short-r5 104 144 11564 — M* — M* — M*
MQOM2-L5-gf256-short-r3 160 256 14564 — M* — M* — M*
MQOM2-L5-gf256-short-r5 160 256 12964 — M* — M* — M*
MQOM2-L5-gf2-fast-r3 104 144 13412 — M* — M* — M*
MQOM2-L5-gf2-fast-r5 104 144 13124 — M* — M* — M*
MQOM2-L5-gf256-fast-r3 160 256 17444 — M* — M* — M*
MQOM2-L5-gf256-fast-r5 160 256 15140 — M* — M* — M*

* Currently, the existing implementations of MQOM have not been fully optimized, and their benchmarks do not accurately represent the computational performance of the MQOM signature scheme. We will deliver fully optimized implementations and their benchmarks in the coming months. The second-round specifications include early-stage benchmarks. Stay tuned to the GitHub repository for updates.

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 tailored to different use cases.

Small communication

MPCitH-based signature schemes in the literature have signature sizes ranging on 2.5-10 KB (for 128-bit of security). MQOM is on the lower side of this range, with 2.8-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.