2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ any comments on my answer? $\endgroup$
    – kodlu
    Oct 30 '20 at 11:27
1
$\begingroup$

Forgive me if I missed something.

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.

In particular sums of elements of the translated code are codewords in the original code (characteristic two means sum is the same as difference).

$\endgroup$
1
  • 1
    $\begingroup$ In the meantime I think I found the answer. I tried to understand Stern's paper. And it appears the algorithm doesn't really cares about what matrix you throw at it, it doesn't even need to be the check matrix for a linear code. Which explains why the algorithm works. You know that the length of the word you look for and an algorithm fiddles with the indexes until it finds it (or not). $\endgroup$
    – Calmarius
    Oct 30 '20 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.