Geodesic
On some properties of the Schur~--- Hadamard product for linear codes and their applications
Prikladnaâ diskretnaâ matematika, no. 4 (2020), pp. 72-86.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: tensor product codes, decomposability of codes, McEliece type systems. 
@article{PDM_2020_4_a4,
     author = {V. M. Deundyak and Yu. V. Kosolapov},
     title = {On some properties of the {Schur~---} {Hadamard} product for linear codes and their applications},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {72--86},
     publisher = {mathdoc},
     number = {4},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2020_4_a4/}
}
TY  - JOUR
AU  - V. M. Deundyak
AU  - Yu. V. Kosolapov
TI  - On some properties of the Schur~--- Hadamard product for linear codes and their applications
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2020
SP  - 72
EP  - 86
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2020_4_a4/
LA  - ru
ID  - PDM_2020_4_a4
ER  - 
%0 Journal Article
%A V. M. Deundyak
%A Yu. V. Kosolapov
%T On some properties of the Schur~--- Hadamard product for linear codes and their applications
%J Prikladnaâ diskretnaâ matematika
%D 2020
%P 72-86
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2020_4_a4/
%G ru
%F PDM_2020_4_a4
V. M. Deundyak; Yu. V. Kosolapov. On some properties of the Schur~--- Hadamard product for linear codes and their applications. Prikladnaâ diskretnaâ matematika, no. 4 (2020), pp. 72-86. http://geodesic.mathdoc.fr/item/PDM_2020_4_a4/

[1] R. J. McEliece, “A public-key cryptosystem based on algebraic coding theory”, DSN Progress Report, 1978, 42–44

[2] N. Sendrier, J. P. Tillich, “Code-Based Cryptography: New Security Solutions against a Quantum Adversary”, ERCIM News, ERCIM, 2016

[3] G. Alagic, J. Alperin-Sheriff, D. Apon et al, Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process, US Department of Commerce, NIST, 2019

[4] C. Wieschebrink, “Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes”, LNCS, 6061, 2010, 61–72

[5] M. A. Borodin, I. V. Chizhov, “Effective attack on the McEliece cryptosystem based on Reed Muller codes”, Discrete Math. Appl., 24:5 (2014), 273–280

[6] V. M. Deundyak, Yu. V. Kosolapov, “On the strength of asymmetric code cryptosystems based on the merging of generating matrices of linear codes”, XVI Intern. Symp. Prob. of Redundancy in Information and Control Systems (Russia, 2019), 143–148

[7] M. A. Borodin, I. V. Chizhov, “Classification of Hadamard products of codimension 1 subcodes of Reed–Muller codes”, Diskret. Matem., 32:1 (2020), 115–134 (in Russian)

[8] V. Vysotskaya, “The Reed–Muller code square and equivalence classes of McEliece–Sidelnikov cryptosystem private keys”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2017, no. 10, 66–68 (in Russian)

[9] V. Vysotskaya, I. Chizhov, “Equivalence classes of McEliece–Sidelnikov-type cryptosystems”, Sixteenth Intern. Workshop Algebraic Combinat. Coding Theory (Svetlogorsk (Kaliningrad region), Russia, 2018), 121–124

[10] A. M. Davletshina, “Search for equivalent keys of the McEliece - Sidelnikov cryptosystem built on the Reed–Muller binary codes”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2019, no. 12, 98–100 (in Russian)

[11] V. M. Deundyak, Yu. V. Kosolapov, I. A. Maystrenko, “On the decipherment of Sidel'nikov-type cryptosystems”, LNCS, 12087, 2020, 20–40

[12] V. M. Deundyak, Y. V. Kosolapov, E. A. Lelyuk, “Decoding the tensor product of MLD codes and applications for code cryptosystems”, Aut. Control Comp. Sci., 52:7 (2019), 647–657

[13] H. Randriambololona, On Products and Powers of Linear Codes under Componentwise Multiplication, 2014, arXiv: 1312.0022

[14] V. M. Deundyak, Yu. V. Kosolapov, “The use of the direct sum decomposition algorithm for analyzing the strength of some McEliece type cryptosystems”, Vestn. JuUrGU. Ser. Matem. Modelirovanie i Programmirovanie, 12:3 (2019), 89–101 (in Russian)

[15] I. Cascudo, R. Cramer, D. Mirandola, G. Zemor, “Squares of random linear codes”, IEEE Trans. Inform. Theory, 61:3 (2015), 1159–1173

[16] H. V. Henderson, S. R. Searle, “The vec-permutation matrix, the vec operator and Kronecker products: A review”, Linear and Multilinear Algebra, 9 (1981), 271–288

[17] V. M. Sidel'nikov, Coding Theory, Fizmatlit Publ, M., 2008, 324 pp. (in Russian)

[18] D. Slepian, “Some further theory of group codes”, Bell Syst. Tech. J., 39:5 (1960), 1219–1252

[19] E. F. Assmus, “The category of linear codes”, IEEE Trans. Inform. Theory, 44:2 (1998), 612–629

[20] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Pub. Co., Amsterdam–New York, 1977, 762 pp.