Cryptanalysis of the BBCRS system on Reed–Muller binary code

The paper considers the BBCRS system which is a modification of the McEliece cryptosystem proposed by M. Baldi and some others. In this modification matrix $G_{pub}$ of the public key is the product of three matrices: a non-singular $(k\times k)$-matrix $S$, a generator matrix $G$ of a secret $[n,k]_q$-code $C_{sec}$, and a non-singular $(n\times n)$-matrix $Q$. The difference between the modified system and the original system is that the permutation matrix used in the McEliece system is replaced by a non-singular matrix $Q$. The matrix $Q$ is obtained as the sum of a permutation matrix $P$ and a matrix $R$ of small rank $r(R)$. Later, V. Gauthier and some others constructed an attack that allows decrypting messages in the case when $C_{sec}$ is a generalized Reed–Solomon code (GRS code) and $r(R)=1$. The key stages of the constructed attack are, firstly, finding the intersection of the linear span $\mathcal{L}(G_{pub})=C_{pub}$ and $\mathcal{L}(G P)=C$ that spanned on the rows of the matrices $G_{pub}$ and $G P$ respectively, and secondly, finding the code $C$ by the subcode $C_{pub}\cap C$. In this paper we present an attack in the case when $C_{sec}$ is the Reed–Muller binary code of order $r$, length $2^m$ and $r(R)=1$. The stages of finding the codes $C_{pub}\cap C$ and $C$ in this paper are completely different from the corresponding steps in attack by V. Gauthier and some others and other steps are the adaptation of the known results of cryptanalysis that applied in the case of GRS codes.