# Decrypting McEliece if security assumptions fail

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?

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).
• McEliece systems have $n$ columns where $n$ is typically in the thousands. There are $n!$ possible choices of $P$ which is not small. Sep 9 at 10:33