Conservative security
MQOM relies on fully random unstructured instances of the MQ problem which is believed to be a conservative hardness assumption.
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).
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* |
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* |
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.
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 tailored to different use cases.
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.
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.