I can't understand how Niederreiter cryptosystem works. If $c=mH^{'T}$ than why we cannot compute $m$ directly by multiplying $c$ with the $(H^{'T})^{-1}$? Can you give me an example of a "fast decoding algorithm"?

Thank you!

  • $\begingroup$ did you consider the noise removal by $D$? $\endgroup$ – kelalaka Feb 8 at 11:43
  • $\begingroup$ What noise? That's confuses me. In the McEliece cryptosystem we add some error $e$ but in all Niederreiter documentations I didn't see any error adding to the plaintext message $\endgroup$ – mip Feb 8 at 11:46

In the Niederreiter system, the plaintext is mapped to some error vector of weight $t$, where the code correction capability is $d=2t+1.$

With the trapdoor information (permutation) this can be decoded by the legitimate receiver by syndrome decoding.

Without the trapdoor information, this is equivalent to decoding a random vector, which is hard, as in the McEliece cryptosystem.

  • $\begingroup$ Is $2t+1$ excessive? $\endgroup$ – kelalaka Feb 9 at 15:33
  • $\begingroup$ It is always guaranteed that the matrix H' doesn't has an inverse? $\endgroup$ – mip Feb 10 at 6:44
  • 1
    $\begingroup$ @kelalaka If you took $d=t+k+1$ you might be unlucky and the actual codeword might only be Hamming distance $k+1$ away which can be found with $O(2^{k+1})$ effort. $\endgroup$ – kodlu Feb 10 at 20:46
  • $\begingroup$ $H'$ is rectangular, so has no inverse. $\endgroup$ – kodlu Feb 10 at 20:48
  • $\begingroup$ Can be uniquely and correctly found? $\endgroup$ – kelalaka Feb 10 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.