August  2017, 11(3): 533-548. doi: 10.3934/amc.2017042

New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions

1. 

Faculty of Mathematics and Statistics, University of St. Gallen, St. Gallen, Switzerland

2. 

Institute of Mathematics, University of Zurich, Zurich, Switzerland

Received  September 2015 Revised  November 2016 Published  August 2017

Fund Project: The authors were partially supported by SNF grant no. 149716

It is well-known that maximum rank distance (MRD) codes can be constructed as generalized Gabidulin codes. However, it was unknown until recently whether other constructions of linear MRD codes exist. In this paper, we derive a new criterion for linear MRD codes as well as an algebraic criterion for testing whether a given linear MRD code is a generalized Gabidulin code. We then use the criteria to construct examples of linear MRD codes which are not generalized Gabidulin codes.

Citation: Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042
References:
[1]

T. P. Berger, Isometries for rank distance and permutation group of Gabidulin codes, IEEE Trans. Inf. Theory, 49 (2003), 3016-3019. doi: 10.1109/TIT.2003.819322. Google Scholar

[2]

A. CossidenteG. Marino and F. Pavese, Non-linear maximum rank distance codes, Des. Codes Crypt., 79 (2016), 597-609. doi: 10.1007/s10623-015-0108-0. Google Scholar

[3]

J. de la CruzM. KiermaierA. Wassermann and W. Willems, Algebraic structures of MRD codes, Adv. Math. Commun., 10 (2016), 499-510. doi: 10.3934/amc.2016021. Google Scholar

[4]

P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A, 25 (1978), 226-241. doi: 10.1016/0097-3165(78)90015-8. Google Scholar

[5]

E. M. Gabidulin, Theory of codes with maximum rank distance, Probl. Peredachi Inf., 21 (1985), 3-16. Google Scholar

[6]

E. M. Gabidulin, A. V. Paramonov and O. V. Tretjakov, Ideals over a non-commutative ring and their application in cryptology, in Proc. 10th Ann. Int. Conf. Theory Appl. Crypt. Techn. EUROCRYPT'91, Springer-Verlag, Berlin, 1991,482–489. doi: 10.1007/3-540-46416-6_41. Google Scholar

[7]

M. Giorgetti and A. Previtali, Galois invariance, trace codes and subfield subcodes, Finite Fields Appl., 16 (2010), 96-99. doi: 10.1016/j.ffa.2010.01.002. Google Scholar

[8]

A. Horlemann-Trautmann, K. Marshall and J. Rosenthal, Extension of Overbeck's attack for Gabidulin based cryptosystems Des. Codes Crypt. published online, 2017. doi: 10.1007/s10623-017-0343-7. Google Scholar

[9]

A. Kshevetskiy and E. Gabidulin, The new construction of rank codes, in Proc. Int. Symp. Inf. Theory (ISIT), 2005,2105–2108.Google Scholar

[10]

R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications Cambridge Univ. Press, Cambridge, 1994. doi: 10.1017/CBO9781139172769. Google Scholar

[11]

P. Loidreau, Designing a rank metric based McEliece cryptosystem, in Proc. 3rd Int. Conf. Post-Quantum Crypt. PQCrypto'10, Springer-Verlag, Berlin, 2010,142–152. doi: 10.1007/978-3-642-12929-2_11. Google Scholar

[12]

K. Morrison, Equivalence for rank-metric and matrix codes and automorphism groups of Gabidulin codes, IEEE Trans. Inf. Theory, 60 (2014), 7035-7046. doi: 10.1109/TIT.2014.2359198. Google Scholar

[13]

J. Sheekey, A new family of linear maximum rank distance codes, Adv. Math. Commun., 10 (2016), 475-488. doi: 10.3934/amc.2016019. Google Scholar

[14]

Z. -X. Wan, Geometry of Matrices World Scient. , Singapore, 1996.Google Scholar

show all references

References:
[1]

T. P. Berger, Isometries for rank distance and permutation group of Gabidulin codes, IEEE Trans. Inf. Theory, 49 (2003), 3016-3019. doi: 10.1109/TIT.2003.819322. Google Scholar

[2]

A. CossidenteG. Marino and F. Pavese, Non-linear maximum rank distance codes, Des. Codes Crypt., 79 (2016), 597-609. doi: 10.1007/s10623-015-0108-0. Google Scholar

[3]

J. de la CruzM. KiermaierA. Wassermann and W. Willems, Algebraic structures of MRD codes, Adv. Math. Commun., 10 (2016), 499-510. doi: 10.3934/amc.2016021. Google Scholar

[4]

P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A, 25 (1978), 226-241. doi: 10.1016/0097-3165(78)90015-8. Google Scholar

[5]

E. M. Gabidulin, Theory of codes with maximum rank distance, Probl. Peredachi Inf., 21 (1985), 3-16. Google Scholar

[6]

E. M. Gabidulin, A. V. Paramonov and O. V. Tretjakov, Ideals over a non-commutative ring and their application in cryptology, in Proc. 10th Ann. Int. Conf. Theory Appl. Crypt. Techn. EUROCRYPT'91, Springer-Verlag, Berlin, 1991,482–489. doi: 10.1007/3-540-46416-6_41. Google Scholar

[7]

M. Giorgetti and A. Previtali, Galois invariance, trace codes and subfield subcodes, Finite Fields Appl., 16 (2010), 96-99. doi: 10.1016/j.ffa.2010.01.002. Google Scholar

[8]

A. Horlemann-Trautmann, K. Marshall and J. Rosenthal, Extension of Overbeck's attack for Gabidulin based cryptosystems Des. Codes Crypt. published online, 2017. doi: 10.1007/s10623-017-0343-7. Google Scholar

[9]

A. Kshevetskiy and E. Gabidulin, The new construction of rank codes, in Proc. Int. Symp. Inf. Theory (ISIT), 2005,2105–2108.Google Scholar

[10]

R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications Cambridge Univ. Press, Cambridge, 1994. doi: 10.1017/CBO9781139172769. Google Scholar

[11]

P. Loidreau, Designing a rank metric based McEliece cryptosystem, in Proc. 3rd Int. Conf. Post-Quantum Crypt. PQCrypto'10, Springer-Verlag, Berlin, 2010,142–152. doi: 10.1007/978-3-642-12929-2_11. Google Scholar

[12]

K. Morrison, Equivalence for rank-metric and matrix codes and automorphism groups of Gabidulin codes, IEEE Trans. Inf. Theory, 60 (2014), 7035-7046. doi: 10.1109/TIT.2014.2359198. Google Scholar

[13]

J. Sheekey, A new family of linear maximum rank distance codes, Adv. Math. Commun., 10 (2016), 475-488. doi: 10.3934/amc.2016019. Google Scholar

[14]

Z. -X. Wan, Geometry of Matrices World Scient. , Singapore, 1996.Google Scholar

[1]

Javier de la Cruz, Michael Kiermaier, Alfred Wassermann, Wolfgang Willems. Algebraic structures of MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 499-510. doi: 10.3934/amc.2016021

[2]

Gabriele Nebe, Wolfgang Willems. On self-dual MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 633-642. doi: 10.3934/amc.2016031

[3]

Kamil Otal, Ferruh Özbudak. Explicit constructions of some non-Gabidulin linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 589-600. doi: 10.3934/amc.2016028

[4]

Ernst M. Gabidulin, Pierre Loidreau. Properties of subspace subcodes of Gabidulin codes. Advances in Mathematics of Communications, 2008, 2 (2) : 147-157. doi: 10.3934/amc.2008.2.147

[5]

Kamil Otal, Ferruh Özbudak, Wolfgang Willems. Self-duality of generalized twisted Gabidulin codes. Advances in Mathematics of Communications, 2018, 12 (4) : 707-721. doi: 10.3934/amc.2018042

[6]

Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225

[7]

Liren Lin, Hongwei Liu, Bocong Chen. Existence conditions for self-orthogonal negacyclic codes over finite fields. Advances in Mathematics of Communications, 2015, 9 (1) : 1-7. doi: 10.3934/amc.2015.9.1

[8]

David Grant, Mahesh K. Varanasi. Duality theory for space-time codes over finite fields. Advances in Mathematics of Communications, 2008, 2 (1) : 35-54. doi: 10.3934/amc.2008.2.35

[9]

Fatma-Zohra Benahmed, Kenza Guenda, Aicha Batoul, Thomas Aaron Gulliver. Some new constructions of isodual and LCD codes over finite fields. Advances in Mathematics of Communications, 2019, 13 (2) : 281-296. doi: 10.3934/amc.2019019

[10]

Umberto Martínez-Peñas. Rank equivalent and rank degenerate skew cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 267-282. doi: 10.3934/amc.2017018

[11]

David Grant, Mahesh K. Varanasi. The equivalence of space-time codes and codes defined over finite fields and Galois rings. Advances in Mathematics of Communications, 2008, 2 (2) : 131-145. doi: 10.3934/amc.2008.2.131

[12]

Xia Li, Feng Cheng, Chunming Tang, Zhengchun Zhou. Some classes of LCD codes and self-orthogonal codes over finite fields. Advances in Mathematics of Communications, 2019, 13 (2) : 267-280. doi: 10.3934/amc.2019018

[13]

Susanne Pumplün. Finite nonassociative algebras obtained from skew polynomials and possible applications to (f, σ, δ)-codes. Advances in Mathematics of Communications, 2017, 11 (3) : 615-634. doi: 10.3934/amc.2017046

[14]

Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87

[15]

Jean-François Biasse, Michael J. Jacobson, Jr.. Smoothness testing of polynomials over finite fields. Advances in Mathematics of Communications, 2014, 8 (4) : 459-477. doi: 10.3934/amc.2014.8.459

[16]

John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019

[17]

Amita Sahni, Poonam Trama Sehgal. Enumeration of self-dual and self-orthogonal negacyclic codes over finite fields. Advances in Mathematics of Communications, 2015, 9 (4) : 437-447. doi: 10.3934/amc.2015.9.437

[18]

Ekkasit Sangwisut, Somphong Jitman, Patanee Udomkavanich. Constacyclic and quasi-twisted Hermitian self-dual codes over finite fields. Advances in Mathematics of Communications, 2017, 11 (3) : 595-613. doi: 10.3934/amc.2017045

[19]

Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010

[20]

Lars Eirik Danielsen. Graph-based classification of self-dual additive codes over finite fields. Advances in Mathematics of Communications, 2009, 3 (4) : 329-348. doi: 10.3934/amc.2009.3.329

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (24)
  • HTML views (17)
  • Cited by (4)

Other articles
by authors

[Back to Top]