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 sth 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.
Download file
Counter downloads: 47
- Title On some properties of the Schur - Hadamard product for linear codes and their applications
- Headline On some properties of the Schur - Hadamard product for linear codes and their applications
- Publesher
Tomsk State University
- Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 50
- Date:
- DOI 10.17223/20710410/50/5
Keywords
tensor product codes, decomposability of codes, McEliece type systemsAuthors
References
McEliece R. J. A public-key cryptosystem based on algebraic coding theory // DSN Progress Report. 1978. P.42-44.
Sendrier N. and Tillich J. P. Code-Based Cryptography: New Security Solutions against a Quantum Adversary. ERCIM News. ERCIM, 2016.
Alagic G., Alperin-Sheriff J., Apon D., et al. Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process. US Department of Commerce, NIST, 2019.
Wieschebrink C. Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes // LNCS. 2010. V.6061. P.61-72.
Бородин М. А., Чижов И. В. Эффективная атака на криптосистему Мак-Элиса, построенную на основе кодов Рида - Маллера // Дискретная математика. 2014. Т. 26. №1. С. 10-20.
Deundyak V. M. and Kosolapov Yu. V. 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. P. 143-148.
Бородин М. А., Чижов И. В. Классификация произведений Адамара подкодов коразмерности 1 кодов Рида - Маллера // Дискретная математика. 2020. Т. 32. №1. С. 115-134.
Высоцкая В. В. Квадрат кода Рида - Маллера и классы эквивалентности секретных ключей криптосистемы Мак-Элиса - Сидельникова // Прикладная дискретная математика. Приложение. 2017. №10. С. 66-68.
Vysotskaya V. and Chizhov I. Equivalence classes of McEliece - Sidelnikov-type cryptosystems // Sixteenth Intern. Workshop Algebraic Combinat. Coding Theory. Svetlogorsk (Kaliningrad region), Russia, 2018. P.121-124.
Давлетшина А.М. Поиск эквивалентных ключей криптосистемы Мак-Элиса - Сидельникова, построенной на двоичных кодах Рида - Маллера // Прикладная дискретная математика. Приложение. 2019. № 12. С. 98-100.
Deundyak V. M., Kosolapov Yu. V., and Maystrenko I. A. On the decipherment of Sidel’nikov-type cryptosystems // LNCS. 2020. V. 12087. P.20-40.
Deundyak V.M., Kosolapov Y. V., and Lelyuk E. A. Decoding the tensor product of MLD codes and applications for code cryptosystems // Aut. Control Comp. Sci. 2019. V. 52. No. 7. P. 647-657.
Randriambololona H. On Products and Powers of Linear Codes under Componentwise Multiplication. arXiv:1312.0022. 2014.
Деундяк В. М., Косолапов Ю. В. Анализ стойкости некоторых кодовых криптосистем, основанный на разложении кодов в прямую сумму // Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование. 2019. Т. 12. №3. С. 89-101.
Cascudo I., Cramer R., Mirandola D., and Zemor G. Squares of random linear codes // IEEE Trans. Inform. Theory. 2015. V. 61. No.3. P.1159-1173.
Henderson H. V. and Searle S. R. The vec-permutation matrix, the vec operator and Kronecker products: A review // Linear and Multilinear Algebra. 1981. V.9. P.271-288.
Сидельников В. М. Теория кодирования. М.: Физматлит, 2008. 324c.
Slepian D. Some further theory of group codes // Bell Syst. Tech. J. 1960. V. 39. No. 5. P. 1219-1252.
Assmus E. F. The category of linear codes // IEEE Trans. Inform. Theory. 1998. V. 44. No. 2. P. 612-629.
Мак-Вильямс Ф. Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь, 1979. 746 c.

On some properties of the Schur - Hadamard product for linear codes and their applications | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 50. DOI: 10.17223/20710410/50/5
Download full-text version
Counter downloads: 193