# How can we prove that the scrambled G matrix in McEliece cryptosystem preserves the minimum distance properties of G matrix?

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?

### edit

Encryption

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?

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