Hall Of Fame

McEliece Parameters

A McEliece public key is a matrix $\mathsf{pk}\in {\mathbb{F}}_2^{tm\times (n-tm)}$, which is used to define a parity check matrix $\mathbf{H}:=[{\mathbf{I}}_{tm}\mid \mathsf{pk}]\in {\mathbb{F}}_2^{tm\times n}$ of a binary Goppa code $C\subset {\mathbb{F}}_2^n$.
The corresponding secret key consists of a list $L:=({\alpha }_1,\dots ,{\alpha }_n)\in {\mathbb{F}}_{2^m}^n$ and a degree-$t$ polynomial $g(X)\in {\mathbb{F}}_{2^m}[X]$, such that
$$C=\left\{(c_1,\dots ,c_n)\in {\mathbb{F}}_2^n\mid \sum _{i=1}^n\frac{c_i}{X-{\alpha }_i}\equiv 0\mathrm{mod}g(X)\right\}.$$
A McEliece ciphertext is a vector $\mathbf{s}:=\mathbf{He}\in {\mathbb{F}}_2^{tm}$, called the syndrome, where $\mathbf{e}\in {\mathbb{F}}_2^n$ is a secret error vector of Hamming weight $t$.

Format of Instances

Our challenges contain a public key, a syndrome, and the parameters $n$, $m$ and $t$.
Additionally, they contain a vector $\mathbf{f}=(f_m,\dots ,f_1,f_0)\in {\mathbb{F}}_2^{m+1}$, representing a degree-$m$ polynomial $f(Z):={\sum }_{i=0}^m{f}_i{Z}^i\in {\mathbb{F}}_2[Z]$, which defines the field ${\mathbb{F}}_{2^m}={\mathbb{F}}_2[Z]/(f(Z))$.

Using our script, the secret vector $\mathbf{e}$ can be decoded to a human-readable message.

Estimated Bit-Complexity

The bit complexities for recovering the error vector $\mathbf{e}$ were estimated with the Binary Syndrome Decoding Estimator.