The MQOM scheme has two variants: the short variant (-short suffix) and the fast variant (-fast suffix). 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 and each security level, two instances are proposed: an instance with base field GF(31) and an instance with base field GF(251).
| Instance | Public Key (bytes) | Secret Key (bytes) | Signature (bytes) | Key Generation (cycles) | Sign (cycles) | Verify (cycles) |
|---|---|---|---|---|---|---|
| MQOM-L1-gf31-short | 47 | 78 | 6348 | 0.67M | 44.36M | 41.72M |
| MQOM-L1-gf251-short | 59 | 102 | 6575 | 0.48M | 28.51M | 27.31M |
| MQOM-L1-gf31-fast | 47 | 78 | 7621 | 0.65M | 17.65M | 15.54M |
| MQOM-L1-gf251-fast | 59 | 102 | 7809 | 0.48M | 11.52M | 10.16M |
| Instance | Public Key (bytes) | Secret Key (bytes) | Signature (bytes) | Key Generation (cycles) | Sign (cycles) | Verify (cycles) |
|---|---|---|---|---|---|---|
| MQOM-L3-gf31-short | 73 | 122 | 13837 | 2.51M | 108.13M | 102.22M |
| MQOM-L3-gf251-short | 92 | 160 | 14257 | 1.98M | 69.51M | 65.56M |
| MQOM-L3-gf31-fast | 73 | 122 | 16590 | 2.46M | 56.29M | 51.25M |
| MQOM-L3-gf251-fast | 92 | 160 | 17161 | 1.96M | 32.85M | 29.58M |
| Instance | Public Key (bytes) | Secret Key (bytes) | Signature (bytes) | Key Generation (cycles) | Sign (cycles) | Verify (cycles) |
|---|---|---|---|---|---|---|
| MQOM-L5-gf31-short | 99 | 166 | 24147 | 6.24M | 224.45M | 213.61M |
| MQOM-L5-gf251-short | 125 | 218 | 24926 | 4.86M | 148.0M | 142.26M |
| MQOM-L5-gf31-fast | 99 | 166 | 28917 | 6.38M | 156.26M | 146.2M |
| MQOM-L5-gf251-fast | 125 | 218 | 29919 | 4.83M | 81.55M | 75.58M |
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 5-10 KB (for 128-bit of security). MQOM is on the lower side of this range, with 6.3-6.6 KB.
Both the secret key and public key sizes are small. The public key, which is often transported with the signature, is between 47-125 bytes across all security levels.