Search for equivalent keys of the McEliece--Sidelnikov cryptosystem built on the Reed--Muller binary codes

A. M. Davletshina

Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 98-100

Résumé

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.

Détail

Keywords: McEliece–Sidelnikov cryptosystem, Reed–Muller code, polynomial attack.