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

The Verification algorithm is much simpler:

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

The index [math]\displaystyle{ I_z }[/math] of [math]\displaystyle{ z }[/math] can be derived using the formula below, where [math]\displaystyle{ i_1\lt \dots\lt i_9 }[/math] denote the positions of non-zero bits of [math]\displaystyle{ z }[/math].[math]\displaystyle{ I_z = 1 + \sum_{n=1}^{9}{\binom{i_n}{n}} }[/math]The number of bits necessary to store [math]\displaystyle{ i_0 }[/math] is not reducible. On average it will be [math]\displaystyle{ log_2(9!)\approx 18.4 }[/math] bits long. Combined with the average [math]\displaystyle{ 125.5 }[/math] bits necessary to store [math]\displaystyle{ I_z }[/math], the signaure will on average be [math]\displaystyle{ 125.5+18.4\approx 144 }[/math] 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