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 paritycheck matrix \({\rm \bf H} \in \mathbb{F}_2^{(nk) \times n}\) and a vector \({\rm \bf s} \in \mathbb{F}_2^{nk}\) (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 chose a weight \(w\) slightly higher than the GilbertVarshamov 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 Lowweight 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 inpyt the length of the code and a seed.
How to participate?
Length  Weight  Authors  Details 

450  54  Valentin Vasseur  See details 
430  51  Valentin Vasseur  See details 
420  52  Valentin Vasseur  See details 
410  51  Valentin Vasseur  See details 
400  50  Shintaro Narisada, Hiroki Okada, Kazuhide Fukushima, Yuto Nakano, and Shinsaku Kiyomoto  See details 
 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 paritycheck 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)