The use of the direct sum decomposition algorithm for analyzing the strength of some McEliece type cryptosystems

V. M. Deundyak ; Yu. V. Kosolapov

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 12 (2019) no. 3, pp. 89-101

Résumé

We construct a polynomial algorithm for decomposing an arbitrary linear code C into a direct sum of indecomposable subcodes with pairwise disjoint supports. The main idea of the constructed algorithm is to find the basis of a linear code consisting of minimal code vectors, that is, such vectors whose supports are not contained in the supports of other code vectors of this linear code. Such a basis is found in the polynomial number of operations, which depends on the code length. We use the obtained basis and the cohesion of supports of minimal code vectors in order to find the basic vectors of indecomposable subcodes such that the original linear code is the direct sum of these subcodes. Based on the obtained algorithm, we construct an algorithm of structural attack for asymmetric McEliece type cryptosystem based on code C, which polynomially depends on the complexity of structural attacks for McEliece type cryptosystems based on subcodes. Therefore, we show that the use of a direct sum of codes does not significantly enhance the strength of a McEliece-type cryptosystem against structural attacks.

Détail

Keywords: direct sum of codes, McEliece type cryptosystem, attack on the key.

Bibliographie

[1] McEliece R. J., “A Public-Key Cryptosystem Based on Algebraic Coding Theory”, DSN Progress Report, 42–44 (1978), 114–116

[2] Sidel'nikov V. M., Shestakov S. O., “On an Encoding System Constructed on the Basis of Generalized Reed–Solomon Codes”, Discrete Mathematics and Applications, 2:4 (1992), 439–444 | DOI | MR | Zbl

[3] Deundyak V. M., Druzhinina M. A., Kosolapov Yu. V., “Modification of the Sidelnikov–Shestakov Cryptanalytic Algorithm for Generalized Reed–Solomon Codes and its Software Implementation”, Izvestiya vysshih uchebnyh zavedenij. Severo-Kavkazskij region. Tekhnicheskie nauki, 2006, no. 4, 15–19 (in Russian)

[4] Wieschebrink C., “Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes”, Third International Workshop (Berlin, 2010), 61–72 | MR | Zbl

[5] Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov Cryptosystem”, Advances in Cryptology–EUROCRYPT 2007, Lecture Notes Computer Science, 4515, 347–360 | DOI | MR | Zbl

[6] Borodin M. A., Chizhov I. V., “Effective Attack on the McEliece Cryptosystem Based on Reed–Muller Codes”, Discrete Mathematics and Applications, 26:1 (2014), 273–280 | DOI | MR | Zbl

[7] Deundyak V. M., Kosolapov Yu. V., “Cryptosystem on Induced Group Codes”, Modelling and Analysis of Information Systems, 23:2 (2016), 137–152 | MR

[8] Kosolapov Yu. V., Shigaev A. N., “On the Support Splitting Algorithm for Induced Codes”, Modelling and Analysis of Information Systems, 25:3 (2018), 276–290 (in Russian) | MR

[9] Sidel'nikov V. M., Coding Theory, Fizmatlit, M., 2008

[10] Morelos-Zaragoza R. H., The Art of Error Correcting Coding, John Wiley Sons, Chichester, West Sussex, 2006

[11] Massey J. L., “Minimal Codewords and Secret Sharing”, Proceeding of 6th Joint Swedish-Russian Workshop on Information Theory, 1993, 276–279

[12] Avgustinovich S. V., Gorkunov E. V., “On Automorphisms of Linear Codes over a Simple Field”, Siberian Electronic Mathematical Reports, 14 (2017), 210–217 (in Russian) | MR | Zbl

[13] Sendrier N., “On the Concatenated Structure of a Linear Code”, Applicable Algebra in Engineering, Communication and Computing, 9:3 (1998), 221–242 | DOI | MR | Zbl

[14] Berger T. P., Ourivski A. V., “Construction of New MDS Codes from Gabidulin Codes”, Proceedings of ACCT'9, 2004, 40–47

[15] Assmus E. F., “The Category of Linear Codes”, IEEE Transaction on Information Theory, 44:2 (1998), 612–629 | DOI | MR | Zbl

[16] Fripertinger H., Kerber A., “Isometry Classes of Indecomposable Linear Codess”, Lecture Notes in Computer Science, 948, 1995, 194–204 | DOI | MR | Zbl

[17] Sidel'nikov V. M., “A Public-Key Cryptosystem Based on Binary Reed–Muller Codes”, Discrete Mathematics and Applications, 4:3 (1994), 191–208 | DOI | MR | MR | Zbl

[18] Deundyak V. M., Kosolapov Yu. V., “On the Berger–Loidreau Cryptosystem on the Tensor Product of Codes”, Journal of Computational and Engineering Mathematics, 5:2 (2018), 16–33 | DOI | MR | Zbl

[19] Krasavin A. A., “Using the Modified $ (u | u + v) $-Construction in the McEliece Cryptosystem”, Trudy MFTI, 10:2 (2018), 189–191 (in Russian)

[20] Kabatiansky G., Tavernier C., “A New Code-Based Cryptosystem via Pseudorepetition of Codes”, Proceedings of ACCT XVI, 2018, 189–191

[21] Deundyak V. M., Kosolapov Yu. V., “Using the Tensor Product of Reed–Muller Codes in an Asymmetric McEliece Type Cryptosystem and Analyzing its Resistance to Attacks on a Cipher”, Computational Technologies, 22:4 (2017), 43–60 (in Russian) | MR