This article is cited in 3 papers

Mathematical Methods of Cryptography

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

A. M. Davletshina<sup>ab

a</sup> Infotecs, Moscow
^b Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

Abstract: 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.

UDC: 003.26, 519.725

DOI: 10.17223/2226308X/12/31

Bibliographic databases:

•