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.

References

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

1. H. Niederreiter (1986). "Knapsack-type cryptosystems and algebraic coding theory". Problems of Control and Information Theory. Problemy Upravlenija I Teorii Informacii. 15: 159–166.
2. V. M. Sidel'nikov & S. O. Shestakov (1992). "On the insecurity of cryptosystems based on generalized Reed-Solomon codes". Discrete Mathematics and Applications. 2 (4): 439–444. doi:10.1515/dma.1992.2.4.439. S2CID   120779674.
3. N. Courtois; M. Finiaz; N. Sendrier (2001). "How to Achieve a McEliece-Based Digital Signature Scheme". Advances in Cryptology — ASIACRYPT 2001. Lecture Notes in Computer Science. Vol. LNCS 2248. pp. 163–164. doi: 10.1007/3-540-45682-1_10 . ISBN   978-3-540-42987-6.
4. Makoui, Farshid Haidary; Gulliver, Thomas Aaron; Dakhilalian, Mohammad (17 December 2022). "A new code-based digital signature based on the McEliece cryptosystem". IET Communications. 17 (10). Institution of Engineering and Technology (published 6 April 2023): 1199–1207. doi: 10.1049/cmu2.12607 .

External links

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