Niederreiter cryptosystem

☆ Save On Wikipedia ↗

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, Hpub = SHP.
  6. Alice's public key is (Hpub, t); her private key is (S, H, P).

Message encryption

Suppose Bob wishes to send a message, m, to Alice whose public key is (Hpub, t):

  1. Bob encodes the message, m, as a binary string em' of length n and weight at most t.
  2. Bob computes the ciphertext as c = HpubeT.

Message decryption

Upon receipt of c = HpubmT from Bob, Alice does the following to retrieve the message, m.

  1. Alice computes S−1c = HPmT.
  2. Alice applies a syndrome decoding algorithm for G to recover PmT.
  3. Alice computes the message, m, via mT = P−1PmT.

Signature scheme

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

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

The Verification algorithm is much simpler:

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

The index I z {\displaystyle I_{z}} {\displaystyle I_{z}} of z {\displaystyle z} {\displaystyle z} can be derived using the formula below, where i 1 < ⋯ < i 9 {\displaystyle i_{1}<\dots <i_{9}} {\displaystyle i_{1}<\dots <i_{9}} denote the positions of non-zero bits of z {\displaystyle z} {\displaystyle z}. I z = 1 + ∑ n = 1 9 ( i n n ) {\displaystyle I_{z}=1+\sum _{n=1}^{9}{\binom {i_{n}}{n}}} {\displaystyle I_{z}=1+\sum _{n=1}^{9}{\binom {i_{n}}{n}}}The number of bits necessary to store i 0 {\displaystyle i_{0}} {\displaystyle i_{0}} is not reducible. On average it will be l o g 2 ( 9 ! ) ≈ 18.4 {\displaystyle log_{2}(9!)\approx 18.4} {\displaystyle log_{2}(9!)\approx 18.4} bits long. Combined with the average 125.5 {\displaystyle 125.5} {\displaystyle 125.5} bits necessary to store I z {\displaystyle I_{z}} {\displaystyle I_{z}}, the signature will on average be 125.5 + 18.4 ≈ 144 {\displaystyle 125.5+18.4\approx 144} {\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.