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!
2
-
$\begingroup$ did you consider the noise removal by $D$? $\endgroup$– kelalakaFeb 8, 2019 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$– mipFeb 8, 2019 at 11:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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$ It is always guaranteed that the matrix H' doesn't has an inverse? $\endgroup$– mipFeb 10, 2019 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$– kodluFeb 10, 2019 at 20:46
-
-