On the security of a Loidreau rank metric code based encryption scheme
- PDF / 345,514 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 200 Views
On the security of a Loidreau rank metric code based encryption scheme Daniel Coggia1,2 · Alain Couvreur3,4 Received: 31 August 2019 / Revised: 19 May 2020 / Accepted: 17 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We present a polynomial time attack of a rank metric code based encryption scheme due to Loidreau for some parameters. Keywords Rank metric codes · Gabidulin codes · Code based cryptography · Cryptanalysis Mathematics Subject Classification 11T71 · 94B99
1 Introduction To instantiate a McEliece encryption scheme, one needs a family of codes with random looking generator matrices and an efficient decoding algorithm. While the original proposal due to McEliece himself [14] relies on classical Goppa codes endowed with the Hamming metric, one can actually consider codes endowed with any other metric. The use of Fq m – linear rank metric codes, first suggested by Gabidulin et al. [10] is of particular interest, since the Fq m –linearity permits a very “compact” representation of the code and hence permits to design a public key encryption scheme with rather short keys compared to the original McEliece proposal. Compared to the Hamming metric world, only a few families of codes with efficient decoding algorithms are known in rank metric. Basically, the McEliece scheme has been
This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography 2019”.
B
Alain Couvreur [email protected] Daniel Coggia [email protected]
1
DGA, 60, bd du Général Martial Valin, CS21623 - 75509 Paris cedex 15, France
2
Inria de Paris, 2 rue Simone Iff, CS 42112 75589, Paris CEDEX 12, France
3
Inria Saclay - Île-de-France, 1 rue Honoré d’Estienne d’Orves, Bâtiment Alan Turing, Campus de l’École polytechnique, 91120 Palaiseau, France
4
LIX, UMR 7161, École Polytechnique, 91120 Palaiseau, France
123
D. Coggia, A. Couvreur
instantiated with two general families of rank metric codes, namely Gabidulin codes [7,9] and LRPC codes [11]. In [13], Loidreau proposed the use of codes which can in some sense be regarded as an intermediary version between Gabidulin codes and LRPC codes. These codes are obtained by right multiplying a Gabidulin code with an invertible matrix whose entries are in Fq m and span an Fq –subspace of small dimension λ. This approach can be regarded as a “rank metric” counterpart of the BBCRS scheme [1] in Hamming metric. In the present article, we explain why the case λ = 2 and dim Cpub ≥ n/2 is weak and describe a polynomial time key recovery attack in this situation. Note The material of the present article has been communicated to Pierre Loidreau in April 2016. The article [13] is subsequent to this discussion and proposes parameters which avoid the attack described in the present article.
2 Prerequisites 2.1 Rank metric codes In this article m, n denote positive integers and q a prime power. A code of dimension k is an Fq m –subspace of Fqn m whose dimension as an Fq m –vector space
Data Loading...
