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, Hpub = SHP.
  6. Alice's public key is (Hpub, t); her private key is (S, H, P).

Message encryption

Suppose Bob wishes to send a message, m, to Alice whose public key is (Hpub, t):

  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 s = h ( d ) {\displaystyle s=h(d)}, where h {\displaystyle h} is a Hash Function and d {\displaystyle d} is the signed document.
  2. Calculate s i = h ( s | i ) , i = 0 , 1 , 2 , … {\displaystyle s_{i}=h(s|i),i=0,1,2,\dots }, where | {\displaystyle |} denotes concatenation.
  3. Attempt to decrypt s i {\displaystyle s_{i}} until the smallest value of i {\displaystyle i} (denoted further as i 0 {\displaystyle i_{0}}) for which s i {\displaystyle s_{i}} is decryptable is found.
  4. Use the trapdoor function to compute such z {\displaystyle z} that H z T = s i 0 {\displaystyle Hz^{T}=s_{i_{0}}}, where H {\displaystyle H} is the public key.
  5. Compute the index I z {\displaystyle I_{z}} of z {\displaystyle z} in the space of words of weight 9.
  6. Use [ I z | z ] {\displaystyle \left[I_{z}|z\right]} as the signature.

The Verification algorithm is much simpler:

  1. Recover z {\displaystyle z} from index I z {\displaystyle I_{z}}.
  2. Compute s 1 = H z T {\displaystyle s_{1}=Hz^{T}} with the public key H {\displaystyle H}.
  3. Compute s 2 = h ( h ( d ) | i 0 ) {\displaystyle s_{2}=h(h(d)|i_{0})}.
  4. Compare s 1 {\displaystyle s_{1}} and s 2 {\displaystyle s_{2}}. If they are the same the signature is valid.

The index I z {\displaystyle I_{z}} of z {\displaystyle z} can be derived using the formula below, where i 1 < ⋯ < i 9 {\displaystyle i_{1}<\dots <i_{9}} denote the positions of non-zero bits of z {\displaystyle z}.I z = 1 + ∑ n = 1 9 ( i n n ) {\displaystyle I_{z}=1+\sum _{n=1}^{9}{\binom {i_{n}}{n}}}The number of bits necessary to store i 0 {\displaystyle i_{0}} is not reducible. On average it will be l o g 2 ( 9 ! ) ≈ 18.4 {\displaystyle log_{2}(9!)\approx 18.4} bits long. Combined with the average 125.5 {\displaystyle 125.5} bits necessary to store I z {\displaystyle I_{z}}, the signaure will on average be 125.5 + 18.4 ≈ 144 {\displaystyle 125.5+18.4\approx 144} bits long.

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

External links

  • Daniel J. Bernstein and Tanja Lange and Christiane Peters