### 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 $GM^{-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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Post-quantum cryptography Code-based cryptography Gabidulin codes Partial cyclic codes Linearized transformations
Contact author(s)
ws_guo @ mail nankai edu cn
fwfu @ nankai edu cn
History
2022-09-07: approved
See all versions
Short URL
https://ia.cr/2022/1166

CC BY

BibTeX

@misc{cryptoeprint:2022/1166,
author = {Wenshuo Guo and Fang-Wei Fu},
title = {McEliece-type encryption based on Gabidulin codes with no hidden structure},
howpublished = {Cryptology ePrint Archive, Paper 2022/1166},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1166}},
url = {https://eprint.iacr.org/2022/1166}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.