my-server
← Wiki

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 (n, k)-linear Goppa code, G, capable of correcting t errors. This code possesses an efficient decoding algorithm.
  2. Alice generates a (n − k) × n parity check matrix, H, for the code, G.
  3. Alice selects a random (n − k) × (n − k) binary non-singular matrix, S.
  4. Alice selects a random n × n permutation matrix, P.
  5. Alice computes the (n − k) × n matrix, H<sup>pub</sup> = SHP.
  6. Alice's public key is (H<sup>pub</sup>, t); her private key is (S, H, P).

Message encryption

Suppose Bob wishes to send a message, m, to Alice whose public key is (H<sup>pub</sup>, t):

  1. Bob encodes the message, m, as a binary string e<sup>m'</sup> of length n and weight at most t.
  2. Bob computes the ciphertext as c = H<sup>pub</sup>e<sup>T</sup>.

Message decryption

Upon receipt of c = H<sup>pub</sup>m<sup>T</sup> from Bob, Alice does the following to retrieve the message, m.

  1. Alice computes S<sup>−1</sup>c = HPm<sup>T</sup>.
  2. Alice applies a syndrome decoding algorithm for G to recover Pm<sup>T</sup>.
  3. Alice computes the message, m, via m<sup>T</sup> = P<sup>−1</sup>Pm<sup>T</sup>.

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 (denoted further as ) 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.

References

  • Henk C. A. van Tilborg. Fundamentals of Cryptology, 11.4.

External links