doi: 10.3934/amc.2022034
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Constructions of optimal rank-metric codes from automorphisms of rational function fields

1. 

UiT - The Arctic University of Norway, Tromsø, Norway

2. 

Florida Atlantic University, Florida, USA

* Corresponding author: Tovohery Hajatiana Randrianarisoa

Received  August 2021 Revised  February 2022 Early access April 2022

Fund Project: This work was supported by the University Grant Commission, Govt. of India (Sr. No. 2061641156), the Research Council of Norway grant No. 280731 and the Swiss SNF grant No. 181446

We define a class of automorphisms of rational function fields of finite characteristic and employ these to construct different types of optimal linear rank-metric codes. The first construction is of generalized Gabidulin codes over rational function fields. Reducing these codes over finite fields, we obtain maximum rank distance (MRD) codes which are not equivalent to generalized twisted Gabidulin codes. We also construct optimal Ferrers diagram rank-metric codes which settles further a conjecture by Etzion and Silberstein.

Citation: Rakhi Pratihar, Tovohery Hajatiana Randrianarisoa. Constructions of optimal rank-metric codes from automorphisms of rational function fields. Advances in Mathematics of Communications, doi: 10.3934/amc.2022034
References:
[1]

RQC, Accessed: June, 14th 2021. Available from: https://pqc-rqc.org/.

[2]

C. Aguilar-MelchorO. BlazyJ.-C. DeneuvilleP. Gaborit and G. Zémor, Efficient encryption from random quasi-cyclic codes, IEEE Trans. Inf. Theory, 64 (2018), 3927-3943.  doi: 10.1109/TIT.2018.2804444.

[3]

J. Antrobus and H. Gluesing-Luerssen, Maximal Ferrers diagram codes: Constructions and genericity considerations, IEEE Trans. Inform. Theory, 65 (2019), 6204-6223.  doi: 10.1109/TIT.2019.2926256.

[4]

N. AragonP. GaboritA. HautevilleO. Ruatta and G. Zémor, Low rank parity check codes: New decoding algorithms and applications to cryptography, IEEE Trans. Inform. Theory, 65 (2019), 7697-7717.  doi: 10.1109/TIT.2019.2933535.

[5]

D. AugotP. Loidreau and G. Robert, Generalized Gabidulin codes over fields of any characteristic, Des. Codes Cryptogr., 86 (2018), 1807-1848.  doi: 10.1007/s10623-017-0425-6.

[6]

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

[7]

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

[8]

H. El Gamal and A. R. Hammons, On the design of algebraic space-time codes for MIMO block-fading channels, IEEE Trans. Inform. Theory, 49 (2003), 151-163.  doi: 10.1109/TIT.2002.806116.

[9]

T. EtzionE. GorlaA. Ravagnani and A. Wachter-Zeh, Optimal Ferrers diagram rank-metric codes, IEEE Trans. Inform. Theory, 62 (2016), 1616-1630.  doi: 10.1109/TIT.2016.2522971.

[10]

T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inform. Theory, 55 (2009), 2909-2919.  doi: 10.1109/TIT.2009.2021376.

[11]

È. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21 (1985), 3-16. 

[12]

È. M. Gabidulin and A. Kshevetskiy, The new construction of rank codes, Proceedings, Int. Symp. Inf. Theory, (2005), 2105–2108.

[13]

È. M. Gabidulin, A. V. Paramonov and O. V. Tretjakov, Ideals over a non-commutative ring and their application in cryptology, Advances in Cryptology — EUROCRYPT '91, Springer Berlin Heidelberg, (1991), 482–489. doi: 10.1007/3-540-46416-6_41.

[14]

L. Giuzzi and F. Zullo, Identifiers for MRD-codes, Linear Algebra Appl., 575 (2019), 66-86.  doi: 10.1016/j.laa.2019.03.030.

[15]

