This page is dedicated to the syndrome decoding problem for random quasi-cyclic binary linear codes, in the range of parameters similar to the BIKE cryptosystem.

**Quasi-cyclic Syndrome Decoding problem.** Given integers \(n, k,
w\) such that \(k \leq n\) and \( w \leq n\), an instance
of the problem \(\mathrm{QCSD}(n,k,w)\) consists of a
quasi-cyclic 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 \). First, an
even weight \( w \) is set. Then, the length \( n =
w^2 + 2 \) and the dimension \( k = n/2 \) are
derived, so that \( w \simeq \sqrt{n} \). Notice that
the block length \( k \) is an odd integer, preventing
the following attack.
With these choices of parameters, we expect the problem to be as
close as possible to the problem (2,1)-QCSD on which rely the BIKE, HQC and LEDAcrypt cryptosystems 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 among all quasi-cyclic matrices 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?**

- Choose a provider for the challenge you want to solve. This indicates who generated the instance. Because the instances are generated using a trapdoor, please pick an institution which is independent from yours to ensure the fairness of the competition.
- Choose the value of \(w\) for which you want to solve the problem and download the corresponding instance (on the right).
- Parse the instance to get the values of \(n, w, \rm \bf h\) and \(\rm \bf s\). Generate \(\rm \bf H\) the quasi-cyclic matrix whose first line is equal to \(h\). 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 |
---|---|---|---|

1766 | 42 | Valentin Vasseur | See details |

1602 | 40 | Valentin Vasseur | See details |

1446 | 38 | Valentin Vasseur | See details |

1298 | 36 | Valentin Vasseur | See details |

1158 | 34 | Valentin Vasseur | 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 have been
replaced by freshly generated ones, using urandom as source of randomness.

Submit your solution

Hall of fame

##### Download instances

Hall of fame

A list of instances (indexed by error weight \(w\)) generated by:

- lines 1, 3, 5, 7 are comments

- line 2 is the length \( n \)

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

- lines 6 is a vector \( {\rm \bf h} \) whose cyclic shifts form a square matrix \( {\rm \bf M} \), such that \( {\rm \bf H} = [ {\rm \bf I}_{0.5 n} | {\rm \bf M}^\top ] \) is the parity-check matrix of the challenge

- line 9 is the target syndrome

Details here.