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

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.