Niederreiter cryptosystem

In cryptography, the Niederreiter cryptosystem is a variation of the McEliece cryptosystem developed in 1986 by Harald Niederreiter. It applies the same idea to the parity check matrix, H, of a linear code. Niederreiter is equivalent to McEliece from a security point of view. It uses a syndrome as ciphertext and the message is an error pattern. The encryption of Niederreiter is about ten times faster than the encryption of McEliece. Niederreiter can be used to construct a digital signature scheme.
Scheme definition.
A special case of Niederreiter's original proposal was broken but the system is secure when used with a Binary Goppa code.
Message encryption.
Suppose Bob wishes to send a message, "m", to Alice whose public key is ("H"pub, "t"):
Message decryption.
Upon receipt of "c" = "H"pub"m"T from Bob, Alice does the following to retrieve the message, "m".
Signature scheme.
Courtois, Finiasz and Sendrier showed how the Niederreiter cryptosystem can be used to derive a signature scheme
Verification then applies the public encryption function to the signature and checks whether or not this equals the hash value of the document. When using Niederreiter, or in fact any cryptosystem based on error correcting codes, the second step in the signature scheme almost always fails. This is because a random syndrome usually corresponds to an error pattern of weight greater than "t". The system then specifies a deterministic way of tweaking d until one is found which can be decrypted.
The choice of the code parameters is related to the probability that a random syndrome is decodable. Courtois, Finiaz, and Sendrier suggest the parameter values "n" = 216 and "t" = 9. Then the probability to decode a random syndrome is formula_1. Therefore, a decodable syndrome is found after an expected number of 9! attempts. Add a counter, "i", to the original document d, to produce a slightly altered document, d"i". Hashing d"i" gives a syndrome that depends on "i". Let "i" run from 0 to "i"0, with "i"0 the first value of "i" for which d"i" is decodable. In this case the decrypted message is a word, "z", of length "n" and weight 9, such that "Hz"T equals the hash value of d"i"0. The signature will be "z" combined with the value "i"0 for verification. This signature is attached to the original document, d.