This page is dedicated to the Syndrome Decoding problem for random binary linear codes.

**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.5 \), that is \(n = 2k\). We will choose a weight
\(w\) slightly higher than the Gilbert-Varshamov bound: \(w
= \lceil 1.05 \, d_{\rm GV}\rceil\). The matrix \( {\rm \bf H} \) and
the syndrome \( {\rm \bf s} \) are picked uniformly at
random. In this context, with very high
probability there exists a vector \( {\rm \bf e} \) of
weight \(\leq w \) such that \( {\rm \bf He^{\top}} = {\rm \bf
s^{\top}} \).

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.
The Low-weight Codeword challenge
proposes another approach: instances of fixed cryptographic
size but where the goal is to make \(w\) as small as possible.

**Instance generation.** The instances are generated using a
Python script. This
script takes as input the length of the code and a seed.

**How to participate?**

- Choose the value of \(n\) for which you want to solve the problem and download the corresponding instance (on the right). You can also use the generator to generate an instance with another random seed.
- Parse the instance to get the values of \(w, \rm \bf H\) and \(\rm \bf s\). Find a vector \(\rm \bf e\) of weight \(\leq w\) such that \( {\rm \bf He^{\top}} = {\rm \bf s^{\top}} \).
- Submit your solution using the submission form. If your solution is correct and you solved a new challenge, your name will appear in the hall of fame.

Length | Weight | Authors | Details |
---|---|---|---|

570 | 70 | Shintaro Narisada, Kazuhide Fukushima, and Shinsaku Kiyomoto | See details |

550 | 67 | Shintaro Narisada, Kazuhide Fukushima, and Shinsaku Kiyomoto | See details |

540 | 66 | Shintaro Narisada, Kazuhide Fukushima, and Shinsaku Kiyomoto | See details |

530 | 65 | Shintaro Narisada, Kazuhide Fukushima, and Shinsaku Kiyomoto | See details |

510 | 61 | Shintaro Narisada, Kazuhide Fukushima, and Shinsaku Kiyomoto | See details |

Submit your solution

Hall of fame

##### Download instances

Instance generator

Hall of fame

- lines 1, 3, 5, 7 are comments

- line 2 is the length \( n \)

- line 4 is the seed

- line 6 is the target weight \( w \)

- lines 8 to 7 + \( n/2 \) form a binary square
matrix \( {\rm \bf M} \), such that
\( {\rm \bf H} = [ {\rm \bf I}_{n/2} | {\rm \bf M}^\top ] \)
is the parity-check matrix of the challenge

- line 8 + \( n/2 \) is a comment

- line 9 + \( n/2 \) is the target syndrome

Details here.

**A list of instances** with seed 0 (indexed by length)

Tooltips give an indication of complexity.