[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Two modifications for Loidreau’s code-based cryptosystem

  • Original Paper
  • Published:
Applicable Algebra in Engineering, Communication and Computing Aims and scope

Abstract

This paper presents two modifications for Loidreau’s cryptosystem, a rank metric-based cryptosystem constructed by using Gabidulin codes in the McEliece setting. Recently a polynomial-time key recovery attack was proposed to break this cryptosystem in some cases. To prevent this attack, we propose the use of subcodes to disguise the secret codes in Modification I. In Modification II, we choose a random matrix of low column rank to mix with the secret matrix. Our analysis shows that these two modifications can both resist the existing structural attacks. Furthermore, these modifications have a much more compact representation of public keys compared to Classic McEliece, which has been selected into the fourth round of the NIST-PQC project.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Albrecht, M.R., Bernstein, D.J., Chou, T., Cid, C., Gilcher, J., Lange, T., Maram, V., Maurich, I., Misoczki, R., Niederhagen, R., Paterson, K., Persichetti, E., Peters, C., Schwabe, P., Sendrier, N., Szefer, J., Tjhai, C.J., Tomlinson, M., Wang, W.: Classic McEliece: conservative code-based cryptography. https://classic.mceliece.org/nist/mceliece-20201010.pdf. Accessed October 10 (2020)

  2. Aragon, N., Barreto, P.S., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Gaborit, P., Ghosh, S., Gueron, S., Güneysu, T., Melchor, C.A., Misoczki, R., Persichetti, E., Sendrier, Tillich, J.-P., N., Vasseur, V., Zémor, G.: BIKE: bit flipping key encapsulation. https://bikesuite.org/files/v4.1/BIKE_Spec.2020.10.22.1.pdf. Accessed October 10 (2020)

  3. Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.-P.: A new algorithm for solving the rank syndrome decoding problem. In: Proceedings of ISIT 2018, pp. 2421–2425. IEEE (2018)

  4. Augot, D., Finiasz, M.: A public key encryption scheme based on the polynomial reconstrution problem. In: Biham, E. (ed.): Proceedings of EUROCRYPT 2003, LNCS, vol. 2656, pp. 229–240. Springer (2003)

  5. Baldi, M., Bianchi, M., Chiaraluce, F., Rosenthal, J., Schipani, D.: Enhanced public key security for the McEliece cryptosystem. J. Cryptol. 29(1), 1–27 (2016)

    Article  MathSciNet  Google Scholar 

  6. Bardet, M., Briaud, P., Bros, M., Gaborit, P., Neiger, V., Ruatta, O., Tillich, J.-P.: An algebraic attack on rank metric code-based cryptosystems. In: Proceedings of EUROCRYPT 2020, LNCS, vol. 12107, pp. 64–93. Springer (2020)

  7. Bardet, M., Bros, M., Cabarcas, D., Gaborit, P., Perlner, R., Smith-Tone, D., Tillich, J.-P., Verbel, J.: Improvements of algebraic attacks for solving the rank decoding and MinRank problems. In: Proceedings of ASIACRYPT 2020, LNCS, vol. 12491, pp. 507–536. Springer (2020)

  8. Berlekamp, E.R., McEliece, R.J., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978)

    Article  MathSciNet  Google Scholar 

  9. Bombar, M., Couvreur, A.: Decoding supercodes of Gabidulin codes and applications to cryptanalysis. In: Proceedings of PQCrypto 2021, LNCS, vol. 12841, pp. 3–22. Springer (2021)

  10. Bosma, W., Cannon, J., Playoust, C.: The MAGMA algebra system I: The user language. J. Symbolic Comput. 24(3–4), 235–265 (1997)

    Article  MathSciNet  Google Scholar 

  11. Canteaut, A., Sendrier, N.: Cryptanalysis of the original McEliece cryptosystem. In: Ohta, K., Pei, D. (eds.): Proceedings of ASIACRYPT 1998, LNCS, vol. 1514, pp. 187–199. Springer (2000)

  12. Chabaud, F., Stern, J.: The cryptographic security of the syndrome decoding problem for rank distance codes. In: Proceedings of ASIACRYPT 1996, pp. 368–381. Springer (1996)

  13. Coggia, D., Couvreur, A.: On the security of a Loidreau rank metric code based encryption scheme. Des. Codes Cryptogr. 88(9), 1941–1957 (2020)

    Article  MathSciNet  Google Scholar 

  14. Couvreur, A., Gaborit, P., Otmani, A., Tillich, J.-P.: Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes. Des. Codes Cryptogr. 73(2), 641–666 (2014)

    Article  MathSciNet  Google Scholar 

  15. Couvreur, A., Otmani, A., Tillich, J.-P., Gauthier-Umaña.: A polynomial-time attack on the BBCRS cryptosystem. In: Proceedings of PKC 2015, LNCS, vol. 9020, pp. 175–193. Springer (2015)

  16. Faugère, J.-C., Otmani, A., Perret, L., de Portzamparc, F., Tillich, J.-P.: Structural cryptanalysis of McEliece schemes with compact keys. Des. Codes Cryptogr. 79(1), 87–112 (2016)

    Article  MathSciNet  Google Scholar 

  17. Faure, C., Loidreau, P.: A new public-key cryptosystem based on the problem of reconstructing \(p\)-polynomials. In: Ytrehus, \(\varnothing\). (ed.): Proceedings of WCC 2005, LNCS, vol. 3969, pp. 304–315. Springer (2005)

  18. Gabidulin, E.M.: Theory of codes with maximum rank distance. Prob. Peredachi Inf. 21(1), 3–16 (1985)

    MathSciNet  Google Scholar 

  19. Gabidulin, E.M.: Attacks and counter-attacks on the GPT public key cryptosystem. Des. Codes Cryptogr. 48(2), 171–177 (2008)

    Article  MathSciNet  Google Scholar 

  20. Gabidulin, E.M., Ourivski, A.V., Honary, B., Ammar, B.: Reducible rank codes and their applications to cryptography. IEEE Trans. Inf. Theory 49(12), 3289–3293 (2003)

    Article  MathSciNet  Google Scholar 

  21. Gabidulin, E.M., Paramonov, A.V., Tretjakov, O.V.: Ideals over a non-commutative ring and their application in cryptology. In: Davies, D.W. (ed.): Proceedings of EUROCRYPT 1991, LNCS, vol. 547, pp. 482–489. Springer (1991)

  22. Gabidulin, E.M., Rashwan, H., Honary, B.: On improving security of GPT cryptosystems. In: Proceedings of ISIT 2009, pp. 1110–1114. IEEE (2009)

  23. Gaborit, P., Otmani, A., Kalachi, H.T.: Polynomial-time key recovery attack on the Faure–Loidreau scheme based on Gabidulin codes. Des. Codes Cryptogr. 86(7), 1391–1403 (2018)

    Article  MathSciNet  Google Scholar 

  24. Gaborit, P., Ruatta, O., Schrek, J.: On the complexity of the rank syndrome decoding problem. IEEE Trans. Inf. Theory 62(2), 1006–1019 (2016)

    Article  MathSciNet  Google Scholar 

  25. Gaborit, P., Zémor, G.: On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Trans. Inf. Theory 62(12), 7245–7252 (2016)

    Article  MathSciNet  Google Scholar 

  26. Ghatak, A.: Extending Coggia–Couvreur attack on Loidreau’s rank-metric cryptosystem. Des. Codes Cryptogr. 90(1), 215–238 (2022)

    Article  MathSciNet  Google Scholar 

  27. Gibson, K.: The security of the Gabidulin public key cryptosystem. In: Proceedings of EUROCRYPT 1996, LNCS, vol. 1070, pp. 212–223. Springer (1996)

  28. Horlemann-Trautmann, A.-L., Marshall, K.: New criteria for MRD and Gabidulin codes and some rank-metric code constructions. Adv. Math. Commun. 11(3), 533–548 (2017)

    Article  MathSciNet  Google Scholar 

  29. Horlemann-Trautmann, A.-L., Marshall, K., Rosenthal, J.: Considerations for rank-based cryptosystems. In: Proceedings of ISIT 2016, pp. 2544–2548. IEEE (2016)

  30. Horlemann-Trautmann, A.-L., Marshall, K., Rosenthal, J.: Extension of Overbeck’s attack for Gabidulin-based cryptosystems. Des. Codes Cryptogr. 86(2), 319–340 (2018)

    Article  MathSciNet  Google Scholar 

  31. Kobara, K., Imai, H.: Semantically secure McEliece public-key cryptosystems-conversions for McEliece PKC. Kim, K. (ed.): Proceedings of PKC 2001, LNCS, vol. 1992, pp. 19–35. Springer (2001)

  32. Lavauzelle, J., Loidreau, P., Pham, B.-D.: RAMESSES, a rank metric encryption scheme with short keys. arXiv:1911.13119 [cs.CR] (2019)

  33. Lee, P.J., Brickell, E.F.: An observation on the security of McEliece’s public-key cryptosystem. In: Guenther, C.G. (ed.): Proceedings of EUROCRYPT 1988, LNCS, vol. 330, pp. 275–280. Springer (1988)

  34. Li, Y.X., Deng, R.H., Wang, X.M.: On the equivalence of McEliece’s and Niederreiter’s public-key cryptosystems. IEEE Trans. Inf. Theory 40(1), 271–273 (1994)

    Article  MathSciNet  Google Scholar 

  35. Ling, S., Xing, C.: Coding Theory: A First Course. Cambridge University Press, Cambridge (2004)

    Book  Google Scholar 

  36. Loidreau, P.: A Welch-Berlekamp like algorithm for decoding Gabidulin codes. In: Ytrehus, \(\varnothing\). (ed.): Proceedings of WCC 2005, LNCS, vol. 3969, pp. 36–45. Springer (2005)

  37. Loidreau, P.: Designing a rank metric based McEliece cryptosystem. In: Sendrier, N. (ed.): Proceedings of PQCrypto 2010, LNCS, vol. 6061, pp. 142–152. Springer (2010)

  38. Loidreau, P.: A new rank metric codes based encryption scheme. In: Lange, T., Takagi, T. (Eds.): Proceedings of PQCrypto 2017, LNCS, vol. 10346, pp. 3–17. Springer (2017)

  39. Loidreau, P.: Analysing the key recovery complexity for a rank-metric code-based cryptosystem. https://drive.google.com/file/d/1FuMgqm0NfGMJOxaZyrIrI1OWn0UICwPo/view. Accessed July 1 (2021)

  40. Loidreau, P., Sendrier, N.: Weak keys in the McEliece public-key cryptosystem. IEEE Trans. Inf. Theory 47(3), 1207–1211 (2001)

    Article  MathSciNet  Google Scholar 

  41. McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Jet Propuls. Lab. DSN Progr. Rep. 42–44, 114–116 (1978)

    Google Scholar 

  42. Melchor, C.A., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Bos, J., Deneuville, J.-C., Dion, A., Gaborit, P., Lacan, J., Persichetti, E., Robert, J.-M., Véron, P., Zémor, G.: Hamming quasi-cyclic (HQC). http://pqc-hqc.org/doc/hqc-specification_2020-10-01.pdf. Accessed October 10 (2020)

  43. Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Prob. Control Inf. Theory 15(2), 159–166 (1986)

    MathSciNet  Google Scholar 

  44. Otmani, A., Kalachi, H.T., Ndjeya, S.: Improved cryptanalysis of rank metric schemes based on Gabidulin codes. Des. Codes Cryptogr. 86(9), 1983–1996 (2018)

    Article  MathSciNet  Google Scholar 

  45. 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)

    Article  MathSciNet  Google Scholar 

  46. Overbeck, R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptol. 21(2), 280–301 (2008)

    Article  MathSciNet  Google Scholar 

  47. Rashwan, H., Gabidulin, E.M., Honary, B.: A smart approach for GPT cryptosystem based on rank codes. In: Proceedings of ISIT 2010, pp. 2463–2467. IEEE (2010)

  48. Rashwan, H., Gabidulin, E.M., Honary, B.: Security of the GPT cryptosystem and its applications to cryptography. Secur. Commun. Netw. 4(8), 937–946 (2011)

    Article  Google Scholar 

  49. Renner, J., Puchinger, S., Wachter-Zeh, A.: LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding. Des. Codes Cryptogr. 89(6), 1279–1319 (2021)

    Article  MathSciNet  Google Scholar 

  50. Richter, G., Plass, S.: Error and erasure decoding of rank-codes with a modified Berlekamp–Massey algorithm. ITG FACHBERICHT, pp. 203–210 (2004)

  51. Sidelnikov, V.M., Shestakov, S.O.: On insecurity of cryptosystems based on generalized Reed–Solomon codes. Discret. Math. Appl. 2(4), 439–444 (1992)

    Google Scholar 

Download references

Acknowledgements

The authors are very grateful to Editor Prof. Teo Mora and the reviewers for their valuable comments and suggestions that greatly improved the presentation and quality of this paper. This research is supported by the National Key Research and Development Program of China (Grant No. 2018YFA0704703), the National Natural Science Foundation of China (Grant No. 61971243), the Natural Science Foundation of Tianjin (20JCZDJC00610), and the Fundamental Research Funds for the Central Universities of China (Nankai University).

Author information

Authors and Affiliations

  1. Chern Institute of Mathematics and LPMC, Nankai University, Tianjin, 300071, China

    Wenshuo Guo & Fang-Wei Fu

Authors
  1. Wenshuo Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fang-Wei Fu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wenshuo Guo.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Guo, W., Fu, FW. Two modifications for Loidreau’s code-based cryptosystem. AAECC 35, 647–665 (2024). https://doi.org/10.1007/s00200-022-00577-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00200-022-00577-0

Keywords

Search

Navigation