### Large Weight Syndrome Decoding Problem

This page is dedicated to the Large Weight Ternary Syndrome Decoding problem for random binary linear codes.

Large Weight Ternary Syndrome Decoding problem. Given integers $$n, k, w$$ such that $$k \leq n$$ and $$w \leq n$$, an instance of the problem $$\mathrm{LW3SD}(n,k,w)$$ consists of a parity-check matrix $${\rm \bf H} \in \mathbb{F}_3^{(n-k) \times n}$$ and a vector $${\rm \bf s} \in \mathbb{F}_3^{n-k}$$ (called the syndrome). A solution to the problem is a vector $${\rm \bf e} \in \mathbb{F}_3^n$$ of Hamming weight $$\geq w$$ such that $${\rm \bf He^{\top}} = {\rm \bf s^{\top}}$$.

The challenge. Here, we focus on instances with code rate $$R = \log_3(2) \simeq 0.36907$$, that is $$k = \lfloor R n \rfloor$$. At this rate, the equivalent of the Gilbert-Varshamov bound for heigh weight words is exactly equal to $$n$$. Hence we will take : $$w = \lfloor 0.99 \, d_{\rm GV}^{+}\rfloor = \lfloor 0.99 \, n \rfloor$$. The matrix $${\rm \bf H}$$ and the syndrome $${\rm \bf s}$$ are picked uniformly at random. In this context, with very high probability there exists a vector $${\rm \bf e}$$ of weight $$\geq w$$ such that $${\rm \bf He^{\top}} = {\rm \bf s^{\top}}$$.

Under these conditions, instances with cryptographic size are assumed to be out of reach, so we propose instances with increasing size to see how hard this problem is in practice.

Instance generation. The instances are generated using a Python script. This script takes as input the length of the code and a seed.

How to participate?

1. Choose the value of $$n$$ for which you want to solve the problem and download the corresponding instance (on the right). You can also use the generator to generate an instance with another random seed.
2. Parse the instance to get the values of $$w, \rm \bf H$$ and $$\rm \bf s$$. Find a vector $$\rm \bf e$$ of weight $$\geq w$$ such that $${\rm \bf He^{\top}} = {\rm \bf s^{\top}}$$.
3. Submit your solution using the submission form. If your solution is correct and you solved a new challenge, your name will appear in the hall of fame.

##### Best solutions
Length Weight Authors Details
200198Andre Esser, Alexander May and Floyd Zweydinger
190189Andre Esser, Alexander May and Floyd Zweydinger
180178Andre Esser, Alexander May and Floyd Zweydinger
170168Andre Esser, Alexander May and Floyd Zweydinger
160158Andre Esser, Alexander May and Floyd Zweydinger

- lines 1, 3, 5, 7 are comments
- line 2 is the length $$n$$
- line 4 is the seed
- line 6 is the dimension $$k$$
- line 8 is the target weight $$w$$
- lines 10 to 10 + $$k$$ form a ternary matrix $${\rm \bf M}$$, such that $${\rm \bf H} = [ {\rm \bf I}_{n-k} | {\rm \bf M}^\top ]$$ is the parity-check matrix of the challenge
- the last line is the target syndrome

Details here.

A list of instances with seed 0 (indexed by length)

Tooltips give an indication of complexity.