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.

> Challenge: Large Weight Ternary Syndrome Decoding

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

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
18-03-2020. New challenge: large weight ternary syndrome decoding.
28-01-2020. It is now possible to submit a solution to a challenge that was already solved! The ten first persons to solve a challenge will appear in the hall of fame.
20-01-2020. New feature: tooltips give an indication of complexity of the challenges.
06-09-2019. New challenges for the Goppa-McEliece and the Quasi-Cyclic challenges.
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.