Conservative security
Our signature scheme is based on the presumably hardest problem in code-based cryptography: the Syndrome Decoding (SD) problem for random linear codes.
The SDitH scheme has two variants: the hypercube variant (-hyp suffix) and the threshold variant (-thr 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(256) and an instance with base field GF(251).
Instance | Public Key (bytes) | Secret Key (bytes) | Signature (bytes) | Key Generation (cycles) | Sign (cycles) | Verify (cycles) |
---|---|---|---|---|---|---|
SDitH-gf256-L1-hyp | 132 | 432 | 8496 | 14.2M | 10.8M | 9.7M |
SDitH-gf251-L1-hyp | 132 | 432 | 8496 | 7.9M | 21.2M | 20.3M |
SDitH-gf256-L1-thr | 132 | 432 | 10684 | 4.3M | 6.4M | 2.2M |
SDitH-gf251-L1-thr | 132 | 432 | 10684 | 1.6M | 4.6M | 0.6M |
Instance | Public Key (bytes) | Secret Key (bytes) | Signature (bytes) | Key Generation (cycles) | Sign (cycles) | Verify (cycles) |
---|---|---|---|---|---|---|
SDitH-gf256-L3-hyp | 180 | 628 | 19544 | 16.6M | 26.2M | 22.9M |
SDitH-gf251-L3-hyp | 180 | 628 | 19544 | 9.5M | 46.6M | 44.3M |
SDitH-gf256-L3-thr | 180 | 628 | 25964 | 5.2M | 16.2M | 5.7M |
SDitH-gf251-L3-thr | 180 | 628 | 25964 | 2.0M | 11.1M | 1.5M |
Instance | Public Key (bytes) | Secret Key (bytes) | Signature (bytes) | Key Generation (cycles) | Sign (cycles) | Verify (cycles) |
---|---|---|---|---|---|---|
SDitH-gf256-L5-hyp | 244 | 838 | 33924 | 28.7M | 49.9M | 44.0M |
SDitH-gf251-L5-hyp | 244 | 838 | 33924 | 16.5M | 84.8M | 81.0M |
SDitH-gf256-L5-thr | 244 | 838 | 45676 | 9.0M | 32.7M | 11.6M |
SDitH-gf251-L5-thr | 244 | 838 | 45676 | 3.6M | 22.7M | 3.2M |
Our signature scheme is based on the presumably hardest problem in code-based cryptography: the Syndrome Decoding (SD) problem for random linear codes.
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.
SD-in-the-Head is particularly performant in terms of the common “signature size + public-key size” metric (one of the best code-based schemes for this metric).
Both the secret key and public key sizes are small. The public key, which is often transported with the signature, is between 132-244 bytes across all security levels.