main-content

Published in:

21-11-2021

Extending Coggia–Couvreur attack on Loidreau’s rank-metric cryptosystem

Author: Anirban Ghatak

Published in: Designs, Codes and Cryptography | Issue 1/2022

Abstract

A recent paper by Coggia and Couvreur presents a polynomial time key-recovery attack on Loidreau’s encryption scheme, based on rank-metric codes, for some parameters. Their attack was formulated for the particular case when the secret matrix in Loidreau’s scheme is restricted to a 2-dimensional subspace. We present an extension of the Coggia–Couvreur attack to deal with secret matrices chosen over subspaces of dimension greater than 2.
Footnotes
1
In the recent version of their paper [3], Coggia and Couvreur have indicated the form of the sum space to extend their argument for $$\lambda =2$$. We had independently arrived at a similar conclusion based on the original version of their paper ([2]) and have, moreover, presented the details of the proof for $$\lambda \ge 3$$.

2
The author is grateful to the anonymous reviewer for pointing this out.

Literature
1.
Blichfeldt H.F.: Finite Collineation Groups: With an Introduction to the Theory of Groups of Operators and Substitution Groups. University of Chicago Press, Chicago (1917).
2.
Coggia D., Couvreur A.: On the security of a Loidreau’s rank metric code based encryption scheme. http://​arxiv.​org/​abs/​1903.​02933 (2019)
3.
Coggia D., Couvreur A.: On the security of a Loidreau rank metric code based encryption scheme. Des. Codes Crypt. 88(9), 1941–1957 (2020).
4.
Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A 25(3), 226–241 (1978).
5.
Dvir Z.: On the size of Kakeya sets in finite fields. J. Am. Math. Soc. 22(4), 1093–1097 (2009).
6.
Faure C., Loidreau P.: A new public-key cryptosystem based on the problem of reconstructing p-polynomials. In: International Workshop on Coding and Cryptography, pp. 304–315. Springer (2005)
7.
Gabidulin E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985).
8.
Gabidulin E.M., Paramonov A., Tretjakov O.: Ideals over a non-commutative ring and their application in cryptology. In: Workshop on the Theory and Application of Cryptographic Techniques, pp. 482–489. Springer (1991)
9.
Gaborit P., Murat G., Ruatta O., Zémor G.: Low rank parity check codes and their application to cryptography. In: Proceedings of the Workshop on Coding and Cryptography WCC, vol. 2013 (2013)
10.
Gaborit P., Otmani A., Kalachi H.T.: Polynomial-time key recovery attack on the Faure–Loidreau scheme based on Gabidulin codes. Des. Codes Crypt. 86(7), 1391–1403 (2018).
11.
Hirschfeld J.: Projective Geometries Over Finite Fields. Oxford University Press, Oxford (1998). MATH
12.
Lidl R., Niederreiter H., Cohn P., Rota G., Doran B., Flajolet P., Ismail M., Lam T., Lutwak E.: Finite Fields. Cambridge University Press, Cambridge (1997).
13.
Loidreau P.: A Welch–Berlekamp like algorithm for decoding Gabidulin codes. In: Ytrehus Ø. (ed.) Coding Cryptogr., pp. 36–45. Springer, Berlin (2006). CrossRef
14.
Loidreau P.: A new rank metric codes based encryption scheme. In: International Workshop on Post-Quantum Cryptography, pp. 3–17. Springer (2017)
15.
McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Progress Report pp. 42–44 (1978)
16.
Overbeck R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptol. 21(2), 280–301 (2008).
17.
Puchinger S., Renner J., Wachter-Zeh A.: Twisted Gabidulin codes in the gpt cryptosystem. arXiv:​1806.​10055 (2018)
18.
Stein W., et al.: Sage Mathematics Software (Version 7.5.1). The Sage Development Team (2017). http://​www.​sagemath.​org
19.
von zur Gathen J., Gerhard J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2013). CrossRef
20.
von zur Gathen J., Kaltofen E.: Factorization of multivariate polynomials over finite fields. Math. Comput. 45(171), 251–261 (1985).
21.
Wachter-Zeh A., Afanassiev V.B., Sidorenko V.: Fast decoding of Gabidulin codes. Des. Codes Cryptogr. 66(1–3), 57–73 (2013). https://​doi.​org/​10.​1007/​s10623-012-9659-5.
22.
Wachter-Zeh A., Puchinger S., Renner J.: Repairing the faure-loidreau public-key cryptosystem. In: 2018 IEEE International Symposium on Information Theory (ISIT), pp. 2426–2430. IEEE (2018)
Title
Extending Coggia–Couvreur attack on Loidreau’s rank-metric cryptosystem
Author
Anirban Ghatak
Publication date
21-11-2021
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 1/2022
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-00972-7

Go to the issue