[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

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

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Similar content being viewed by others

Notes

  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.

References

  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).

    Google Scholar 

  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).

    Article  MathSciNet  Google Scholar 

  4. Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A 25(3), 226–241 (1978).

    Article  MathSciNet  Google Scholar 

  5. Dvir Z.: On the size of Kakeya sets in finite fields. J. Am. Math. Soc. 22(4), 1093–1097 (2009).

    Article  MathSciNet  Google Scholar 

  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).

    MathSciNet  MATH  Google Scholar 

  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).

    Article  MathSciNet  Google Scholar 

  11. Hirschfeld J.: Projective Geometries Over Finite Fields. Oxford University Press, Oxford (1998).

    MATH  Google Scholar 

  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).

    Google Scholar 

  13. Loidreau P.: A Welch–Berlekamp like algorithm for decoding Gabidulin codes. In: Ytrehus Ø. (ed.) Coding Cryptogr., pp. 36–45. Springer, Berlin (2006).

    Chapter  Google Scholar 

  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).

    Article  MathSciNet  Google Scholar 

  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).

    Book  Google Scholar 

  20. von zur Gathen J., Kaltofen E.: Factorization of multivariate polynomials over finite fields. Math. Comput. 45(171), 251–261 (1985).

    Article  MathSciNet  Google Scholar 

  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.

    Article  MathSciNet  MATH  Google Scholar 

  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)

Download references

Acknowledgements

The author is deeply grateful to the anonymous referees whose comments have substantially improved both the content and presentation. In addition, the author would like to thank Arnab Chakraborty, Mridul Nandi and Anupam Chattopadhyay for several helpful discussions. Anupam’s assistance in running the simulations is gratefully acknowledged.

Author information

Authors and Affiliations

Authors

Additional information

Communicated by M. Lavrauw.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ghatak, A. Extending Coggia–Couvreur attack on Loidreau’s rank-metric cryptosystem. Des. Codes Cryptogr. 90, 215–238 (2022). https://doi.org/10.1007/s10623-021-00972-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-021-00972-7

Keywords

Mathematics Subject Classification

Navigation