Geodesic
Hadamard square of linear codes and the generalized minimal distance of Reed–Muller code of order 2
Diskretnaya Matematika, Tome 35 (2023) no. 1, pp. 128-152
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We propose a new technique for dimensional analysis of the Hadamard (Schur) square of an error-correcting linear code. This is usually achieved by a representation of the Hadamard square as an image of some linear operator defined on the set of quadratic forms. A link between the dimension of the Hadamard square and the rank of some submatrix of the generating matrix of the code containing the set of vector values of quadratic forms is established. So, the dimensional analysis of the Hadamard square can be carried out with the extensive code-based machinery, rather than via the approach with estimation of the number of joint zeros of the set of quadratic forms. As a result, we establish a nonasymptotic estimate for the probability that the Hadamard square of a random linear code fills the entire space. This estimate can be used for cryptographic analysis of post-quantum code-based cryptosystems.
Keywords: Hadamard square, Schur square, Hadamard product of linear codes, Schur product of linear codes, generalized minimal distance linear code, nondegenerate submatrices, Reed–Muller code. 
@article{DM_2023_35_1_a8,
     author = {I. V. Chizhov},
     title = {Hadamard square of linear codes and the generalized minimal distance of {Reed{\textendash}Muller} code of order~2},
     journal = {Diskretnaya Matematika},
     pages = {128--152},
     year = {2023},
     volume = {35},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2023_35_1_a8/}
}
TY  - JOUR
AU  - I. V. Chizhov
TI  - Hadamard square of linear codes and the generalized minimal distance of Reed–Muller code of order 2
JO  - Diskretnaya Matematika
PY  - 2023
SP  - 128
EP  - 152
VL  - 35
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2023_35_1_a8/
LA  - ru
ID  - DM_2023_35_1_a8
ER  - 
%0 Journal Article
%A I. V. Chizhov
%T Hadamard square of linear codes and the generalized minimal distance of Reed–Muller code of order 2
%J Diskretnaya Matematika
%D 2023
%P 128-152
%V 35
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2023_35_1_a8/
%G ru
%F DM_2023_35_1_a8
I. V. Chizhov. Hadamard square of linear codes and the generalized minimal distance of Reed–Muller code of order 2. Diskretnaya Matematika, Tome 35 (2023) no. 1, pp. 128-152. http://geodesic.mathdoc.fr/item/DM_2023_35_1_a8/

[1] Pellikaan R., “On decoding by error location and dependent sets of error positions”, Discrete Mathematics, 106–107 (1992), 369–381 | DOI | MR

[2] Chen H., Cramer R., “Algebraic geometric secret sharing schemes and secure multi-party computations over small fields”, CRYPTO 2006, Lect. Notes Comput. Sci., 4117, 2006, 521–536 | DOI | MR

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

[4] Wieschebrink C., “Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes”, PQCrypto 2010, Lect. Notes Comput. Sci., 6061, 2010, 61–72 | DOI | MR

[5] Couvreur C., Gaborit P., Gauthier-Umaña V., Otmani A., Tillich J.-P., “Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes”, Des. Codes Cryptogr., 73:2 (2014), 641–666 | DOI | MR

[6] Couvreur A., Márquez-Corbella I., Pellikaan R., “Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes”, Coding Theory and Applications, CIM Ser. in Math. Sci., 3, Springer, Cham, 2015, 133–140 | DOI | MR

[7] Couvreur A., Otmani A., Tillich J.-P., “Polynomial time attack on wild McEliece over quadratic extensions”, IEEE Trans. Inf. Theory, 63:1 (2017), 404–427 | DOI | MR

[8] Couvreur A., Otmani A., Tillich J.-P., Gauthier-Umaña V., “A polynomial-time attack on the BBCRS scheme”, PKC 2015, Lect. Notes Comput. Sci., 9020, 2015, 175–193 | DOI | MR

[9] Otmani A., Kalachi H. T., “Square code attack on a modified Sidelnikov cryptosystem”, C2SI 2015, Lect. Notes Comput. Sci., 9084, 2015, 173–183 | DOI | MR

[10] Faugére J., Gauthier-Umaña V., Otmani A., Perret L., Tillich J.-P., “A distinguisher for high-rate McEliece cryptosystems”, IEEE Trans. Inf. Theory, 59:10 (2013), 6830–6844 | DOI | MR

[11] Cascudo I., Cramer R., Mirandola D., Zémor G., “Squares of random linear codes”, IEEE Trans. Inf. Theory, 61:3 (2015), 1159–1173 | DOI | MR

[12] Bardet M., Bertin M., Couvreur A., Otmani A., “Practical algebraic attack on DAGS”, CBC 2019, Lect. Notes Comput. Sci., 11666, 2019, 86–101 | DOI

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

[14] Hall J. I., Notes on Coding Theory, Chapter 3: Linear Codes, 2010 https://users.math.msu.edu/users/halljo/classes/CODENOTES/Linear.pdf

[15] Heijnen P., Pellikaan R., “Generalized Hamming weights of $q$-ary Reed–Muller codes”, IEEE Trans. Inf. Theory, 44:1 (1998), 181–196 | DOI | MR

[16] Randriambololona H., “On products and powers of linear codes under componentwise multiplication”, AGCT 2013, Contemp. Math., 637, 2015, 3–78 | DOI | MR

[17] Wei V. K., “Generalized Hamming weights for linear codes”, IEEE Trans. Inf. Theory, 37:5 (1991), 1412–1418 | DOI | MR

[18] Delsarte P., Goethals J. M., Mac Williams F. J., “On generalized Reed–Muller codes and their relatives”, Inf. Control, 16:5 (1970), 403–442 | DOI | MR

[19] Abbe E., Shpilka A., Wigderson A., “Reed–Muller codes for random erasures and errors”, STOC'15: Proc. 47th Ann. ACM Symp. Theory Comput., Assoc. Comput. Mach., New York, 2015, 297–306 | MR