E. Gorla and A. Ravagnani, Subspace codes from Ferrers diagrams, J. Algebra Appl., 16 (2017), 1750131, 23 pp. doi: 10.1142/S0219498817501316.

[16]

A.-L. Horlemann-Trautmann and K. Marshall, New criteria for MRD and Gabidulin codes and some rank-metric code constructions, Adv. Math. Commun., 11 (2017), 533-548.  doi: 10.3934/amc.2017042.

[17]

S. LiuY. Chang and T. Feng, Constructions for optimal Ferrers diagram rank-metric codes, IEEE Trans. Inform. Theory, 65 (2019), 4115-4130.  doi: 10.1109/TIT.2019.2894401.

[18]

G. LunardonR. Trombetti and Y. Zhou, Generalized twisted Gabidulin codes, J. Combin. Theory Ser. A, 159 (2018), 79-106.  doi: 10.1016/j.jcta.2018.05.004.

[19]

R. MahmoodA. Badr and A. Khisti, Convolutional codes with maximum column sum rank for network streaming, IEEE Trans. Inform. Theory, 62 (2016), 3039-3052.  doi: 10.1109/TIT.2016.2555949.

[20]

U. Martínez-Peñas, Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring, J. Algebra, 504 (2018), 587-612.  doi: 10.1016/j.jalgebra.2018.02.005.

[21]

U. Martínez-Peñas, Theory of supports for linear codes endowed with the sum-rank metric, Des. Codes Cryptogr., 87 (2019), 2295-2320.  doi: 10.1007/s10623-019-00619-8.

[22]

U. Martínez-Peñas and F. R. Kschischang, Reliable and secure multishot network coding using linearized Reed-Solomon codes, IEEE Trans. Inf. Theory, 65 (2019), 4785-4803.  doi: 10.1109/TIT.2019.2912165.

[23]

U. Martínez-Peñas and F. R. Kschischang, Universal and dynamic locally repairable codes with maximal recoverability via sum-rank codes, IEEE Trans. Inf. Theory, 65 (2019), 7790-7805.  doi: 10.1109/TIT.2019.2924888.

[24]

R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, Deep Space Network Progress Report, 44 (1978), 114-116. 

[25]

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.

[26]

D. Napp, R. Pinto, J. Rosenthal and P. Vettori, MRD rank metric convolutional codes, Proceedings, Int. Symp. Inf. Theory, (2017), 2766–2770.

[27]

A. Neri, Twisted linearized reed-solomon codes: A skew polynomial framework, preprint, 2021, arXiv: 2105.10451.

[28]

A. NeriA.-L. Horlemann-TrautmannT. Randrianarisoa and J. Rosenthal, On the genericity of maximum rank distance and Gabidulin codes, Des. Codes Cryptogr., 86 (2018), 341-363.  doi: 10.1007/s10623-017-0354-4.

[29]

R. W. Nobrega and B. F. Uchoa-Filho, Multishot codes for network coding: Bounds and a multilevel construction, Proceedings, Int. Symp. Inf. Theory, (2009), 428–432.

[30]

O. Ore, Theory of non-commutative polynomials, Ann. of Math., 34 (1933), 480-508.  doi: 10.2307/1968173.

[31]

O. Ore, On a special class of polynomials, Trans. Amer. Math. Soc., 35 (1933), 559-584.  doi: 10.1090/S0002-9947-1933-1501703-0.

[32]

K. Otal and F. Özbudak, Explicit constructions of some non-Gabidulin linear maximum rank distance codes, Adv. Math. Commun., 10 (2016), 589-600.  doi: 10.3934/amc.2016028.

[33]

R. Overbeck, Structural attacks for public key cryptosystems based on Gabidulin codes, J. Cryptology, 21 (2008), 280-301.  doi: 10.1007/s00145-007-9003-9.

[34]

