This page is dedicated to the syndrome decoding problem for random binary linear codes, in the range of parameters similar to the Goppa-McEliece cryptosystem.
Syndrome Decoding problem. Given integers \(n, k, w\) such that \(k \leq n\) and \( w \leq n\), an instance of the problem \(\mathrm{SD}(n,k,w)\) consists of a parity-check matrix \({\rm \bf H} \in \mathbb{F}_2^{(n-k) \times n}\) and a vector \({\rm \bf s} \in \mathbb{F}_2^{n-k}\) (called the syndrome). A solution to the problem is a vector \( {\rm \bf e} \in \mathbb{F}_2^n \) of Hamming weight \(\leq w\) such that \( {\rm \bf He^{\top}} = {\rm \bf s^{\top}} \).
The challenge. Here, we focus on instances with code rate \( R = 0.8 \), that is \(k = 0.8\,n\). We will choose a weight \(w = \lceil \frac{n}{5 \lceil \log_2 n \rceil} \rceil \). With these choices of parameters, we intend the problem to be as close as possible to the problem on which relies the Classic McEliece cryptosystem proposed for the NIST standardization process.
Under these conditions, instances with cryptographic size are assumed to be out of reach, so we propose instances with increasing size to see how hard this problem is in practice.
Trapdoor. The matrix \( {\rm \bf H} \) is picked uniformly at random but the syndrome \( {\rm \bf s} \) is generated using a trapdoor, to ensure that there exists a solution of weight \(w\). First a vector \( {\rm \bf e} \in \mathbb{F}_2^n \) is chosen uniformly at random* among all vectors of weight \(w\), then we compute the value of \(\rm \bf s\) such that \( {\rm \bf He^{\top}} = {\rm \bf s^{\top}} \). To ensure that the challenge is fair, we provide different versions of the challenge for each size, generated independently by people in different institutions.
How to participate?
| Length | Weight | Authors | Details |
|---|---|---|---|
| 1409 | 26 | Shintaro Narisada, Hiroki Furue, Yusuke Aikawa, Kazuhide Fukushima, and Shinsaku Kiyomoto | See details |
| 1347 | 25 | Daniel J. Bernstein, Tanja Lange, Christiane Peters | See details |
| 1284 | 24 | Andre Esser, Alex May and Floyd Zweydinger | See details |
| 1223 | 23 | Andre Esser, Alex May and Floyd Zweydinger | See details |
| 1161 | 22 | Shintaro Narisada, Kazuhide Fukushima, and Shinsaku Kiyomoto | See details |
* Note on the source of randomness (6th Sept. 2019). We are grateful to Taylor Campbell for pointing out the weakness induced by using the standard Python PRNG. Challenges of length > 534 (that were not already solved) have been replaced by freshly generated ones, using urandom as source of randomness.
lines 1, 3, 5, 7, 9 are comments
- line 2 is the length \( n \)
- line 4 is the dimension \( k = 0.8 n\)
- line 6 is the target weight \( w \)
- lines 8 to 7 + \( 0.8 n \) form a binary square matrix \( {\rm \bf M} \), such that \( {\rm \bf H} = [ {\rm \bf I}_{0.8 n} | {\rm \bf M}^\top ] \) is the parity-check matrix of the challenge
- line 8 + \( 0.8 n \) is a comment
- line 9 + \( 0.8 n \) is the target syndrome
Details here.
A list of instances (indexed by length) generated by:
Tooltips give an indication of complexity.