# How can the Stern's algorithm be used to attack McEliece?

I'm reading about the attacks of the McEliece cryptosystem. I needed to work out a lot of things because most descriptions I have found so far on the internet seems to be quite hand-wavy about the details. So I wrote down what I understand or I think I understand then I have some questions at the end.

In a McEliece cryptosystem the public key consists of a $$k×n$$ key matrix $$K$$ and and the number of errors $$t$$ to introduce into the ciphertext. To encrypt we take a $$k$$ element long message $$\mathbf{m}$$, an $$n$$ element long error vector $$\mathbf{z}$$ with $$t$$ non-zero elements, and finally we get the ciphertext $$\mathbf{y} = \mathbf{m}K + \mathbf{z}$$.

The attacker can decode the plaintext using information set decoding (ISD). In which we choose $$k$$ random linearly independent columns from $$K$$ to form an invertible $$k×k$$ square matrix $$A$$, also we choose $$k$$ elements from the same positions as the columns to form the vector $$\mathbf{a}$$. In an attempt to get the plain text we compute $$\mathbf{q} = \mathbf{a}A^{-1}$$, if all elements in a are error free this should give us the plain text. Verify the result by computing $$\mathbf{y} - \mathbf{q}K = \mathbf{m}K + \mathbf{z} - \mathbf{q}K = (\mathbf{m}-\mathbf{q})K + \mathbf{z}$$. If $$\mathbf{m} = \mathbf{q}$$, then the result is $$\mathbf{z}$$ which has $$t$$ non-zero elements and we are done. If $$\mathbf{m} \neq \mathbf{q}$$, then our guess was wrong. The Hamming distance between two codewords is it least $$2t+1$$, so $$(\mathbf{m}-\mathbf{q})K$$ is a vector that has at least $$2t+1$$ non-zero elements. $$\mathbf{z}$$ has $$t$$ non-zero elements so even if $$\mathbf{z}$$ happens to cancel exactly $$t$$ elements from $$(\mathbf{m}-\mathbf{q})K$$, then the result still has $$t+1$$ non-zero elements. So having more than $$t$$ non-zero elements in the result means failure.

The McEliece cryptosystem chooses the parameters such that finding error free sub sequences is unlikely.

Then I read that there are other attacks. One that turns the problem into a shortest codeword finding problem. And does so by changing the linear code to such that message is mapped like this: $$\mathbf{x} \mapsto \mathbf{x}K - \mathbf{y}$$. So this translates the codewords in the code defined by $$K$$ and this preserves the minimum Hamming-distance requirements so it's still an error correcting code. In this code there is no zero element and the shortest codeword is $$-\mathbf{z}$$ with $$t$$ non-zero elements (when $$\mathbf{x} = \mathbf{m}$$). Since the minimum distance is still $$2t+1$$ all other codewords have at least $$t+1$$ non-zero elements. So if we can find this shortest codeword, then we can remove errors from the ciphertext making the ISD succeed on first try.

Now here is one thing I got stuck at: the code obtained by translation isn't a linear code because translation isn't linear transformation. The linear combination of codewords in it isn't necessarily another codeword, and doesn't contain an all-zero codeword. Right?

But still most descriptions I saw proceed by adding $$\mathbf{y}$$ as a new row into $$K$$, then compute the parity check matrix of this modified code and feed it into a minimum-length codeword searching algorithm such as Stern's algorithm. How and why does this work when the code isn't linear?

• any comments on my answer? – kodlu Oct 30 '20 at 11:27

Is $$K$$ a generator matrix? I believe yes, which means the original code is linear.
The translate of the original code by subtracting $$y$$ is a coset, sometimes called affine subspace. It has almost all the nice properties of a subspace.