On the strength of asymmetric code cryptosystems based on the merging of generating matrices of linear codes

The resistance to attacks on a key of code cryptosystems based on the merging of generating matrices of u(∈ ℕ) linear [n
_i
, k, d
_i
]
_q
-codes C
_i
(⊆ F
_q
ⁿ⁽ⁱ⁾
), i = 1, ..., u, are considered. The resistance of such cryptosystems in particular is based on the assumption that for u ≥ 2 in the public key matrix G̃ it is computationally difficult to find such (k × n
_i
)-submatrices composed of n
_i
columns of the matrix G̃, which would be generating matrices of codes permutably equivalent to the codes C
_i
, i = 1, ..., u. In the present paper an algorithm is constructed which can be used to efficiently find such submatrices when a number of easily verified conditions are met. It is shown that the constructed algorithm can be used to clarify the strength of the Sidelnikov cryptosystem and its modification for u = 2.