Niederreiter cryptosystem

In cryptography, the Niederreiter cryptosystem is a variation of the McEliece cryptosystem developed in 1986 by Harald Niederreiter.^[1] 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^[2] 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 .^[3][4]

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

The Verification algorithm is much simpler:

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

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