Abstract:
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.
Keywords:
direct sum of codes, McEliece type cryptosystem, attack on the key.
Citation:
V. M. Deundyak, Yu. V. Kosolapov, “The use of the direct sum decomposition algorithm for analyzing the strength of some McEliece type cryptosystems”, Vestnik YuUrGU. Ser. Mat. Model. Progr., 12:3 (2019), 89–101
\Bibitem{DeuKos19}
\by V.~M.~Deundyak, Yu.~V.~Kosolapov
\paper The use of the direct sum decomposition algorithm for analyzing the strength of some McEliece type cryptosystems
\jour Vestnik YuUrGU. Ser. Mat. Model. Progr.
\yr 2019
\vol 12
\issue 3
\pages 89--101
\mathnet{http://mi.mathnet.ru/vyuru507}
\crossref{https://doi.org/10.14529/mmp190308}
\elib{https://elibrary.ru/item.asp?id=41265006}
Linking options:
https://www.mathnet.ru/eng/vyuru507
https://www.mathnet.ru/eng/vyuru/v12/i3/p89
This publication is cited in the following 5 articles:
Yu. V. Kosolapov, E. A. Lelyuk, “O strukturnoi stoikosti kriptosistemy tipa Mak-Elisa na summe tenzornykh proizvedenii binarnykh kodov Rida — Mallera”, PDM, 2022, no. 57, 22–39
Yu. V. Kosolapov, E. A. Lelyuk, “O razlozhimosti proizvedeniya Shura — Adamara summy tenzornykh proizvedenii kodov Rida — Mallera”, PDM. Prilozhenie, 2021, no. 14, 158–161
V. M. Deundyak, Yu. V. Kosolapov, “O nekotorykh svoistvakh proizvedeniya Shura — Adamara dlya lineinykh kodov i ikh prilozheniyakh”, PDM, 2020, no. 50, 72–86
Vladimir M. Deundyak, Yury V. Kosolapov, Igor A. Maystrenko, Lecture Notes in Computer Science, 12087, Code-Based Cryptography, 2020, 20
V.M. Deundyak, Yu.V. Kosolapov, 2019 XVI International Symposium “Problems of Redundancy in Information and Control Systems” (REDUNDANCY), 2019, 143
Citation in format AMSBIB
Contact us: