Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 2/2018

28-04-2017

Extension of Overbeck’s attack for Gabidulin-based cryptosystems

Authors: Anna-Lena Horlemann-Trautmann, Kyle Marshall, Joachim Rosenthal

Published in: Designs, Codes and Cryptography | Issue 2/2018

Login to get access

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

search-config
loading …

Abstract

Cryptosystems based on codes in the rank metric were introduced in 1991 by Gabidulin, Paramanov, and Tretjakov (GPT) and have been studied as a promising alternative to cryptosystems based on codes in the Hamming metric. In particular, it was observed that the combinatorial solution for solving the rank analogy of the syndrome decoding problem appears significantly harder. Early proposals were often made with an underlying Gabidulin code structure. Gibson, in 1995, made a promising attack which was later extended by Overbeck in 2008 to cryptanalyze many of the systems in the literature. Improved systems were then designed to resist the attack of Overbeck and yet continue to use Gabidulin codes. In this paper, we generalize Overbeck’s attack to break the GPT cryptosystem for all possible parameter sets, and then extend the attack to cryptanalyze particular variants which explicitly resist the attack of Overbeck.
previous article Concatenation of convolutional codes and rank metric codes for multi-shot network coding
next article On the genericity of maximum rank distance and Gabidulin codes
Footnotes
1
The attack needs \(O(k^2nm^2 (s^2+k))\) operations over \(\mathbb {F}_q\), plus the operations needed for the Gabidulin code decoding algorithm. E.g., the decoding algorithm of [23] needs \(O(m^3 \log m)\) operations over \(\mathbb {F}_q\).
 
2
The attack needs \(O(k^2nm^2 (\hat{t}^2+k))\) operations over \(\mathbb {F}_q\), plus the operations needed for the Gabidulin code decoding algorithm.
 
Literature
1.
Berger T.P.: Isometries for rank distance and permutation group of Gabidulin codes. IEEE Trans. Inf. Theory 49(11), 3016–3019 (2003).MathSciNetCrossRefMATH
2.
Chabaud F., Stern J.: The cryptographic security of the syndrome decoding problem for rank distance codes. In: Advances in Cryptology—ASIACRYPT ’96, International Conference on the Theory and Applications of Cryptology and Information Security, Kyongju, Korea, November 3–7, 1996, Proceedings, pp. 368–381 (1996).
3.
Gabidulin E.M.: Theory of codes with maximum rank distance. Probl. Pereda. Inform. 21(1), 3–16 (1985).MathSciNetMATH
4.
5.
Gabidulin E.M., Paramonov A.V., Tretjakov O.V.: Ideals over a non-commutative ring and their application in cryptology. In: Proceedings of the 10th Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT’91, pp. 482–489. Springer, Berlin (1991).
6.
Gabidulin E.M., Rashwan H., Honary B.: On improving security of GPT cryptosystems. In: IEEE International Symposium on Information Theory, 2009 (ISIT 2009), pp. 1110–1114 (2009).
7.
Gaborit P., Ruatta O., Schrek J., Zémor G.: New results for rank-based cryptography. In: Progress in Cryptology—AFRICACRYPT 2014—7th International Conference on Cryptology in Africa, Marrakesh, Morocco, May 28–30, 2014, Proceedings, pp. 1–12 (2014).
8.
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
9.
Gibson J.K.: Severely denting the Gabidulin version of the McEliece public key cryptosystem. Des. Codes Cryptogr. 6(1), 37–45 (1995).MathSciNetCrossRefMATH
10.
11.
Horlemann-Trautmann A.-L., Marshall K.: New criteria for MRD and Gabidulin codes and some rank-metric code constructions. arXiv:​1507.​08641 (2015).
12.
Horlemann-Trautmann A.-L., Marshall K., Rosenthal J.: Considerations for rank-based cryptosystems. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT 2016), Barcelona, pp. 2544–2548 (2016).
13.
Kshevetskiy A.: Security of GPT-like public-key cryptosystems based on linear rank codes. In: 3rd International Workshop on Signal Design and Its Applications in Communications, 2007 (IWSDA 2007), pp. 143–147 (2007).
14.
Loidreau P.: Designing a rank metric based McEliece cryptosystem. In: Proceedings of the Third International Conference on Post-Quantum Cryptography (PQCrypto’10), pp. 142–152. Springer, Berlin (2010).
15.
McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. Deep Space Netw. Progr. Rep. 44, 114–116 (1978).
16.
Morrison K.: Equivalence for rank-metric and matrix codes and automorphism groups of Gabidulin codes. IEEE Trans. Inf. Theory 60(11), 1–12 (2014).MathSciNetCrossRefMATH
17.
Ourivski A.V., Johansson T.: New technique for decoding codes in the rank metric and its cryptography applications. Probl. Inf. Transm. 38(3), 237–246 (2002).MathSciNetCrossRefMATH
18.
19.
Rashwan H., Gabidulin E.M., Honary B.: A smart approach for GPT cryptosystem based on rank codes. In: IEEE International Symposium on Information Theory, ISIT 2010, June 13–18, 2010, Austin, Texas, USA, Proceedings, pp. 2463–2467 (2010).
20.
Sidelnikov V.M., Shestakov S.O.: On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Math. Appl. 2, 439–444 (1992).MathSciNet
21.
Silva D., Kschischang F.R.: Fast encoding and decoding of Gabidulin codes. In: IEEE International Symposium on Information Theory, 2009 (ISIT 2009), pp. 2858–2862 (2009).
22.
23.
24.
Wan Z.-X.: Geometry of matrices. World Scientific, Singapore (1996). In memory of Professor L.K. Hua (1910–1985).
Metadata
Title
Extension of Overbeck’s attack for Gabidulin-based cryptosystems
Authors
Anna-Lena Horlemann-Trautmann
Kyle Marshall
Joachim Rosenthal
Publication date
28-04-2017
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 2/2018
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-017-0343-7

Other articles of this Issue 2/2018

Designs, Codes and Cryptography 2/2018 Go to the issue

OriginalPaper

A new series of large sets of subspace designs over the binary field

OriginalPaper

Concatenation of convolutional codes and rank metric codes for multi-shot network coding

OriginalPaper

Coding for locality in reconstructing permutations

OriginalPaper

Anticode-based locally repairable codes with high availability

EditorialNotes

Preface to the special issue on network coding and designs

OriginalPaper

The order of the automorphism group of a binary -analog of the Fano plane is at most two

Premium Partner

    Image Credits