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.

Key generation

  1. Alice selects a binary -linear Goppa code, G, capable of correcting t errors. This code possesses an efficient decoding algorithm.
  2. Alice generates a × n parity check matrix, H, for the code, G.
  3. Alice selects a random × binary non-singular matrix, S.
  4. Alice selects a random n × n permutation matrix, P.
  5. Alice computes the × n matrix, Hpub = SHP.
  6. Alice's public key is ; her private key is.

Message encryption

Suppose Bob wishes to send a message, m, to Alice whose public key is :
  1. Bob encodes the message, m, as a binary string em' of length n and weight at most t.
  2. Bob computes the ciphertext as c = HpubeT.

Message decryption

Upon receipt of c = HpubmT from Bob, Alice does the following to retrieve the message, m.
  1. Alice computes S−1c = HPmT.
  2. Alice applies a syndrome decoding algorithm for G to recover PmT.
  3. Alice computes the message, m, via mT = P−1PmT.

Signature scheme

Courtois, Finiasz and Sendrier showed how the Niederreiter cryptosystem can be used to derive a signature scheme
  1. Calculate, where is a Hash Function and is the signed document.
  2. Calculate, where denotes concatenation.
  3. Attempt to decrypt until the smallest value of for which is decryptable is found.
  4. Use the trapdoor function to compute such that, where is the public key.
  5. Compute the index of in the space of words of weight 9.
  6. Use as the signature.
The Verification algorithm is much simpler:
  1. Recover from index.
  2. Compute with the public key.
  3. Compute.
  4. Compare and. If they are the same the signature is valid.
The index of can be derived using the formula below, where denote the positions of non-zero bits of.The number of bits necessary to store is not reducible. On average it will be bits long. Combined with the average bits necessary to store, the signaure will on average be bits long.