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 [ni, k, di]q-codes $C_i (subseteq mathbb{F}_q^{n_i})$, 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 × ni)-submatrices composed of ni columns of the matrix G?, which would be generating matrices of codes permutably equivalent to the codes Ci, 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.