On decomposability of Schur~--- Hadamard product of the tensor products sum of Reed~--- Muller codes

Yu. V. Kosolapov ; E. A. Lelyuk

Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 158-161.

Résumé

McEliece code-based cryptosystems are considered to be a perspective alternative to modern asymmetric cryptosystems, because by choosing a suitable error-correcting code they are assume to be resistant to attacks by computer based on a quantum computing model. The original McEliece cryptosystem based on Goppa codes is now considered to be resistant. It should be noted that high resistance is achieved by using a large key size. In order to reduce the key size, cryptosystems of the McEliece type based on another error-correcting codes have been proposed. But for some well-known codes, such as generalized Reed — Solomon codes and binary Reed — Muller codes, these cryptosystems turn out to be broken even by computers based on the classical Turing model. Earlier, to enhance the resistance, it was proposed to use the tensor product of Reed — Muller codes. The natural generalization of this approach is using the class of codes that are the sum of several tensor products of a special form. Such codes are effectively decoded, so a McEliece type cryptosystem can be built on their basis. In order to use a cryptosystem, its resistance should be analized. For analysis of the code-based cryptosystems resistance to a structural attacks, the properties of the Schur — Hadamard product of codes that lie in the basis of these cryptosystems are often investigated. In the paper, we investigate the decomposability of codes that are a special sum of two tensor products of Reed — Muller codes. In a number of cases, we found conditions on the parameters of the multiplier codes that lead us to decomposition of the square of the code under consideration into a direct sum of Reed — Muller codes. Conditions were also found under which such a decomposition is impossible.

Détail

Keywords: McEliece type cryptosystem, sum of tensor products, Schur — Hadamard product, decomposability.

Bibliographie

[1] Sendrier N., Tillich J.-P., Code-Based Cryptography: New Security Solutions Against a Quantum Adversary., ERCIM News, ERCIM, 2016

[2] Supporting Documentation describing the round-3 submission, , 2020 https://classic.mceliece.org/nist/mceliece-20201010.pdf

[3] Sidelnikov V. M., Shestakov S. O., “O sisteme shifrovaniya, osnovannoi na obobschennykh kodakh Rida — Solomona”, Diskretnaya matematika, 3:3 (1992), 57–63 | Zbl

[4] Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, LNCS, 4515, 2007, 347–360 | MR | Zbl

[5] Chizhov I. I., Borodin M. A., “Effektivnaya ataka na kriptosistemu Mak-Elisa, postroennuyu na osnove kodov Rida — Mallera”, Diskretnaya matematika, 26:1 (2014), 10–20 | MR | Zbl

[6] Deundyak V. M., Kosolapov Yu. V., Lelyuk E. A., “Dekodirovanie tenzornogo proizvedeniya MLD-kodov i prilozheniya k kodovym kriptosistemam”, Model. i analiz inform. sistem, 24:2 (2017), 137–152 | MR

[7] Deundyak V. M., Lelyuk E. A., “Teoretiko-grafovyi metod dekodirovaniya nekotorykh gruppovykh MLD-kodov”, Diskretn. analiz i issled. oper., 27:2 (2020), 17–42 | MR

[8] Randriambololona H., On products and powers of linear codes under componentwise multiplication, arXiv: 1312.0022 | MR

[9] Mak-Vilyams F. Dzh., Sloen N. Dzh. A., Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, M., 1979

[10] Deundyak V. M., Kosolapov Yu. V., “Analiz stoikosti nekotorykh kodovykh kriptosistem, osnovannyi na razlozhenii kodov v pryamuyu summu”, Vestn. YuUrGU. Ser. Matem. modelirovanie i programmirovanie, 12:3 (2019), 89–101 | MR | Zbl

[11] Deundyak V. M., Kosolapov Yu. V., “O nekotorykh svoistvakh proizvedeniya Shura — Adamara dlya lineinykh kodov i ikh prilozheniyakh”, Prikladnaya diskretnaya matematika, 2020, no. 50, 72–86 | Zbl