Generalized subspace subcodes in the rank metric
DOI:
https://doi.org/10.13069/jacodesmath.v13i2.334Keywords:
Coding theory, Rank-metric, Gabidulin code, Cryptography, Shortened code, Punctured code, Subfield subcodesAbstract
Rank-metric codes were studied by E. Gabidulin in 1985 after a brief introduction by Delsarte in 1978 as analogues of Reed-Solomon codes in the rank metric, but based on linearized polynomials. They have found applications in many areas, including linear network coding and space-time coding. They are also used in cryptography to reduce the size of the keys compared to Hamming metric codes at the same level of security. However, some families of rank-metric codes suffer from structural attacks due to the strong algebraic structure from which they are defined. It therefore becomes interesting to find new code families in order to address these questions in the landscape of rank-metric codes. In this paper, we provide a generalization of Subspace Subcodes in rank metric introduced by Gabidulin and Loidreau. We also characterize this family by giving an algorithm which allows one to obtain its generator and parity-check matrices based on the associated extended codes. We have also studied the specific case of Gabidulin codes whose underlying decoding algorithms are known. Bounds for the cardinalities of these codes, both in the general case and in the case of Gabidulin codes, are also provided.
Accepted: 19 November 2025
Downloads
References
T. P. Berger and P. Loidreau, How to mask the structure of codes for a cryptographic use, Des. Codes Cryptogr. 35(1) (2005) 63–79.
T. P. Berger, C. Thiécoumba Gueye, J. Belo Klamti, Generalized subspace subcodes with application in cryptology, IEEE Trans. Inf. Theory 65(8) (2019) 4641–4657.
T. P. Berger, C. Thiécoumba Gueye, J. Belo Klamti, O. Ruatta, Designing a public key cryptosystem based on quasi-cyclic subspace subcodes of Reed-Solomon codes, in: Algebra, Codes and Cryptology, Springer (2019) 97–113.
T. P. Berger, P. Gaborit, O. Ruatta, Gabidulin matrix codes and their application to small ciphertext size cryptosystems, in: Indocrypt 2017, LNCS 10698, Springer (2017) 247–266.
A. Couvreur, M. Lequesne, On the security of subspace subcodes of Reed-Solomon codes for public key encryption, IEEE Trans. Inf. Theory 68(1) (2021) 632–648.
A. Couvreur, A. Otmani, J.-P. Tillich, Polynomial time attack on wild McEliece over quadratic extensions, IEEE Trans. Inf. Theory 63(1) (2017) 404–427.
P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Comb. Theory A 25(3) (1978) 226–241.
I. El Qachchach, O. Habachi, J.-P. Cances, V. Meghdadi, Efficient multi-source network coding using low rank parity check code, in: IEEE WCNC 2018, IEEE (2018) 1–6.
E. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii 21(1) (1985) 3–16.
E. M. Gabidulin and P. Loidreau, On subcodes of codes in rank metric, in: Proc. IEEE Int. Symp. Inf. Theory (ISIT 2005), IEEE (2005) 121–123.
E. M. Gabidulin and P. Loidreau, Properties of subspace subcodes of Gabidulin codes, Adv. Math. Commun. 2(2) (2008) 147–157.
E. M. Gabidulin, Attacks and counter-attacks on the GPT public key cryptosystem, Des. Codes Cryptogr. 48(2) (2008) 171–177.
E. M. Gabidulin, A. V. Paramonov, O. V. Tretjakov, Ideals over a non-commutative ring and their application in cryptology, in: Workshop on the Theory and Application of Cryptographic Techniques, Springer (1991) 482–489.
J. K. Gibson, Severely denting the Gabidulin version of the McEliece public key cryptosystem, Des. Codes Cryptogr. 6(1) (1995) 37–45.
K. Gibson, The security of the Gabidulin public key cryptosystem, in: Eurocrypt ’96, LNCS 1070, Springer (1996) 212–223.
M. Hattori, R. J. McEliece, G. Solomon, Subspace subcodes of Reed-Solomon codes, IEEE Trans. Inf. Theory 44(5) (1998) 1861–1880.
A.-L. Horlemann-Trautmann, K. Marshall, J. Rosenthal, Extension of Overbeck’s attack for Gabidulin-based cryptosystems, Des. Codes Cryptogr. 86(2) (2018) 319–340.
W. C. Huffman, V. Pless, Fundamentals of Error-Correcting Codes, Cambridge Univ. Press (2003).
J. M. Jensen, Subgroup subcodes, IEEE Trans. Inf. Theory 41(3) (1995) 781–785.
H. T. Kalachi, On the failure of the smart approach of the GPT cryptosystem, Cryptologia 46(2) (2022) 167–182.
P. Loidreau, Designing a rank metric based McEliece cryptosystem, in: Post-Quantum Cryptography (PQC 2010), LNCS 6061, Springer (2010) 142–152.
H.-F. Lu, P. V. Kumar, A unified construction of space-time codes with optimal rate-diversity trade-off, IEEE Trans. Inf. Theory 51(5) (2005) 1709–1730.
C. A. Melchor, N. Aragon, M. Bardet, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, ROLLO–Rank-Ouroboros, LAKE & LOCKER, NIST Competition for Post-Quantum Cryptography (2019).
C. A. Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, G. Zémor, Rank quasi-cyclic (RQC), NIST Competition for Post-Quantum Cryptography (2017).
O. Ore, On a special class of polynomials, Trans. Amer. Math. Soc. 35(3) (1933) 559–584.
A. Otmani, H. T. Kalachi, S. Ndjeya, Improved cryptanalysis of rank metric schemes based on Gabidulin codes, Des. Codes Cryptogr. 86(9) (2018) 1983–1996.
R. Overbeck, A new structural attack for GPT and variants, in: Mycrypt 2005, LNCS 3715, Springer (2005) 50–63.
H. Rashwan, E. M. Gabidulin, B. Honary, A Smart approach for GPT cryptosystem based on rank codes, in: IEEE Int. Symp. Inf. Theory (ISIT 2010), IEEE (2010) 2463–2467.
H. Rashwan, E. M. Gabidulin, B. Honary, Security of the GPT cryptosystem and its applications to cryptography, Secur. Commun. Networks 4(8) (2011) 937–946.
I. S. Reed, G. Solomon, Polynomial codes over certain finite fields, J. Soc. Indust. Appl. Math. 8(2) (1960) 300–304.
P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in: 35th Annu. Symp. Foundations of Computer Science (FOCS 1994), IEEE (1994) 124–134.
Y. Wu, On expanded cyclic and Reed-Solomon codes, IEEE Trans. Inf. Theory 57(2) (2011) 601–620.
