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 private and public keys in mceliece


1 Answer 1


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

  • $\begingroup$ Oh yeah you are right - but how is it in the niederreiter version - there I have given H' = SHP and it is send c= SHm, with wt(m) <= t so I can decode correctly But to decode I have to calculate first S^(-1) c = Hm and then I can decode to m given the support but do I have to store S as a private key here or can I apply an analog trick like for the McEliece system $\endgroup$
    – fepaul
    Sep 12, 2023 at 15:30
  • 1
    $\begingroup$ @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 $\endgroup$
    – Daniel S
    Sep 12, 2023 at 16:24
  • $\begingroup$ Thank you so much for your help! $\endgroup$
    – fepaul
    Sep 13, 2023 at 9:09

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.