# Optimization of the McEliece crypto system

In the normal McEliece proposal, the public key G' = SGP is used, with S beeing non-singular, G Generator Matrix and P permutation Matrix

In the White Paper on McEliece with Binary Goppa Codes by Michiel Marcus and the lecture of Tanja Lange it says that you do not need P because you can just permute the support L and remember the sorting - that's fine, I understand that BUT

they also say that the matrix S is not needed by bringing the Generator Matrix in systematic form because gaussian elimination is the same as multiplying by a non-singular matrix

My question is how can I decode a message mG' + e if I have given g,L

• the decoding algorithm by Patterson assumes the form mG + e and returns e

## so I have two problems:

1. how can I use g,L to decode a Codeword m = mSG + e generated by SG instead of G to get e - do I interpret mS as a new message m' and the decoding works just fine and returns mS?

2.after getting m' = mS how can I calculate m because S is unknown

Is my assumption wrong, that S is not available,because if I store the transformation of G to systematic form encoded in a Matrix S then I can calculate m BUT in the whitepaper they do not store the matrix S

for reference: In the whitepaper it says

The Paterson decoding algorithm will work for cipher texts $$\mathbf c=\mathbf m G'+\mathbf e$$, because Paterson only needs you to know the correspondence between field elements and columns. This allows you to recover $$\mathbf e$$. Once you have recovered $$\mathbf e$$ you know $$\mathbf mG'=\mathbf c-\mathbf e$$. $$G'$$ is in systematic form, so just look at the first $$k$$ entries of $$mG'$$ you recover $$m$$.
• @fepaul With Niederreiter, we typically work with the parity check matrix of the code and if we use systematic forms (which correspond to the same $S$) for both the generator and parity check matrices, then they are equivalent up to glueing of an identity matrix. This the same trick applies Commented Sep 12, 2023 at 16:24