S. Puchinger, J. S. H. Rosenkilde and J. Sheekey, Further generalisations of twisted Gabidulin codes, in Proceedings of the 10th International Workshop on Coding and Cryptography, 2017.

[35]

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

[36]

R. M. Roth, Tensor codes for the rank metric, IEEE Trans. Inf. Theory, 42 (1996), 2146-2157.  doi: 10.1109/18.556603.

[37]

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

[38]

J. Sheekey, MRD codes: Constructions and connections, in Combinatorics and Finite Fields: Difference Sets, Polynomials, Pseudorandomness and Applications, (eds. K-U. Schimdt and A. Winterhof), (2019), 255–286. doi: 10.1515/9783110642094-013.

[39]

J. Sheekey, New semifields and new MRD codes from skew polynomial rings, J. Lond. Math. Soc., 101 (2020), 432-456.  doi: 10.1112/jlms.12281.

[40]

D. SilvaF. R. Kschischang and R. Köetter, A rank-metric approach to error control in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3951-3967.  doi: 10.1109/TIT.2008.928291.

[41]

R. Trombetti and Y. Zhou, A new family of MRD codes in $\mathbb{F}_q^{2n \times 2n}$ with right and middle nuclei $\mathbb{F}_{q^n}$, IEEE Trans. Inf. Theory, 65 (2019), 1054-1062.  doi: 10.1109/TIT.2018.2853184.

[42]

T. Zhang and G. Ge, Constructions of optimal Ferrers diagram rank metric codes, Des. Codes Cryptogr., 87 (2019), 107-121.  doi: 10.1007/s10623-018-0491-4.

show all references

References:
[1]

RQC, Accessed: June, 14th 2021. Available from: https://pqc-rqc.org/.

[2]

C. Aguilar-MelchorO. BlazyJ.-C. DeneuvilleP. Gaborit and G. Zémor, Efficient encryption from random quasi-cyclic codes, IEEE Trans. Inf. Theory, 64 (2018), 3927-3943.  doi: 10.1109/TIT.2018.2804444.

[3]

J. Antrobus and H. Gluesing-Luerssen, Maximal Ferrers diagram codes: Constructions and genericity considerations, IEEE Trans. Inform. Theory, 65 (2019), 6204-6223.  doi: 10.1109/TIT.2019.2926256.

[4]

N. AragonP. GaboritA. HautevilleO. Ruatta and G. Zémor, Low rank parity check codes: New decoding algorithms and applications to cryptography, IEEE Trans. Inform. Theory, 65 (2019), 7697-7717.  doi: 10.1109/TIT.2019.2933535.

[5]

D. AugotP. Loidreau and G. Robert, Generalized Gabidulin codes over fields of any characteristic, Des. Codes Cryptogr., 86 (2018), 1807-1848.  doi: 10.1007/s10623-017-0425-6.

[6]

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

[7]

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

[8]

H. El Gamal and A. R. Hammons, On the design of algebraic space-time codes for MIMO block-fading channels, IEEE Trans. Inform. Theory, 49 (2003), 151-163.  doi: 10.1109/TIT.2002.806116.

[9]

T. EtzionE. GorlaA. Ravagnani and A. Wachter-Zeh, Optimal Ferrers diagram rank-metric codes, IEEE Trans. Inform. Theory, 62 (2016), 1616-1630.  doi: 10.1109/TIT.2016.2522971.

[10]

T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inform. Theory, 55 (2009), 2909-2919.  doi: 10.1109/TIT.2009.2021376.

[11]

È. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21 (1985), 3-16. 

[12]

È. M. Gabidulin and A. Kshevetskiy, The new construction of rank codes, Proceedings, Int. Symp. Inf. Theory, (2005), 2105–2108.

[13]

È. M. Gabidulin, A. V. Paramonov and O. V. Tretjakov, Ideals over a non-commutative ring and their application in cryptology, Advances in Cryptology — EUROCRYPT '91, Springer Berlin Heidelberg, (1991), 482–489. doi: 10.1007/3-540-46416-6_41.

