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!
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this communityI 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!
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.