Structural attack on McEliece-Sidelnikov type public-key cryptosystem based on a combination of random codes with Reed-Muller codes

Ivan Chizhov, Elizaveta Popova

Abstract


This paper represents the investigation of McEliece-Sidelnikov cryptosystem, based on combination of random codes with Reed-Muller codes. Different modifications of classical McEliece cryptosystem has been studied. Sidelnikov’s work introduced using the several samples of Reed-Muller code, and Kabatiansky and Tavernier’s work proposed to use the concatenation of Goppa and Reed-Muller codes. The popularity of this cryptosystem explains with the fact that it’s strength is based on the hardness of the decoding general linear code problem, so it will remain unbreakable in postquantum era. This paper investigates one of the modifications of McElice cryptosystem in a model when the attacker knows the public-key matrix and the generator matrix of random linear code. The goal is to reconstruct the permutation matrix from the secret-key. During the investigation of the hull of the code built by combining random codes with Reed-Muller codes the theorem about the number of such codes with fixed size of the hull has been proved. An attack based on signature method has been produced and programmed with the use of C++ programming language. All the results of this program’s work are represented in this paper. With the use of proved theorem the hardness of provided attack has been calculated.

Full Text:

PDF (Russian)

References


J. Mceliece R. A Public-Key Cryptosystem Based on Algebraic Coding Theory // JPL DSN Prog. Rep. 1978. Vol. 44. P. 123–125.

Shor P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // SIAM J. Comput. 1997. Vol. 26, № 5. P. 1484–1509.

Courtois N.T., Finiasz M., Sendrier N. How to Achieve a McEliece-Based Digital Signature Scheme // Advances in Cryptology — ASIACRYPT 2001 / ed. Boyd C. Berlin, Heidelberg: Springer, 2001. P. 157–174.

V. M. Sidelnikon, “Open encryption based on Reed-Muller codes”, Discrete Math. Appl., 4:3 (1994), 191–207.

Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov Cryptosystem // Advances in Cryptology - EUROCRYPT 2007 / ed. Naor M. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. Vol. 4515. P. 347–360.

Borodin М.А. et al. Effective attack on the McEliece public key cryptosystem based on Reed-Muller codes // Discrete Mathematic. 2014. Vol. 26, № 1. P. 10–20.

Egorova E. et al. A new code-based public-key cryptosystem resistant to quantum computer attacks // J. Phys. Conf. Ser. 2019. Vol. 1163. P. 012061.

McWilliams, F. J., and N. J. Sloane. The Theory of Error Correcting Codes, North Mathematical Library, Vol. 16. (1983).

Berlekamp E., McEliece R.J., van Tilborg H.C. On the Inherent Intractability of Certain Coding Problems // Inf. Theory IEEE Trans. On. 1978. Vol. 24, № 3. P. 384–386.

Sendrier N. Finding the permutation between equivalent linear codes: the support splitting algorithm // IEEE Trans. Inf. Theory. 2000. Vol. 46, № 4. P. 1193–1203.

Mirandola D., Zémor G. Schur products of linear codes: a study of parameters // Diss Master Thesis Superv. G Zémor Univ Bordx. 2012. 12. Sendrier N. On the Dimension of the Hull // SIAM J. Discrete Math. 1997. Vol. 10, № 2. P. 282–293.

Sendrier N. On the Dimension of the Hull // SIAM J. Discrete Math. 1997. Vol. 10, № 2. P. 282–293.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162