Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Designs, Codes and Cryptography 1/2022

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

Login to get access
share
SHARE

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.
go back to reference 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). 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).
3.
go back to reference Coggia D., Couvreur A.: On the security of a Loidreau rank metric code based encryption scheme. Des. Codes Crypt. 88(9), 1941–1957 (2020). MathSciNetCrossRef Coggia D., Couvreur A.: On the security of a Loidreau rank metric code based encryption scheme. Des. Codes Crypt. 88(9), 1941–1957 (2020). MathSciNetCrossRef
4.
go back to reference Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A 25(3), 226–241 (1978). MathSciNetCrossRef Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A 25(3), 226–241 (1978). MathSciNetCrossRef
6.
go back to reference 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) 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.
go back to reference Gabidulin E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985). MathSciNetMATH Gabidulin E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985). MathSciNetMATH
8.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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). MathSciNetCrossRef 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). MathSciNetCrossRef
11.
go back to reference Hirschfeld J.: Projective Geometries Over Finite Fields. Oxford University Press, Oxford (1998). MATH Hirschfeld J.: Projective Geometries Over Finite Fields. Oxford University Press, Oxford (1998). MATH
12.
go back to reference 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). 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.
go back to reference Loidreau P.: A Welch–Berlekamp like algorithm for decoding Gabidulin codes. In: Ytrehus Ø. (ed.) Coding Cryptogr., pp. 36–45. Springer, Berlin (2006). CrossRef Loidreau P.: A Welch–Berlekamp like algorithm for decoding Gabidulin codes. In: Ytrehus Ø. (ed.) Coding Cryptogr., pp. 36–45. Springer, Berlin (2006). CrossRef
14.
go back to reference Loidreau P.: A new rank metric codes based encryption scheme. In: International Workshop on Post-Quantum Cryptography, pp. 3–17. Springer (2017) Loidreau P.: A new rank metric codes based encryption scheme. In: International Workshop on Post-Quantum Cryptography, pp. 3–17. Springer (2017)
15.
go back to reference McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Progress Report pp. 42–44 (1978) McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Progress Report pp. 42–44 (1978)
16.
go back to reference Overbeck R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptol. 21(2), 280–301 (2008). MathSciNetCrossRef Overbeck R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptol. 21(2), 280–301 (2008). MathSciNetCrossRef
19.
go back to reference von zur Gathen J., Gerhard J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2013). CrossRef von zur Gathen J., Gerhard J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2013). CrossRef
20.
go back to reference von zur Gathen J., Kaltofen E.: Factorization of multivariate polynomials over finite fields. Math. Comput. 45(171), 251–261 (1985). MathSciNetCrossRef von zur Gathen J., Kaltofen E.: Factorization of multivariate polynomials over finite fields. Math. Comput. 45(171), 251–261 (1985). MathSciNetCrossRef
22.
go back to reference 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) 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)
Metadata
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

Other articles of this Issue 1/2022

Designs, Codes and Cryptography 1/2022 Go to the issue

Premium Partner