[14]

L. Giuzzi and F. Zullo, Identifiers for MRD-codes, Linear Algebra Appl., 575 (2019), 66-86.  doi: 10.1016/j.laa.2019.03.030.

[15]

E. Gorla and A. Ravagnani, Subspace codes from Ferrers diagrams, J. Algebra Appl., 16 (2017), 1750131, 23 pp. doi: 10.1142/S0219498817501316.

[16]

A.-L. Horlemann-Trautmann and K. Marshall, New criteria for MRD and Gabidulin codes and some rank-metric code constructions, Adv. Math. Commun., 11 (2017), 533-548.  doi: 10.3934/amc.2017042.

[17]

S. LiuY. Chang and T. Feng, Constructions for optimal Ferrers diagram rank-metric codes, IEEE Trans. Inform. Theory, 65 (2019), 4115-4130.  doi: 10.1109/TIT.2019.2894401.

[18]

G. LunardonR. Trombetti and Y. Zhou, Generalized twisted Gabidulin codes, J. Combin. Theory Ser. A, 159 (2018), 79-106.  doi: 10.1016/j.jcta.2018.05.004.

[19]

R. MahmoodA. Badr and A. Khisti, Convolutional codes with maximum column sum rank for network streaming, IEEE Trans. Inform. Theory, 62 (2016), 3039-3052.  doi: 10.1109/TIT.2016.2555949.

[20]

U. Martínez-Peñas, Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring, J. Algebra, 504 (2018), 587-612.  doi: 10.1016/j.jalgebra.2018.02.005.

[21]

U. Martínez-Peñas, Theory of supports for linear codes endowed with the sum-rank metric, Des. Codes Cryptogr., 87 (2019), 2295-2320.  doi: 10.1007/s10623-019-00619-8.

[22]

U. Martínez-Peñas and F. R. Kschischang, Reliable and secure multishot network coding using linearized Reed-Solomon codes, IEEE Trans. Inf. Theory, 65 (2019), 4785-4803.  doi: 10.1109/TIT.2019.2912165.

[23]

U. Martínez-Peñas and F. R. Kschischang, Universal and dynamic locally repairable codes with maximal recoverability via sum-rank codes, IEEE Trans. Inf. Theory, 65 (2019), 7790-7805.  doi: 10.1109/TIT.2019.2924888.

[24]

R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, Deep Space Network Progress Report, 44 (1978), 114-116. 

[25]

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.

[26]

D. Napp, R. Pinto, J. Rosenthal and P. Vettori, MRD rank metric convolutional codes, Proceedings, Int. Symp. Inf. Theory, (2017), 2766–2770.

[27]

A. Neri, Twisted linearized reed-solomon codes: A skew polynomial framework, preprint, 2021, arXiv: 2105.10451.

[28]

A. NeriA.-L. Horlemann-TrautmannT. Randrianarisoa and J. Rosenthal, On the genericity of maximum rank distance and Gabidulin codes, Des. Codes Cryptogr., 86 (2018), 341-363.  doi: 10.1007/s10623-017-0354-4.

[29]

R. W. Nobrega and B. F. Uchoa-Filho, Multishot codes for network coding: Bounds and a multilevel construction, Proceedings, Int. Symp. Inf. Theory, (2009), 428–432.

[30]

O. Ore, Theory of non-commutative polynomials, Ann. of Math., 34 (1933), 480-508.  doi: 10.2307/1968173.

[31]

O. Ore, On a special class of polynomials, Trans. Amer. Math. Soc., 35 (1933), 559-584.  doi: 10.1090/S0002-9947-1933-1501703-0.

[32]

K. Otal and F. Özbudak, Explicit constructions of some non-Gabidulin linear maximum rank distance codes, Adv. Math. Commun., 10 (2016), 589-600.  doi: 10.3934/amc.2016028.

