The use of the direct sum decomposition algorithm for analyzing the strength of some McEliece-type cryptosystems. (Russian. English summary) Zbl 1427.68076

Summary: 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.


68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
94A60 Cryptography


Full Text: DOI MNR


[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 · Zbl 0796.94006
[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 · Zbl 1284.94124
[5] Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov Cryptosystem”, Advances in Cryptology-EUROCRYPT 2007, Lecture Notes Computer Science, 4515, 347-360 · Zbl 1141.94365
[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 · Zbl 1403.94045
[7] Deundyak V. M., Kosolapov Yu. V., “Cryptosystem on Induced Group Codes”, Modelling and Analysis of Information Systems, 23:2 (2016), 137-152
[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)
[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) · Zbl 1429.94072
[13] Sendrier N., “On the Concatenated Structure of a Linear Code”, Applicable Algebra in Engineering, Communication and Computing, 9:3 (1998), 221-242 · Zbl 0915.94008
[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 · Zbl 1105.94335
[16] Fripertinger H., Kerber A., “Isometry Classes of Indecomposable Linear Codess”, Lecture Notes in Computer Science, 948, 1995, 194-204 · Zbl 0877.94045
[17] Sidel’nikov V. M., “A Public-Key Cryptosystem Based on Binary Reed-Muller Codes”, Discrete Mathematics and Applications, 4:3 (1994), 191-208 · Zbl 0872.94040
[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 · Zbl 1429.94057
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.