nach oben

Designs, Codes and Cryptography

Erschienen in:

21.11.2021

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

verfasst von: Anirban Ghatak

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1/2022

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Pseudo-embeddings and quadratic sets of quadrics

Nächster Artikel LWE from non-commutative group rings

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

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

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

Coggia D., Couvreur A.: On the security of a Loidreau’s rank metric code based encryption scheme. http://arxiv.org/abs/1903.02933 (2019)

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

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

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

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)

Gabidulin E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985).MathSciNetMATH

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)

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

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

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

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

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)

Titel: Extending Coggia–Couvreur attack on Loidreau’s rank-metric cryptosystem
verfasst von: Anirban Ghatak
Publikationsdatum: 21.11.2021
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1/2022
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-021-00972-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1/2022

Improved lower bound for locating-dominating codes in binary Hamming spaces

Improving the Gaudry–Schost algorithm for multidimensional discrete logarithms

Pseudo-embeddings and quadratic sets of quadrics

An improvement of the Diffie–Hellman noncommutative protocol

Weight distributions and weight hierarchies of a family of p-ary linear codes

SAND: an AND-RX Feistel lightweight block cipher supporting S-box-based security evaluations