Geodesic
Classification of Hadamard productsof one-codimensional subcodesof Reed–Muller codes
Diskretnaya Matematika, Tome 32 (2020) no. 1, pp. 115-134
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

For Reed–Muller codes we consider subcodes of codimension 1. A classification of Hadamard products of such subcodes is obtained. With the use of this classification it has been shown that in most cases the problem of recovery of the secret key of a code-based cryptosystem employing such subcodes is equivalent to the problem of recovery of the secret key of the same cryptosystem based on Reed–Muller codes, which is known to be tractable.
Keywords: McEliece public key cryptosystem, code-based cryptosystems, Reed–Muller codes, square of a code, classification of Hadamard products, subcodes of codimension 1.
Mots-clés : cryptanalysis, Hadamard product 
@article{DM_2020_32_1_a8,
     author = {I. V. Chizhov and M. A. Borodin},
     title = {Classification of {Hadamard} productsof one-codimensional subcodesof {Reed{\textendash}Muller} codes},
     journal = {Diskretnaya Matematika},
     pages = {115--134},
     year = {2020},
     volume = {32},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2020_32_1_a8/}
}
TY  - JOUR
AU  - I. V. Chizhov
AU  - M. A. Borodin
TI  - Classification of Hadamard productsof one-codimensional subcodesof Reed–Muller codes
JO  - Diskretnaya Matematika
PY  - 2020
SP  - 115
EP  - 134
VL  - 32
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2020_32_1_a8/
LA  - ru
ID  - DM_2020_32_1_a8
ER  - 
%0 Journal Article
%A I. V. Chizhov
%A M. A. Borodin
%T Classification of Hadamard productsof one-codimensional subcodesof Reed–Muller codes
%J Diskretnaya Matematika
%D 2020
%P 115-134
%V 32
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2020_32_1_a8/
%G ru
%F DM_2020_32_1_a8
I. V. Chizhov; M. A. Borodin. Classification of Hadamard productsof one-codimensional subcodesof Reed–Muller codes. Diskretnaya Matematika, Tome 32 (2020) no. 1, pp. 115-134. http://geodesic.mathdoc.fr/item/DM_2020_32_1_a8/

[1] R. J. McEliece, “A public-key cryptosystem based on algebraic coding theory”, Coding Thv, 4244 (1978), 114–116

[2] V. M. Sidelnikov, “Otkrytoe shifrovanie na osnove dvoichnykh kodov Rida–Mallera”, Diskretnaya matematika, 6:2 (1994), 3–20 | MR | Zbl

[3] L. Minder, A. Shokrollahi, “Cryptanalysis of the Sidelnikov cryptosystem”, Lect. Notes Comput. Sci., 4515 (2007), 347–360 | DOI | MR | Zbl

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

[5] T. P. Berger, P. Loidreau, “How to mask the structure of codes for a cryptographic use”, Designs, Codes and Cryptography, 35:1 (2005), 63-79 | DOI | MR | Zbl

[6] V. M. Sidelnikov, S. O. Shestakov, “O sisteme shifrovaniya, postroennoi na osnove obobschennykh kodov Rida–Solomona”, Diskretnaya matematika, 4:3 (1992), 57–63 | Zbl

[7] C. Wieschebrink, “An attack on a modified Niederreiter encryption scheme”, Lect. Notes Comput. Sci., 3958 (2006), 14-26 | DOI | MR | Zbl

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

[9] A. Couvreur, I. Marquez-Corbella, R. Pellikaan, “Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes”, Coding Theory Appl., 2015, 133-140 | DOI | MR | Zbl

[10] A. Couvreur, P. Gaborit, V. Gauthier-Uma{ñ}a, A. Otmani, J.-P. Tillich, “Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes”, Designs, Codes and Cryptography, 73:2 (2014), 641–666 | DOI | MR | Zbl

[11] A. Otmani, H. T. Kalachi, “Square code attack on a modified Sidelnikov cryptosystem”, Codes, Cryptology, and Information Security, 2015, 173–183 | DOI | MR | Zbl

[12] A. Couvreur, A. Otmani, J.-P. Tillich, V. Gauthier–Umana, “A polynomial-time attack on the BBCRS scheme”, IACR Int. Workshop on Public Key Cryptogr., 2015, 175–193 | MR | Zbl

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

[14] F. Dzh. Mak-Vilyams, N. Dzh. A. Sloen, Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, Moskva, 1979; MacWilliams E. J., Sloane N. J. A., The Theory of Error-Correcting Codes, Parts I, II, North-Holland, Amsterdam, 1977 | MR | Zbl