On some properties of the Schur~--- Hadamard product for linear codes and their applications

V. M. Deundyak ; Yu. V. Kosolapov

Prikladnaâ diskretnaâ matematika, no. 4 (2020), pp. 72-86

Résumé

The Shur — Hadamard product is actively used in the cryptanalysis of asymmetric code cryptosystems like McEliece based on linear codes. Namely, this product is successfully used in cryptanalysis of code systems on subcodes of generalized Reed — Solomon codes, on binary Reed — Muller codes and their subcodes of codimension 1, on the combination of some well known codes. As a way to enhance the security of a cryptosystem, the authors have previously proposed a system based on the tensor product of linear codes. In order to analyze the security of this system, in this paper we study the properties of the Schur — Hadamard product for the tensor product of arbitrary linear codes. As a result, necessary and sufficient conditions are obtained when the $s$th power of the tensor product of codes is permutationally equivalent to the direct sum of codes. This result allows, in particular, to choose the parameters of linear codes so that the Schur — Hadamard product for the tensor product coincides with the entire space in which this product is defined. Thus, the parameters of linear codes can be determined, at which the attack based on the Shur — Hadamard product applied to the public key fails. Also, some new results on the Schur — Hadamard product for linear codes were obtained, which made it possible, in particular, to prove the indecomposability of binary Reed — Muller codes. A theorem on the structure of the group of permutation automorphisms of a direct sum of indecomposable codes is proved.

Détail

Keywords: tensor product codes, decomposability of codes, McEliece type systems.