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 $Hz^{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 $\left[I_{z}|z\right]$ as the signature.

The Verification algorithm is much simpler:

1. Recover $z$ from index $I_{z}$.
2. Compute $s_{1}=Hz^{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}{\binom {i_{n}}{n}}$$The number of bits necessary to store $i_{0}$ is not reducible. On average it will be $log_{2}(9!)\approx 18.4$ bits long. Combined with the average $125.5$ bits necessary to store $I_{z}$, the signature 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