Geodesic
Search for equivalent keys of the McEliece–Sidelnikov cryptosystem built on the Reed–Muller binary codes
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 98-100

Voir la notice de l'article provenant de la source Math-Net.Ru

A new method is proposed for recovering equivalent secret keys of the McEliece–Sidelnikov cryptosystem built on the Reed–Muller binary codes. It is proved that using the superposition of Schur product and taking the orthogonal code we can obtain from the code with generating matrix $(R||HR)$ the code belonging to the Cartesian product of codes $\text{RM}(m-r\left(\left\lceil{m}/{r}\right\rceil-1\right)-1,m) \times \text{RM}(m-r(\lceil{m}/{r}\rceil-1)-1,m)$. Here, $R$ is the generating matrix of the Reed–Muller code of order $r$ and length $2^m$. Thus, proposed method reduces the problem of recovering equivalent secret keys of the McEliece–Sidelnikov cryptosystem to two problems of finding the equivalent secret key of the McEliece cryptosystem. It is proved that the offered algorithm works in a polynomial time. Numerical experiments confirm the theoretical results.
Keywords: McEliece–Sidelnikov cryptosystem, Reed–Muller code, polynomial attack. 
A. M. Davletshina. Search for equivalent keys of the McEliece–Sidelnikov cryptosystem built on the Reed–Muller binary codes. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 98-100. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a30/
@article{PDMA_2019_12_a30,
     author = {A. M. Davletshina},
     title = {Search for equivalent keys of the {McEliece{\textendash}Sidelnikov} cryptosystem built on the {Reed{\textendash}Muller} binary codes},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {98--100},
     year = {2019},
     number = {12},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a30/}
}
TY  - JOUR
AU  - A. M. Davletshina
TI  - Search for equivalent keys of the McEliece–Sidelnikov cryptosystem built on the Reed–Muller binary codes
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 98
EP  - 100
IS  - 12
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a30/
LA  - ru
ID  - PDMA_2019_12_a30
ER  - 
%0 Journal Article
%A A. M. Davletshina
%T Search for equivalent keys of the McEliece–Sidelnikov cryptosystem built on the Reed–Muller binary codes
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 98-100
%N 12
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a30/
%G ru
%F PDMA_2019_12_a30

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

[2] Minder L., Shokrollahi A., “Cryptanalysis of the Sidelnikov cryptosystem”, Ann. Intern. Conf. Theory and Appl. of Cryptographic Techniques, Springer, Berlin–Heidelberg, 2007, 347–360 | MR | Zbl

[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 | DOI | Zbl

[4] Sendrier N., “On the structure of a randomly permuted concatenated code”, Proc. EUROCODE'94 (Cote d'Or, France, 1994), 169–173