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?
| Weight | Authors | Algorithm | Details | 204 | Shintaro Narisada, Hiroki Okada, Shusaku Uemura, Yusuke Aikawa, Kazuhide Fukushima, and Shinsaku Kiyomoto | cuBJMM [eprint:2024/393] | See details | 209 | Shintaro Narisada, Hiroki Okada, Shusaku Uemura, Yusuke Aikawa, Kazuhide Fukushima, and Shinsaku Kiyomoto | A GPU implementation of the Becker--Joux--May--Meurer (BJMM) Algorithm [eprint:2024/393] | See details | 210 | Shintaro Narisada, Hiroki Okada, Shusaku Uemura, Yusuke Aikawa, Kazuhide Fukushima, and Shinsaku Kiyomoto | A GPU implementation of the Becker--Joux--May--Meurer (BJMM) Algorithm [eprint:2024/393] | See details | 211 | Leo Ducas, Marc Stevens | Hybrid Wagner-Babai using Code Reduction [eprint:2020/869] | See details | 212 | Vasiliy Usatyuk | Lattice:SBP(BKZ), SVP | See details |
|---|
- 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.