Low-weight Codeword Problem

This page is dedicated to the problem of finding low-weight codewords for random binary linear codes.

Low Weight Codeword problem. Given integers \(n, k, w\) such that \(k \leq n\) and \(w \leq n\), an instance of the problem \(\mathrm{LWC}(n,k)\) consists of a full rank parity-check matrix \({\rm \bf H} \in \mathbb{F}_2^{(n-k) \times n}\). A solution to the problem is a non-zero vector \( {\rm \bf c} \) with Hamming weight \( \leq w \) such that \( {\rm \bf Hc^{\top}} = {\rm \bf 0 } \).

The challenge. Here, we focus on instances with code rate \(R = 0.5\), that is \( n = 2k \). We fix \(n = 1280\) (see below). At this length, there exists on average a unique codeword of weight 144 (the Gilbert-Varshamov bound) and finding it should requires at least \(2^{128}\) operations (see below). Finding words of higher weight is easier. The goal is to find codewords with a weight as low as possible. The current record is Array.

Choice of \(n\). The complexity of finding a codeword of weight equal to the Gilbert-Varshamov bound in a code of rate \(R = 0.5\) using the BJMM algorithm asymptotically requires \( 2^{0.0999852\, n}\) operations, therefore with \(n = 1280\), finding the smallest codeword should require at least \(2^{128}\) operations.

Compared to the Syndrome Decoding challenge, here the size of the instance is cryptographically large. The goal is to assess that finding codewords close to the GV-bound is hard. This problem is close to the Shortest Vector Problem for lattices.

Instance generation. The instances are generated using a Python script. This script takes as input the length of the code and a seed (but for this challenge we only use the length \(n = 1280\)).

How to participate?

  1. Choose an instance on the right. All instances have the same size, the only difference is the value of the random seed used to generate them. You can also use the generator to generate an instance with another random seed.
  2. Parse the instance to get the values of \(\rm \bf H\). Find a non-zero codeword \(\rm \bf c\) of weight < Array such that \( {\rm \bf Hc^{\top}} = {\rm \bf 0} \).
  3. Submit your solution using the submission form. If your solution is correct, your name will appear in the hall of fame.

Best solutions
Weight Authors Algorithm Details
211Leo Ducas, Marc StevensHybrid Wagner-Babai using Code Reduction [eprint:2020/869]See details
212Vasiliy UsatyukLattice:SBP(BKZ), SVPSee details
214Vasiliy UsatyukLattice: Kannan emb, SBP (SBP), SVPSee details
215Samuel Neves-See details
220Valentin VasseurDumerSee details
Submit your solution
Hall of fame
Download instances
Instance generator

- lines 1, 3, 5 are comments
- line 2 is the length \( n \)
- line 4 is the seed
- lines 6 to 5 + \( 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 parity-check matrix of the challenge

Details here.

Download instances
All instances have the same size. They are indexed by seed.