Code-based cryptography relies crucially on the hardness of decoding generic linear codes which can be expressed as follows in the binary case
[decoding a linear code]

Let \( be a binary linear code over \) F2\( of dimension \) k\( and length \) n\(, {\em i.e. }a subspace of \) F2n\( of dimension \) k\(.We are given \) yF2n\(, an integer \) t\( and want to find a codeword \) c and an error vector \({\mathbf {e}}\in \mathbb {F}_2^n\)  of Hamming weight \(|{\mathbf {e}}|=t\)  for which \({\mathbf {y}}= {\mathbf {c}}+{\mathbf {e}}\) .

This terminology stems from information theory, \({\mathbf {y}}\)  is a noisy version of a codeword \({\mathbf {c}}\) : \({\mathbf {y}}={\mathbf {c}}+{\mathbf {e}}\)  where \({\mathbf {e}}\)  is a vector of weight \(t\)  and we want to recover the original codeword \({\mathbf {c}}\) . It can also be viewed as solving an underdetermined linear system with a weight constraint. Indeed, we can associate to a subspace \( of dimension \) k\( of \) F2n\( a binary \) (n-k)n\( matrix \) H\((also called a {\em parity-check} matrix of the code) whose kernel defines\) , namely \( \lbrace {\mathbf {x}}\in \mathbb {F}_2^n: {\mathbf {H}}{\mathbf {x}}^\intercal =\mathbf {0}\rbrace \) . The decoding problem is equivalent to find an \({\mathbf {e}}\)  of Hamming weight \(t\)  such that
\({\mathbf {H}}{\mathbf {e}}^\intercal  = {\mathbf {s}}^\intercal \)  where \({\mathbf {s}}\)  is the syndrome of \({\mathbf {y}}\)  with respect to \({\mathbf {H}}\) , i.e. \({\mathbf {s}}^\intercal  = {\mathbf {H}}{\mathbf {y}}^\intercal \) .
This can be verified by observing that if there exists \({\mathbf {c}}\in  and \) e\( such that \) y=c+e\( then \) Hy = H(c+e) =
Hc+He= He\(.\) The decoding problem has been studied for a long time and despite many efforts on this issue [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}
the best algorithms [8]}, [9]}, [12]} are exponential in the number of errors that have to be corrected:
correcting \(t\)  errors in a binary linear code of length \(n\)  with the aforementioned algorithms has a cost of \(2^{\alpha n(1+ o(1)) }\)  where \(\alpha =\alpha (R,\tau )\)  is a constant depending of the code rate \(R \mathop {=}\limits ^{\triangle }\frac{k}{n}\) , the error rate
\(\tau \mathop {=}\limits ^{\triangle }\frac{t}{n}\)  and the algorithm which is used.
All the efforts that have been spent on this problem have only managed to decrease slightly this exponent \(\alpha \) .
Let us emphasize that this exponent is the key for estimating the security level of any code-based cryptosystem.
We expect that this problem is the hardest at the Gilbert-Varshamov relative distance \(\tau =\delta _{\mathrm {GV}}\)  where \(\delta _{\mathrm {GV}}\mathop {=}\limits ^{\triangle }h^{-1}(1-R)\) , with \(h\)  being the binary entropy function \(h(x) \mathop {=}\limits ^{\triangle }- x \log _2 x -(1-x)\log _2(1-x)\)  and \(h^{-1}(x)\)  its inverse ranging over \([0,\frac{1}{2}]\)  (see an illustration of this behavior in Figure REF ). This corresponds in the case of random linear codes to the largest relative weight below which there is typically just one solution of the decoding problem assuming that there is one. Above this bound, the number of solutions becomes exponential (at least as long as \(\tau < 1 - \delta _{\mathrm {GV}}\) ) and this helps to devise more efficient decoders. Furthermore, all the aforementioned algorithms become polynomial in the regime
\(\frac{1-R}{2} \le \tau \le \frac{1+R}{2}\) .
<FIGURE>