Informatics and Applications
2026, Volume 20, Issue 2, pp 2-24
THE SCHUR-HADAMARD SQUARE OF A RANDOM SUBCODE OF A RANDOM LINEAR CODE OVER A FIELD OF CHARACTERISTIC 2 EQUALS THE SQUARE OF THE ORIGINAL CODE WITH HIGH PROBABILITY
Abstract
The Schur-Hadamard square of a random subcode of a random linear code over a finite field of characteristic 2 is studied. Namely, for a uniformly random generator (k x n)-matrix G of a code C and a uniformly
It is proved 
the above probability differs from one by a quantity that is exponentially small in n, and this holds simultaneously for an overwhelming fraction of matrices G. This result provides a rigorous justification of an experimentally observed property that underlies several attacks on McEliece-type code-based cryptosystems built upon subcodes of generalized Reed-Solomon codes and algebraic-geometric codes. As a technical tool, exact formulas and tight upper bounds are derived for the number of totally isotropic subspaces of a given dimension of an arbitrary symmetric bilinear form of prescribed rank over a field of characteristic 2; these bounds maybe of independent interest.
[+] References (20)
- Couvreur, A., I. Maarquez-Corbella, and R. Pellikaan. 2015. Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes. Algebraic geometry modeling in information theory. Eds. R. Pellikaan, X. Wu, and S. Yao. Ser. on number theory and its applications. World Scientific. 8:201-234. doi: 10.1142/ 9789814678701_0010.
- Kotter, R. 1992. A unified description of an error locating procedure for linear codes. 3rd Workshop (International) on Algebraic and Combinatorial Coding Theory Proceedings. Voneshta Voda, Bulgaria: Hermes. 113-117.
- Pellikaan, R. 1992. On decoding by error location and dependent sets of error positions. Discrete Math. 106/107(1):369-381. doi: 10.1016/0012- 365X(92)90567-Y.
- Randriambololona, H. 2015. On products and powers of linear codes under componentwise multiplication. Algorithmic arithmetic, geometry, and coding theory. Eds.
S. Ballet, J.-M. Couveignes, D. Kohel, and R. Rolland. Contemporary mathematics ser. Providence, RI: American Mathematical Society 637:3-78. doi: 10.1090/conm/ 637/12749.
- Cascudo, I., R. Cramer, D. Mirandola, and G. Zeemor. 2015. Squares of random linear codes. IEEE T. Inform. Theory 61(3):1159-1173. doi: 10.1109/TIT. 2015.2393251.
- Chizhov, I. V. 2025. Hadamard square of linear codes and the generalized minimal distance of Reed-Muller code of order2. Discrete Mathematics Applications 35(1): 15-34. doi: 10.1515/dma-2025-0002. EDN: ATTIEX.
- Chizhov, I. V. 2025. Neasimptoticheskaya otsenka veroyatnosti togo, chto kvadrat Shura-Adamara sluchaynogo dlinnogo lineynogo koda imeet maksimal'nuyu razmernost' [A non-asymptotic estimate of the probability that a Shur-Hadamard square of long random linear code has a maximum dimension]. Prikladnaya diskretnaya mate- matika [Applied Discrete Mathematics] 68:56-70. doi: 10.17223/20710410/68/4. EDN: SYHLAQ.
- Wieschebrink, C. 2010. Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. Post-quantum cryptography. Ed. N. Sendrier. Lecture notes in computer
science ser. Berlin, Heidelberg: Springer. 6061:61-72. doi: 10.1007/978-3-642-12929-2_5.
- McEliece, R. J. 1978. Apublic-key cryptosystem based on algebraic coding theory. DSN Progress Report 42-44:114- 116.
- Sidelnikov, V. M., and S. O. Shestakov. 1992. On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics Applications 2(4):439-444. doi: 10.1515/dma.1992.2.4.439.
- Couvreur,A., M. Lequesne, and J.-P Tillich. 2019. Recovering short secret keys of RLCE in polynomial time. Postquantum cryptography. Eds. J. Ding and R. Steinwandt. Lecture notes in computer science ser. Cham: Springer. 11505:133-152. doi: 10.1007/978-3-030-25510-7.8.
- Couvreur, A., R. Pratihar, N. Tanisali, and I. Zappatore. 2025. On the structure of the Schur squares of twisted generalized Reed-Solomon codes and application to cryptanalysis. Post-quantum cryptography. Eds. R. Niederhagen and M.-J. O. Saarinen. Lecture notes in computer science ser. Cham: Springer. 15577:3-34. doi: 10.1007/978-3- 031-86599-2.1.
- Couvreur, A., P Gaborit, V. Gauthier-Umam, A. Otmani, and J.-P. Tillich. 2014. Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes. Design. Cod. Cryptogr. 73(2):641-666. doi: 10.1007/s10623-014-9967-z.
- Marquez-Corbella, I., E. Martinez-Moro, and R. Pel- likaan. 2013. The non-gap sequence of a subcode of a generalized Reed-Solomon code. Design. Cod. Cryptogr. 66(3):317-333. doi: 10.1007/s10623-012-9694-2.
- Chizhov, I. and M. Borodin. 2022. Classification of Hadamard products of one-codimensional subcodes of Reed-Muller codes. Discrete Mathematics Applications 32(5):297-311. doi: 10.1515/dma-2022-0025.
- Chizhov, I. V. 2024. Complete classification of Hadamard products of codimension 1 subcodes of Reed-Muller codes. Moscow University Computational Mathematics Cybernetics 48(1):65-78. doi: 10.3103/S0278641924010023. EDN: ORUCNZ.
- Vysotskaya, V. V. 2021. Characteristics of Hadamard square of special Reed-Muller subcodes. Prikladnaya diskretnaya matematika [Applied Discrete Mathematics] 53:75-88. doi: 10.17223/20710410/53/5. EDN: TEDEFN.
- Guenda, K., S. Jitman, and T.A. Gulliver. 2017. Constructions of good entanglement-assisted quantum error correcting codes. Design. Cod. Cryptogr. 86(1):121-136. doi: 10.1007/s10623-017-0330-z.
- Pless, V 1965. The number of isotropic subspaces in a finite geometry. AttiAccad. Naz. Lin. 39(6):418-421.
- Li, S., M. Shi, and S. Ling. 2025. A mass formula for linear codes with prescribed hull dimension and related classification. IEEE T. Inform. Theory 71(1):273-286. doi: 10.1109/TIT.2024.3425058.
[+] About this article
Title
THE SCHUR-HADAMARD SQUARE OF A RANDOM SUBCODE OF A RANDOM LINEAR CODE OVER A FIELD OF CHARACTERISTIC 2 EQUALS THE SQUARE OF THE ORIGINAL CODE WITH HIGH PROBABILITY
Journal
Informatics and Applications
2026, Volume 20, Issue 2, pp 2-24
Cover Date
2026-10-07
DOI
10.14357/19922264260201
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
Schur square; random subcode of a linear code; totally isotropic subspace of a symmetric bilinear form; code-based cryptography
Authors
I. V. Chizhov  , 
Author Affiliations
M. V Lomonosov Moscow State University, 1-52 Leninskie Gory, GSP-1, Moscow 119991, Russian Federation
Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|