On the security of the modified Dual-ouroboros PKE using Gabidulin codes

Recently, Kim et al. proposed a modified Dual-Ouroboros public-key encryption (\({\textsf{PKE}}\)) using Gabidulin codes to overcome the limitation of having decryption failure in the original Dual-Ouroboros using low rank parity check codes. This modified Dual-Ouroboros \({\textsf{PKE}}\) using Gabidulin codes is proved to be IND–CPA secure, with very compact public key size of 738 bytes achieving 128-bit security level. However, they did not specify on their choice of the secret key S used in their \({\textsf{PKE}}\). In this paper, we analyze different possible choices for S in the modified Dual-Ouroboros \({\textsf{PKE}}\) using Gabidulin codes. More specifically, we show that if S is invertible over \({\mathbb{F}}_{q^m}\) without any restriction, then the decryption algorithm will fail. Furthermore, we show that Kim et al.’s proposal of the modified Dual-Ouroboros \({\textsf{PKE}}\) using Gabidulin codes has secret key S over \({\mathbb{F}}_q\) for its decryption algorithm to be correct. Then, we proposed two attacks: key recovery attack and plaintext recovery attack on their \({\textsf{PKE}}\) with S over \({\mathbb{F}}_q\). We are able to recover the secret key for all the proposed parameters within 235 seconds. Moreover, we show that the public key matrix in their proposal generates a subcode of Gabidulin code. As a consequence, we can apply the Frobenius weak attack on their proposal and recover the plaintext for all the proposed paramters within 0.614 second. Finally, we give a proposal for the modified Dual-Ouroboros \({\textsf{PKE}}\) using Gabidulin codes such that it is correct and secure, by considering certain restrictions on S over \({\mathbb{F}}_{q^m}\).