Top

Published in:

2017 | OriginalPaper | Chapter

Gabidulin Matrix Codes and Their Application to Small Ciphertext Size Cryptosystems

Authors : Thierry P. Berger, Philippe Gaborit, Olivier Ruatta

Published in: Progress in Cryptology – INDOCRYPT 2017

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper we propose a new method to hide the structure of Gabidulin codes for cryptographic applications. At the difference of previous cryptosystems based on Gabidulin codes, we do not try to mask the structure of Gabidulin codes by the use of some distortion methods, but we consider matrix codes obtained from subcodes of binary images of Gabidulin codes. This allows us to remove the properties related to multiplication in the extension field. In particular, this prevents the use of Frobenius for cryptanalysis. Thus, Overbeck’s attack can no longer be applied. In practice we obtain public key with a gain of a factor of order ten compared to the classical Goppa-McEliece scheme with still a small cipher text of order only 1 kbits, better than recent cryptosystems for which the cipher text size is of order 10 kbits. Several results used and proved in the paper are of independent interest: results on structural properties of Gabidulin matrix codes and hardness of deciding whether a code is equivalent to a subcode of a matrix code.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Field Lifting for Smaller UOV Public Keys

next chapter Lightweight Design Choices for LED-like Block Ciphers

Aguilar Melchor, C., Blazy, O., Deneuville, J.-C., Gaborit, P., Zémor, G.: Efficient encryption from random quasi-cyclic codes. CoRR abs/1612.05572 (2016). http://arxiv.org/abs/1612.05572

Alekhnovich, M.: More on average case vs approximation complexity. In: Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), Cambridge, MA, USA, 11–14 October 2003, pp. 298–307 (2003)

Berger, T.P.: Isometries for rank distance and permutation group of Gabidulin codes. IEEE Trans. Inf. Theory 49(11), 3016–3019 (2003)MathSciNetCrossRefMATH

Berger, T.P., El Amrani, N.: Codes over \(\cal{L}(GF(2)^m,GF(2)^m)\), MDS diffusion matrices and cryptographic applications. In: El Hajji, S., Nitaj, A., Carlet, C., Souidi, E.M. (eds.) C2SI 2015. LNCS, vol. 9084, pp. 197–214. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-18681-8_16

Berger, T.P., Cayrel, P.-L., Gaborit, P., Otmani, A.: Reducing key length of the McEliece cryptosystem. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 77–97. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02384-2_6 CrossRef

Berger, T.P., Gueye, C.T., Klamti, J.B.: A NP-complete problem in coding theory with application to code based cryptography. In: El Hajji, S., Nitaj, A., Souidi, E.M. (eds.) C2SI 2017. LNCS, vol. 10194, pp. 230–237. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55589-8_15 CrossRef

Berger, T.P., Loidreau, P.: Designing an efficient and secure public-key cryptosystem based on reducible rank codes. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 218–229. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30556-9_18 CrossRef

Bogart, K.P., Goldberg, D., Gordon, J.: An elementary proof of the MacWilliams theorem on equivalence of codes. Inf. Control 37, 19–22 (1978)MathSciNetCrossRefMATH

Couvreur, A., Gaborit, P., Gauthier-Umaña, V., Otmani, A., Tillich, J.-P.: Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes. Des. Codes Cryptogr. 73(2), 641–666 (2014)MathSciNetCrossRefMATH

10.

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

11.

Faugère, J.-C., Safey El Din, M., Spaenlehauer, P.-J.: Gröbner bases of Bihomogeneous ideals generated by polynomials of bidegree (1,1): algorithms and complexity. J. Symb. Comput. 46(4), 406–437 (2011)CrossRefMATH

12.

Gabidulin, E.M.: Theory of codes with maximum rank distance. Probl. Inf. Transm. (English translation of Problemy Peredachi Informatsii) 21(1), 1–71 (1985)MathSciNetMATH

13.

Gabidulin, E.M., Paramonov, A.V., Tretjakov, O.V.: Ideals over a non-commutative ring and their application in cryptology. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 482–489. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_41

14.

Gabidulin, E., Rashwan, H., Honary, B.: On improving security of GPT cryptosystems. In: 2009 IEEE International Symposium on Information Theory Proceedings (ISIT), ISIT 2009, pp. 1110–1114 (2009)

15.

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 2013, Bergen, Norway (2013). www.selmer.uib.no/WCC2013/pdfs/Gaborit.pdf

16.

Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inf. Theory 62(2), 1006–1019 (2016)MathSciNetCrossRefMATH

17.

Huffman, W.C.: Groups and codes. In: Pless, V.S., Huffman, W.C. (eds.) Handbook of Coding Theory. Elsevier, Amsterdam (1998). Chap. 17

18.

Loidreau, P.: A new rank metric codes based encryption scheme. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 3–17. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_1 CrossRef

19.

MacWilliams F.J.: Combinatorial properties of elementary Abelian groups Ph.D. thesis, Radcliffe College (1962)

20.

McEliece, R.: A public-key cryptosystem based on algebraic coding theory. In: DSN Program Report, Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA, pp. 114–116, January 1978

21.

Misoczki, R., Barreto, P.S.L.M.: Compact McEliece keys from Goppa codes. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 376–392. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-05445-7_24 CrossRef

22.

Misoczki, R., Tillich, J.P., Sendrier, N., Barreto, P.S.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes. In: IEEE International Symposium on Information Theory, ISIT 2013, pp. 2069–2073. IEEE (2013)

23.

Otmani, A., Kalachi, H.T., Ndjeya, S.: Improved cryptanalysis of rank metric schemes based on Gabidulin codes. CoRR abs/1602.08549 (2016)

24.

Overbeck, R.: A new structural attack for GPT and variants. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 50–63. Springer, Heidelberg (2005). https://doi.org/10.1007/11554868_5 CrossRef

25.

Overbeck, R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptol. 21(2), 280–301 (2008)MathSciNetCrossRefMATH

26.

Rashwan, H., Honary, B., Gabidulin, E.M.: On improving security of GPT cryptosystems. In: IEEE International Symposium on Information Theory, ISIT 2009, pp. 1110–1114. IEEE (2009)

27.

Roth, R.M.: Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Inf. Theory 37(2), 328–336 (1991)MathSciNetCrossRefMATH

Title: Gabidulin Matrix Codes and Their Application to Small Ciphertext Size Cryptosystems
Authors: Thierry P. Berger
Philippe Gaborit
Olivier Ruatta
Publisher: Springer International Publishing
Book: Progress in Cryptology – INDOCRYPT 2017
Print ISBN: 978-3-319-71666-4

Electronic ISBN: 978-3-319-71667-1

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-71667-1_13

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner