Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems (Q6112240)

The paper presents two cryptanalytic attacks, with polynomial time complexity, to the IKKR public-key cryptosystem, a code-based scheme due to \textit{F. Ivanov} et al. [Lect. Notes Comput. Sci. 12087, 41--49 (2020; Zbl 1459.94117)]. The first proposed code-based cryptosystem was the celebrated scheme of \textit{R. J. McEliece} [DSN Progress Report. Technical report. Pasadena: Jet Propulsion Laboratory (1978)]. In it a message \(m\) of length \(k\)\, is ciphered as \(c=mG_{\mathrm{pub}}+e\) where \(G_{\mathrm{pub}}\)\, is a \(k\times n\)\, matrix, in fact a generating matrix of a Goppa code, disguised to look as the generating matrix of a general lineal code, and \(e\)\, a error vector with Hamming weigh less or equal that the correcting capability of the Goppa code. The IKKR cryptosystem (in fact two versions: the modified and the ungraded one) takes a different approach, introducing a new matrix \(E_{\mathrm{pub}}\)\, and allowing \(e\)\, to be of arbitrary weigh. The ciphering is now \(c=mG_{\mathrm{pub}}+eE_{\mathrm{pub}}\). An attack to the IKKR-PKE, the LCKN attack, was proposed by \textit{Y. Lee} et al. [IEEE Commun. Lett. 24, No. 12, 2678--2681 (2020; \url{doi:10.1109/LCOMM.2020.3019054})]. The first attack of the present paper is similar to it ``whilst our second attack is more efficient than the LCKN attack''. Section 2 provides the necessary details about error-correcting codes defined over a finite field \(\mathbb{F}_q\)\, and Section 3 summarizes the modified and the ungraded IKKR crytosystem. Section 4 reveals a weakness in the design of the IKKR scheme which is crucial in the two proposed plaintext recovery attacks.(Algorithms 2 and 3). The first algorithm has complexity \(n^4 + 2n^3+n^2\)\, operations in the underlying field \(\mathbb{F}_q\)\, while Algorithm 3 has complexity \(2n^3+k^4+k^3+k^2\)\, operations. Section 5 shows results of an implementation using Magma V2.20-5, see Table 3. These results show that ``we can recover the plaintext from a given ciphertext in less than 176 miliseconds''. Finally Section 6 proves the impossibility of repairing both versions of the IKKR scheme.