Decrypting McEliece if security assumptions fail

Question

1. G known - how to decrypt Referring to this question: Basic attacks on McEliece; finding S and P (nobody answered)

Take a McEliece cryptosystem with public generator matrix $G′=SGP$ where $G$ is a generator matrix of a secret code with known fast decoding (not necessarily a Goppa code over $\mathbb F_2$), $S$ is random & non-singular and $P$ is a permutation.

Let's say an attacker Eve has a way to find $G$ from $G′$ but not $S$ or $P$.

How would Eve now continue the attack on a encrypted codeword $c=mSGP+e$?

2. How can an attacker get $m$ if an oracle tells him the error $e$?

So the attacker has the received garbled codeword $c = mG' + e = mSGP + e$ and knows $e$. how can he calculate $m$

a) for one special garbled codeword $c$?

b) for every new garbled codeword $c$ without solving a system of equations every time?

Thanks for your help!

Answer 1

1. If you know $G$ and $G'$ you can recover typically recover $P$ from the support splitting algorithm. Note that the support-splitting algorithm is independent of the bases used to represent the two equivalent codes. Once you have $P$ one can compute $G''=GP$ and we can recover $S$ is we can solve $G'=SG''$. To do this we just find a subset of $\mathrm{rank}(G)$ columns of $G''$ of full rank so that if we write $C$ and $C''$ for the submatrices of $G$ and $G''$ formed by the corresponding columns then $C=SC''$ and $S=CC''^{-1}$.

2. a) Again, find a full rank subset of $\mathrm{rank}(G')$ columns, write $C'$ for the corresponding submatrix of $G'$ and $\mathbf x$ for the corresponding entries of $c-e$ and compute $C'^{-1}$. We then have $\mathbf x=mC'$ and so $m=\mathbf xC'^{-1}$. b) Note that the calculation of $C'^{-1}$ is one-time work, so for multiple messages our work is just the evaluation of a set of linear equations rather than their solution and in fact cheaper than the encryption process).

Answer 2

2.a) there you can just solve the systems of equations 2.b) I think thats not possible

1 you could simply try out all possibilities for P - there are not so many ones, then calculate the corresponding S and voila