About SD-in-the-Head
Syndrome-Decoding-in-the-Head is a digital signature scheme based on the hardness of the syndrome decoding problem for random linear codes on a finite field. It consists in a zero-knowledge proof of knowledge of a low-weight vector x solution of a syndrome decoding instance y = H x, which is made non-interactive using the Fiat-Shamir transform. This zero-knowledge proof relies on the principle of "multiparty computation in the head" (MPCitH) originally introduced in [IKOS07]. The MPCitH framework has recently been improved in a series of works which makes it an effective and versatile tool for the design of post-quantum signature schemes. The SD-in-the-Head protocol was initially proposed in [FJR22] and further improved in subsequent works [AGHHJY23,FR22].
SD-in-the-Head is a candidate in the ongoing post-quantum digital signatures standardization process organized by NIST.
Main features
- 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.
- 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 code-based signatures. The 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).
- 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 120-240 bytes across all security levels.
Parameter sets
| Instance | Security level | Public key | Signature | Keygen | Sign | Verify |
|---|---|---|---|---|---|---|
| SDitH-gf256-L1-hyp | 128 | 120 | 8241 | 3.2M | 13.4M | 12.5M |
| SDitH-gf256-L3-hyp | 192 | 183 | 19161 | 3.9M | 30.5M | 27.7M |
| SDitH-gf256-L5-hyp | 256 | 234 | 33370 | 7.1M | 59.2M | 54.4M |
| SDitH-gf251-L1-hyp | 128 | 120 | 8241 | 1.7M | 22.1M | 21.2M |
| SDitH-gf251-L3-hyp | 192 | 183 | 19161 | 1.9M | 51.1M | 49.0M |
| SDitH-gf251-L5-hyp | 256 | 234 | 33370 | 3.7M | 94.8M | 91.3M |
| SDitH-gf256-L1-thr | 128 | 120 | 10117 | 3.2M | 5.1M | 1.6M |
| SDitH-gf256-L3-thr | 192 | 183 | 24918 | 3.9M | 14.8M | 4.9M |
| SDitH-gf256-L5-thr | 256 | 234 | 43943 | 7.1M | 30.5M | 10.2M |
| SDitH-gf251-L1-thr | 128 | 120 | 10117 | 1.7M | 4.4M | 0.6M |
| SDitH-gf251-L3-thr | 192 | 183 | 24918 | 1.9M | 11.7M | 1.5M |
| SDitH-gf251-L5-thr | 256 | 234 | 43943 | 3.7M | 23.9M | 3.2M |
The table shows sizes in number of bytes and timings in cycles.
Consortium
Syndrome-Decoding-in-the-Head has been designed by
- Carlos Aguilar Melchor, SandboxAQ
- Thibauld Feneuil, CryptoExperts
- Nicolas Gama, SandboxAQ
- Shay Gueron, Meta and University of Haifa
- James Howe, SandboxAQ
- David Joseph, SandboxAQ
- Antoine Joux, CISPA
- Edoardo Persichetti, Florida Atlantic University and Sapienza University
- Tovohery H. Randrianarisoa, Umeå University
- Matthieu Rivain, CryptoExperts
- Dongze Yue, SandboxAQ
Resources
Full design document, including specification, design rationale, and security arguments.
NIST submission packages:
- 2022-06-01: NIST submission package v1
References
- [AGHHJY23] Carlos Aguilar Melchor, Nicolas Gama, James Howe, Andreas Hülsing, David Joseph, and Dongze Yue. The Return of the SDitH. In: EUROCRYPT 2023, Part V. Ed. by Carmit Hazay and Martijn Stam. Vol. 14008. LNCS. Springer, Heidelberg, Apr. 2023, pp. 564-596.
- [FR22] Thibauld Feneuil and Matthieu Rivain. Threshold Linear Secret Sharing to the Rescue of MPC-in-the-Head. Cryptology ePrint Archive, Report 2022/1407. https://eprint.iacr.org/2022/1407.
- [FJR22] Thibauld Feneuil, Antoine Joux, and Matthieu Rivain. Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs. In: CRYPTO 2022, Part II. Ed. by Yevgeniy Dodis and Thomas Shrimpton. Vol. 13508. LNCS. Springer, Heidelberg, Aug. 2022, pp. 541-572.
- [IKOS07] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Zero-knowledge from secure multiparty computation. In D. S. Johnson and U. Feige, editors, 39th ACM STOC, pages 21-30. ACM Press, 2007