An estimate of the probability that the Hadamard (Schur-Hadamard) square of a random linear code of dimension k and dyne n > k(k + 1)/2 has the maximum possible dimension is established. The estimate is non-asymptotic in nature and can therefore be used to justify the complexity of cryptographic analysis methods for post-quantum cryptosystems built on the basis of the theory of error-correcting coding.
Download file
Counter downloads: 7
- Title A non-asymptotic estimate of the probability that a Shur-Hadamard square of long random linear code has a maximum dimension
- Headline A non-asymptotic estimate of the probability that a Shur-Hadamard square of long random linear code has a maximum dimension
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 68
- Date:
- DOI 10.17223/20710410/68/4
Keywords
Shur product of linear codes, Hadamard product of linear codes, Random codes, Shur square of linear code, Hadamard square of linear code, McEliece public key cryptosystemAuthors
References
Pellikaan R. On decoding by error location and dependent sets of error positions // Discrete Math. 1992. V. 106-107. P. 369-381.
Wieschebrink C. Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes // LNCS. 2010. V. 6061. P. 61-72.
Berger T. and Loidreau P. How to mask the structure of codes for a cryptographic use // Des. Codes Cryptogr. 2005. V. 35. P. 63-79.
Faugère J., Gauthier-Umana V., Otmani A., et al. A distinguisher for high-rate McEliece cryptosystems // IEEE Trans. Inform. Theory. 2013. V. 59. No. 10. P. 6830-6844.
Couvreur A., Gaborit P., Gauthier-Umana V., et al. Distinguisher-based attacks on publickey cryptosystems using Reed - Solomon codes // Des. Codes Cryptogr. 2014. V. 73. No. 2. P. 641-666.
Otmani A. and Kalachi Н. Square code attack on a modified Sidelnikov cryptosystem // LNCS. 2015. V. 9084. P. 173-183.
Couvreur A., Otmani A., Tillich J.-P., and Gauthier-Umana V. A polynomial-time attack on the BBCRS scheme // LNCS. 2015. V.9020. P. 175-193.
Бородин M. А., Чижов И. В. Эффективная атака на криптосистему Мак-Элиса, построенную на основе кодов Рида - Маллера // Дискретная математика. 2014. Т. 26. №1. С.10-20.
Чижов И. В., Попова Е. А. Структурная атака на криптосистемы типа Мак-Элиса - Сиделвникова, построенные на основе комбинирования случайных кодов с кодами Рида - Маллера // Intern. J. Open Inform. Technol. 2020. V.8. No. 6. P.24-33.
Бородин M. А., Чижов И. В. Классификация произведений Адамара подкодов коразмерности 1 кодов Рида - Маллера // Дискретная математика. 2020. Т. 32. N81. С. 115-134.
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.
Чижов И. В. Квадрат Адамара и обобщённое минималвное расстояние кода Рида - Маллера порядка 2 // Дискретная математика. 2023. Т. 35. №1. С. 128-152.
Мак-Вильямс Ф. Дж., Слоэп Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связи, 1979. 744с.
Hall J.I. Notes on Coding Theory, https://users.math.msu.edu/users/halljo/classes/C0DEN0TES/C0DING-NOTES.HTML, 2010.
Чижов И. В. Полная классификация произведений Адамара подкодов коразмерности 1 кодов Рида - Маллера // Вестник Московского университета. Сер. 15: Вычислителвная математика и кибернетика. 2024. №1. С. 67-80.
Randriambololona Н. On products and powers of linear codes under componentwise multiplication // Algorithmic Arithmetic, Geometry, and Coding Theory. 2015. V. 637. P.3-78.
Shuxing L. On the weight distribution of second order Reed - Muller codes and their relatives // Des. Codes Crvptogr. 2019. V.87. No. 10. P.2447-2460.
A non-asymptotic estimate of the probability that a Shur-Hadamard square of long random linear code has a maximum dimension | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 68. DOI: 10.17223/20710410/68/4
Download full-text version
Counter downloads: 70