In McEliece cryptosystem, G matrix is scrambled using S and P so that scrambled G matrix is G' = SGP. Here G is the generator matrix of a linear code and after scrambling it is converted into another matrix G' of the same size. How can we ensure that G' is another possible G matrix of the code with same distance properties? Is there any proof for that? If G' satisfies all the properties of G, will this hold any linear code other than Goppa code also?



c = mSGP + e

Here mS will give you another k element vector which forms the message for the permuted version of the G matrix, GP. Now my question is whether the permuted G matrix results in another valid G matrix. Are there any properties to be satisfied by P matrix?


1 Answer 1


$P$ is required to be a permutation matrix. Thus, the effect $P$ has on $G$ is simply to reorder its columns. Crucially, this does not change the weight of any of the codewords. Note that this holds irregardless of the code; be it Goppa or something else.

More concretely, suppose $G$ is any $(n,k,d)$ code. This means that $G$ can correct up to $\frac{\lfloor d \rfloor}{2}$ errors. So let $d' \leq \frac{\lfloor d \rfloor}{2} $ be the weight of $e$. Now suppose $$c = mSGP + e.$$ On decrypting $c$ we first apply $P^{-1}$ to $c$ to get $$ c' = cP^{-1} = (mSGP + e)P^{-1} = mSGPP^{-1} + eP^{-1} = mSG + e'. \tag{1}$$ You see that the r.h.v. in (1) is simply a codeword in the code generated by $G$ with an added error of $e'$. But the inverse of a permutation matrix is also a permutation matrix, so the vector $e'$ also has weight $d' \leq \frac{\lfloor d \rfloor}{2} $. Consequently, we can apply the decoding procedure of the code to get rid of $e'$ and obtain $mS$. Since $S$ is invertible, we can obtain $m$ by multiplying with $S^{-1}$ on the right.

  • $\begingroup$ Will any choice of permutation matrix, P reorder the columns of G? Are there any properties to be satisfied by P matrix? $\endgroup$
    – Surya
    Commented Oct 11, 2017 at 6:46
  • $\begingroup$ Because if there is any restriction, it may reduce the offered security. In one paper with n=1024, I saw number of permuation matrix combinations as 1024! $\endgroup$
    – Surya
    Commented Oct 11, 2017 at 6:53
  • $\begingroup$ @Surya Yes, any permutation matrix will reorder the columns of G. There are no other requirements on P other than it being a permutation matrix. $\endgroup$
    – hakoja
    Commented Oct 11, 2017 at 8:21

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.