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^pub = SHP.
6. Alice's public key is (H^pub, 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^pub, t):

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

Message decryption

Upon receipt of c = H^pubm^T from Bob, Alice does the following to retrieve the message, m.

1. Alice computes S⁻¹c = HPm^T.
2. Alice applies a syndrome decoding algorithm for G to recover Pm^T.
3. Alice computes the message, m, via m^T = P⁻¹Pm^T.

Signature scheme

Courtois, Finiasz and Sendrier showed how the Niederreiter cryptosystem can be used to derive a signature scheme .

1. Calculate $s=h(d)$, where $h$ is a Hash Function and $d$ is the signed document.
2. Calculate $s_i=h(s|i),i=0,1,2,\dots$, where $|$ denotes concatenation.
3. Attempt to decrypt $s_i$ until the smallest value of $i$ (denoted further as $i_0$) for which $s_i$ is decryptable is found.
4. Use the trapdoor function to compute such $z$ that $H{z}^T=s_{i_0}$, where $H$ is the public key.
5. Compute the index $I_z$ of $z$ in the space of words of weight 9.
6. Use $[I_z|z]$ as the signature.

The Verification algorithm is much simpler:

1. Recover $z$ from index $I_z$.
2. Compute $s_1=H{z}^T$ with the public key $H$.
3. Compute $s_2=h(h(d)|i_0)$.
4. Compare $s_1$ and $s_2$. If they are the same the signature is valid.

The index $I_z$ of $z$ can be derived using the formula below, where $i_1<\dots <i_9$ denote the positions of non-zero bits of $z$.$$I_z=1+\sum _{n=1}^9(\genfrac{}{}{0ex}{}{i_n}{n})$$The number of bits necessary to store $i_0$ is not reducible. On average it will be $lo{g}_2(9!)\approx 18.4$ bits long. Combined with the average $125.5$ bits necessary to store $I_z$, the signaure will on average be $125.5+18.4\approx 144$ bits long.

References

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

External links

• Attacking and defending the McEliece cryptosystem Daniel J. Bernstein and Tanja Lange and Christiane Peters