# Niederreiter cryptosystem

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!

• did you consider the noise removal by $D$? Feb 8, 2019 at 11:43
• 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
– mip
Feb 8, 2019 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.

• Is $2t+1$ excessive? Feb 9, 2019 at 15:33
• It is always guaranteed that the matrix H' doesn't has an inverse?
– mip
Feb 10, 2019 at 6:44
• @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. Feb 10, 2019 at 20:46
• $H'$ is rectangular, so has no inverse. Feb 10, 2019 at 20:48
• Can be uniquely and correctly found? Feb 10, 2019 at 20:51

Since the parity check matrix H' is not squared (it has dimensions $$n-k \times n$$), one can not ouput the message $$m$$ from the ciphertext $$c$$.

Nevertheless, there is an attack named Lee-Brickell, which defines the security McEliece, but was later found that can also be adapted to Niederreiter, showcasing the equivalence in security of both cryptosystems. The Lee-Brickell attack is based on extracting a full rank submatrix $$H_{n-k} \in \mathbb{F}_2^{n-k \times n-k}$$ which can be inversed so that the message is find randomly in a much smaller configuration space in $$\mathbb{F}_2^{k}$$.