0

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

fepaul
  • 35
  • 3

1 Answers1

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

Daniel S
  • 23,716
  • 1
  • 29
  • 67
  • 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

     – fepaul Sep 12 '23 at 15:30
  • 1
    @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 – Daniel S Sep 12 '23 at 16:24
  • Thank you so much for your help! – fepaul Sep 13 '23 at 09:09