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!


2 Answers 2

  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).


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

  • $\begingroup$ McEliece systems have $n$ columns where $n$ is typically in the thousands. There are $n!$ possible choices of $P$ which is not small. $\endgroup$
    – Daniel S
    Commented Sep 9, 2023 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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