Paper 2022/1166

McEliece-type encryption based on Gabidulin codes with no hidden structure

Abstract

This paper presents a new McEliece-type encryption scheme based on Gabidulin codes, which uses linearized transformations to disguise the private key. When endowing this scheme with the partial cyclic structure, we obtain a public key of the form $G{M}^{-1}$, where $G$ is a partial circulant generator matrix of Gabidulin code and $M$ as well as $M^{-1}$ is a circulant matrix of large rank weight, even as large as the code length. Another difference from Loidreau's proposal at PQCrypto 2017 is that both $G$ and $M$ are publicly known. Recovering the private key can be reduced to deriving from $M$ a linearized transformation and two circulant matrices of small rank weight. This new scheme is shown to resist all the known distinguisher-based attacks, such as the Overbeck attack and Coggia-Couvreur attack, and also has a very small public key size. For instance, 2592 bytes are enough for our proposal to achieve the security of 256 bits, which is 400 times smaller than Classic McEliece that has been selected into the fourth round of the NIST Post-Quantum Cryptography (PQC) standardization process.