The purpose of this webpage is to assess the practical hardness of problems in coding theory.
The following challenges are currently available.
Generic problems. First we consider the two main problems on which Hamming-weight code-based cryptography mainly relies.
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.
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.
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.
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.
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.
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:
This a collaborative project intended to be useful for the code-crypto community. There are several ways you can contribute.