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 $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.
Metadata
- Available format(s)
-
PDF
- 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
- 2022-09-07: received
- See all versions
- Short URL
- https://ia.cr/2022/1166
- License
-
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}
}
