Gabidulin codes based post-quantum encryption schemes
DOI:
https://doi.org/10.55630/mem.2026.55.414-422Keywords:
Gabidulin codes, McEliece cryptosystemAbstract
In this paper we make a historic survey of GPT-like encryption schemes, and show that there are new promising directions in the design of encryption schemes inspired from the pioneering works.
References
M. ALBRECHT, D. J. BERNSTEIN, T. CHOU, C. CID, J. GILCHER, T. LANGE, V. MARAM, I. von MAURICH, R. MIZOCZKI, R. NIEDERHAGEN, E. PERSICHETTI, K. PATERSON, C. PETERS, P. SCHWABE, N. SENDRIER, J. SZEFER, C. J. TJHAI, M. TOMLINSON, and WANG WEN. Classic McEliece (merger of Classic McEliece and NTS-KEM. https://classic.mceliece.org, October 2020. Third round finalist of the NIST post-quantum cryptography call.
N. ARAGON, V. DYSERYN, PH. GABORIT, P. LOIDREAU, J. RENNER, and A. WACHTERZEH. LowMS: a new rank metric code-based KEM without ideal structure. Des. Codes Cryptogr., 92(4):1075–1093, 2024.
D. AUGOT, P. LOIDREAU, and G. ROBERT. Generalized Gabidulin codes over fields of any characteristic. Des. Codes Cryptogr., 86(8):1807–1848, 2018.
M. BALDI, M. BIANCHI, F. CHIARALUCE, J. ROSENTHAL, and D. SCHIPANI. Enhanced public key security for the McEliece cryptosystem. J. Cryptology, 29(1):1–27, 2016.
M. BARDET, P. BRIAUD, M. BROS, PH. GABORIT, and J.-P. TILLICH. Revisiting algebraic attacks on minrank and on the rank decoding problem. Des. Codes Cryptogr., 91(11):3671–3707, 2023.
M. BARDET, M. BROS, D. CABARCAS, PH. GABORIT, R. PERLNER, D. SMITH-TONE, J.-P. TILLICH, and J. VERBEL. Improvements of algebraic attacks for solving the rank decoding and minrank problems. In Advances in Cryptology - ASIACRYPT 2020, pages 507–536, 2020.
P. BRIAUD and P. LOIDREAU. Cryptanalysis of Rank-Metric Schemes Based on Distorted Gabidulin Codes. In T. JOHANSSON and D. SMITH-TONE, editors, Post-Quantum Cryptography 2023, volume 14154 of LNCS, pages 38–56, 2023.
F. CHABAUD and J. STERN. The cryptographic security of the syndrome decoding problem for rank distance codes. In Advances in Cryptology - ASIACRYPT 1996, volume 1163 of LNCS, pages 368–381, Kyongju, Korea. Springer, November 1996.
D. COGGIA and A. COUVREUR. On the security of a Loidreau rank metric code based encryption scheme. Des. Codes Cryptogr., 88(9):1941–1957, 2020.
A. COUVREUR, A. OTMANI, J.-P. TILLICH, and V. GAUTHIER-UMAÑA. A polynomialtime attack on the BBCRS scheme. In J. KATZ, editor, Public-Key Cryptography - PKC 2015, volume 9020 of LNCS, pages 175–193. Springer, 2015.
T. DEBRIS-ALAZARD and J.-P. TILLICH. Two attacks on rank metric code-based schemes: ranksign and an identity-based-encryption scheme. In Advances in Cryptology - ASIACRYPT 2018, volume 11272 of LNCS, pages 62–92, Brisbane, Australia. Springer, December 2018.
PH. DELSARTE. Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory, Ser. A, 25(3):226–241, 1978.
E. GABIDULIN, H. RASHWAN, and B. HONARY. On improving security of GPT cryptosystems. In Proc. IEEE Int. Symposium Inf. Theory - ISIT, pages 1110–1114. IEEE, 2009.
E. M. GABIDULIN. Theory of codes with maximum rank distance. Problemy Peredachi Informatsii, 21(1):3–16, 1985.
E. M. GABIDULIN, A. V. PARAMONOV, and O. V. TRETJAKOV. Ideals over a non-commutative ring and their applications to cryptography. In Advances in Cryptology - EUROCRYPT’91, number 547 in LNCS, pages 482–489, Brighton, April 1991.
PH. GABORIT, G. MURAT, O. RUATTA, and G. ZÉMOR. Low rank parity check codes and their application to cryptography. In Proceedings of the Workshop on Coding and Cryptography WCC’2013, Bergen, Norway, 2013. URL: www.selmer.uib.no/WCC2013/pdfs/Gaborit.pdf.
PH. GABORIT, O. RUATTA, and J. SCHREK. On the complexity of the rank syndrome decoding problem. IEEE Trans. Information Theory, 62(2):1006–1019, 2016.
P. LOIDREAU. An evolution of GPT cryptosystem. In Proceedings of the 15th Algebraic and Combinatorial Theory, Albena, Bulgaria, pages 215–220, 2016.
P. LOIDREAU. A new rank metric codes based encryption scheme. In Post-Quantum Cryptography 2017, volume 10346 of LNCS, pages 3–17. Springer, 2017.
P. LOIDREAU. Analysis of a public-key encryption scheme based on distorted gabidulin codes. In Twelfth International Workshop on Coding and Cryptography, WCC 2022, 2022. URL: https://www.wcc2022.uni-rostock.de.
R. J. MCELIECE. A public-key system based on algebraic coding theory. In DSN Progress Report 44. Jet Propulsion Lab, 1978, pages 114–116.
A. OTMANI, H. TALÉ-KALACHI, and S. NDJEYA. Improved cryptanalysis of rank metric schemes based on Gabidulin codes. Des. Codes Cryptogr., 86(9):1983–1996, 2018.
A. V. OURIVSKI and T. JOHANSSON. New technique for decoding codes in the rank metric and its cryptography applications. English. Problems of Information Transmission, 38(3):237–246, 2002.
R. OVERBECK. Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptology, 21(2):280–301, 2008.
H. RASHWAN, E. GABIDULIN, and B. HONARY. A smart approach for GPT cryptosystem based on rank codes. In Proc. IEEE Int. Symposium Inf. Theory - ISIT, pages 2463–2467. IEEE, 2010.