[33]

R. Overbeck, Structural attacks for public key cryptosystems based on Gabidulin codes, J. Cryptology, 21 (2008), 280-301.  doi: 10.1007/s00145-007-9003-9.

[34]

S. Puchinger, J. S. H. Rosenkilde and J. Sheekey, Further generalisations of twisted Gabidulin codes, in Proceedings of the 10th International Workshop on Coding and Cryptography, 2017.

[35]

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

[36]

R. M. Roth, Tensor codes for the rank metric, IEEE Trans. Inf. Theory, 42 (1996), 2146-2157.  doi: 10.1109/18.556603.

[37]

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

[38]

J. Sheekey, MRD codes: Constructions and connections, in Combinatorics and Finite Fields: Difference Sets, Polynomials, Pseudorandomness and Applications, (eds. K-U. Schimdt and A. Winterhof), (2019), 255–286. doi: 10.1515/9783110642094-013.

[39]

J. Sheekey, New semifields and new MRD codes from skew polynomial rings, J. Lond. Math. Soc., 101 (2020), 432-456.  doi: 10.1112/jlms.12281.

[40]

D. SilvaF. R. Kschischang and R. Köetter, A rank-metric approach to error control in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3951-3967.  doi: 10.1109/TIT.2008.928291.

[41]

R. Trombetti and Y. Zhou, A new family of MRD codes in $\mathbb{F}_q^{2n \times 2n}$ with right and middle nuclei $\mathbb{F}_{q^n}$, IEEE Trans. Inf. Theory, 65 (2019), 1054-1062.  doi: 10.1109/TIT.2018.2853184.

[42]

T. Zhang and G. Ge, Constructions of optimal Ferrers diagram rank metric codes, Des. Codes Cryptogr., 87 (2019), 107-121.  doi: 10.1007/s10623-018-0491-4.

Figure 1.  $ \mathcal{F} = \{2, 2, 4, 4, 6, 6\} $
[1]

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

[2]

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

[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]

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

[5]

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

[6]

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

[7]

Enhui Lim, Frédérique Oggier. On the generalised rank weights of quasi-cyclic codes. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022010

[8]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045

[9]

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

[10]

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

[11]

Olof Heden, Denis S. Krotov. On the structure of non-full-rank perfect $q$-ary codes. Advances in Mathematics of Communications, 2011, 5 (2) : 149-156. doi: 10.3934/amc.2011.5.149

[12]

Nuh Aydin, Nicholas Connolly, Markus Grassl. Some results on the structure of constacyclic codes and new linear codes over GF(7) from quasi-twisted codes. Advances in Mathematics of Communications, 2017, 11 (1) : 245-258. doi: 10.3934/amc.2017016

[13]

Relinde Jurrius, Ruud Pellikaan. On defining generalized rank weights. Advances in Mathematics of Communications, 2017, 11 (1) : 225-235. doi: 10.3934/amc.2017014

[14]

Xiang Wang, Wenjuan Yin. New nonexistence results on perfect permutation codes under the hamming metric. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021058

[15]

Axel Kohnert, Johannes Zwanzger. New linear codes with prescribed group of automorphisms found by heuristic search. Advances in Mathematics of Communications, 2009, 3 (2) : 157-166. doi: 10.3934/amc.2009.3.157

[16]

Anna-Lena Trautmann. Isometry and automorphisms of constant dimension codes. Advances in Mathematics of Communications, 2013, 7 (2) : 147-160. doi: 10.3934/amc.2013.7.147

[17]

Leandro M. Del Pezzo, Nicolás Frevenza, Julio D. Rossi. Convex and quasiconvex functions in metric graphs. Networks and Heterogeneous Media, 2021, 16 (4) : 591-607. doi: 10.3934/nhm.2021019

[18]

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

[19]

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

[20]

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

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (116)
  • HTML views (44)
  • Cited by (0)

[Back to Top]