Welcome to the code-based challenges webpage!

The purpose of this webpage is to assess the practical hardness of problems in coding theory.

The Challenges

The following challenges are currently available.

Generic problems. First we consider the two main problems on which Hamming-weight code-based cryptography mainly relies.

> Challenge: Syndrome Decoding

Given a matrix \({\rm \bf H} \in \mathbb{F}_2^{(n-k) \times n}\), a vector \({\rm \bf s} \in \mathbb{F}_2^{n-k}\) and an integer \(w \leq n\), find a vector \({\rm \bf e} \in \mathbb{F}_2^{n}\) of Hamming weight \(|{\bf e}| \leq w \) such that \( {\rm \bf H e^{\top}} = {\rm \bf s^{\top}} \). Here we will focus especially on the case with rate \(R = 0.5\) and \(w\) close to the Gilbert-Varshamov bound.

> Challenge: Finding Low Weight Codewords

In a random linear code of size \(n = 1280\) and rate \(R = 0.5\), there exists on average a unique codeword of weight 144 (the Gilbert-Varshamov bound) and finding it should requires at least \(2^{128}\) operations with the best known algorithms. Finding words of higher weight is easier. The goal of this challenge is to find codewords with a weight as close as possible to the GV-bound.

NIST-like problems. We propose challenges with the same parameter settings as the main cryptographic schemes proposed for the NIST standardization process for post-quantum cryptography. For now, we propose two such challenges in Hamming metric. In both cases, the goal is to assess the hardness of generic decoding, not to find distinguishers on the codes. Therefore we propose random linear codes with the same rate and error weight as the corresponding NIST candidates.

> Challenge: McEliece-Goppa Syndrome Decoding

The challenge is to solve the Syndrome Decoding problem for a random linear code of rate \(R = 0.8\) and an error-weight \( w = (1 - R) \, n \,/\, \log_{2}(n) \). This corresponds to instances of the SD problem on which the security of the Classic McEliece cryptosystem relies.

> Challenge: QC-MDPC Syndrome Decoding

The challenge is to solve the Syndrome Decoding problem for a random quasi-cyclic linear code of rate \(R = 0.5\) and an error-weight \( w \simeq \sqrt{n} \). This corresponds to instances of the SD problem on which the security of the BIKE, HQC and LEDAcrypt, cryptosystems rely.

Future Challenges

This website is still under construction. In the future, we intend to propose new challenges. Here are some cases that we believe could be interesting:

  • rank-metric Syndrome decoding;
  • \(q\)-ary Syndrome Decoding in Hamming metric;
  • \(q\)-ary Syndrome Decoding in Hamming metric with large weight.

How to contribute?

This a collaborative project intended to be useful for the code-crypto community. There are several ways you can contribute.

Latest news
20-08-2019. Announcement of the challenge at Crypto 2019 conference
12-08-2019. All challenges are now online
21-07-2019. Website is online.
12-07-2019. Contact email is active.