×

An algebraic attack on rank metric code-based cryptosystems. (English) Zbl 1479.94122

Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2020. 39th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, May 10–14, 2020. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 12107, 64-93 (2020).
Summary: The Rank metric decoding problem is the main problem considered in cryptography based on codes in the rank metric. Very efficient schemes based on this problem or quasi-cyclic versions of it have been proposed recently, such as those in the submissions ROLLO and RQC currently at the second round of the NIST Post-Quantum Cryptography Standardization Process. While combinatorial attacks on this problem have been extensively studied and seem now well understood, the situation is not as satisfactory for algebraic attacks, for which previous work essentially suggested that they were ineffective for cryptographic parameters. In this paper, starting from Ourivski and Johansson’s algebraic modelling of the problem into a system of polynomial equations [A. V. Ourivski and T. Johansson, Probl. Inf. Transm. 38, No. 3, 237–246 (2002; Zbl 1026.94023); translation from Probl. Peredachi Inf. 38, No. 3, 83–93 (2002)], we show how to augment this system with easily computed equations so that the augmented system is solved much faster via Gröbner bases. This happens because the augmented system has solving degree \(r\), \(r+1\) or \(r+2\) depending on the parameters, where \(r\) is the rank weight, which we show by extending results from [J. Verbel et al., Lect. Notes Comput. Sci. 11505, 167–186 (2019; Zbl 1509.94136)] on systems arising from the MinRank problem; with target rank \(r\), Verbel et al. lower the solving degree to \(r+2\), and even less for some favorable instances that they call “superdetermined”. We give complexity bounds for this approach as well as practical timings of an implementation using magma. This improves upon the previously known complexity estimates for both Gröbner basis and (non-quantum) combinatorial approaches, and for example leads to an attack in 200 bits on ROLLO-I-256 whose claimed security was 256 bits.
For the entire collection see [Zbl 1475.94009].

MSC:

94A60 Cryptography
81P94 Quantum cryptography (quantum-theoretic aspects)
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

Software:

M4RI; Durandal; GBLA; NTRU
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aguilar Melchor, C., et al.: Ouroboros-R. First round submission to the NIST post-quantum cryptography call, November 2017. https://pqc-ouroborosr.org
[2] Aguilar Melchor, C., et al.: Rank quasi cyclic (RQC). First round submission to the NIST post-quantum cryptography call, November 2017. https://pqc-rqc.org
[3] Aguilar Melchor, C., et al.: Rank quasi cyclic (RQC). Second round submission to the NIST post-quantum cryptography call, April 2019. https://pqc-rqc.org
[4] Albrecht, M., Bard, G.: The M4RI Library - Version 20140914. The M4RI Team (2014). http://m4ri.sagemath.org
[5] Aragon, N., et al.: LAKE - Low rAnk parity check codes Key Exchange. First round submission to the NIST post-quantum cryptography call, November 2017. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/LAKE.zip
[6] Aragon, N., et al.: LOCKER - LOw rank parity ChecK codes EncRyption. First round submission to the NIST post-quantum cryptography call, November 2017. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/LOCKER.zip
[7] Aragon, N., et al.: ROLLO (merger of Rank-Ouroboros, LAKE and LOCKER). Second round submission to the NIST post-quantum cryptography call, March 2019. https://pqc-rollo.org
[8] Aragon, N.; Blazy, O.; Gaborit, P.; Hauteville, A.; Zémor, G.; Ishai, Y.; Rijmen, V., Durandal: a rank metric based signature scheme, Advances in Cryptology - EUROCRYPT 2019, 728-758 (2019), Cham: Springer, Cham · Zbl 1509.94150 · doi:10.1007/978-3-030-17659-4_25
[9] Aragon, N., Gaborit, P., Hauteville, A., Ruatta, O., Zémor, G.: RankSign - a signature proposal for the NIST’s call. First round submission to the NIST post-quantum cryptography call, November 2017. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/RankSign.zip
[10] Aragon, N., Gaborit, P., Hauteville, A., Tillich, J.P.: A new algorithm for solving the rank syndrome decoding problem. In: 2018 IEEE International Symposium on Information Theory (ISIT 2018), Vail, CO, USA, 17-22 June 2018, pp. 2421-2425. IEEE (2018). doi:10.1109/ISIT.2018.8437464
[11] Ars, G.; Faugère, J-C; Imai, H.; Kawazoe, M.; Sugita, M.; Lee, PJ, Comparison between XL and Gröbner basis algorithms, Advances in Cryptology - ASIACRYPT 2004, 338-353 (2004), Heidelberg: Springer, Heidelberg · Zbl 1094.94024 · doi:10.1007/978-3-540-30539-2_24
[12] Bardet, M.: Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. Ph.D. thesis, Université Paris VI, December 2004. http://tel.archives-ouvertes.fr/tel-00449609/en/
[13] Bardet, M., et al.: Algebraic attacks for solving the Rank Decoding and MinRank problems without Gröbner basis. arXiv e-prints arXiv:2002.08322, February 2020
[14] Bardet, M.; Faugère, JC; Salvy, B., On the complexity of the \(F{}_5\) Gröbner basis algorithm, J. Symb. Comput., 70, 49-70 (2015) · Zbl 1328.68319 · doi:10.1016/j.jsc.2014.09.025
[15] Bardet, M., Faugère, J.C., Salvy, B., Yang, B.Y.: Asymptotic expansion of the degree of regularity for semi-regular systems of equations. In: MEGA 2005 - Effective Methods in Algebraic Geometry, pp. 1-14 (2005)
[16] Bouillaguet, C.; Delaplace, C.; Gerdt, VP; Koepf, W.; Seiler, WM; Vorozhtsov, EV, Sparse Gaussian elimination modulo p: an update, Computer Algebra in Scientific Computing, 101-116 (2016), Cham: Springer, Cham · Zbl 1453.65086 · doi:10.1007/978-3-319-45641-6_8
[17] Boyer, B., Eder, C., Faugère, J., Lachartre, S., Martani, F.: GBLA: Gröbner basis linear algebra package. In: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC 2016), Waterloo, ON, Canada, 19-22 July 2016, pp. 135-142 (2016). doi:10.1145/2930889.2930914 · Zbl 1361.13014
[18] Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Ph.D. thesis, Universitat Innsbruck (1965) · Zbl 1245.13020
[19] Bunch, JR; Hopcroft, JE, Triangular factorization and inversion by fast matrix multiplication, Math. Comput., 28, 125, 231-236 (1974) · Zbl 0276.15006 · doi:10.1090/S0025-5718-1974-0331751-8
[20] Buss, JF; Frandsen, GS; Shallit, JO, The computational complexity of some problems of linear algebra, J. Comput. Syst. Sci., 58, 3, 572-596 (1999) · Zbl 0941.68059 · doi:10.1006/jcss.1998.1608
[21] Cabarcas, D.; Smith-Tone, D.; Verbel, JA; Lange, T.; Takagi, T., Key recovery attack for ZHFE, Post-Quantum Cryptography, 289-308 (2017), Cham: Springer, Cham · Zbl 1437.94053 · doi:10.1007/978-3-319-59879-6_17
[22] Courtois, N.; Klimov, A.; Patarin, J.; Shamir, A.; Preneel, B., Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Advances in Cryptology — EUROCRYPT 2000, 392-407 (2000), Heidelberg: Springer, Heidelberg · Zbl 1082.94514 · doi:10.1007/3-540-45539-6_27
[23] Cox, D.; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (2001), New York: Springer, New York · Zbl 0861.13012 · doi:10.1007/978-0-387-35651-8
[24] Debris-Alazard, T.; Tillich, J-P; Peyrin, T.; Galbraith, S., Two attacks on rank metric code-based schemes: RankSign and an IBE scheme, Advances in Cryptology - ASIACRYPT 2018, 62-92 (2018), Cham: Springer, Cham · Zbl 1446.94124 · doi:10.1007/978-3-030-03326-2_3
[25] Ding, J.; Hodges, TJ; Rogaway, P., Inverting HFE systems is quasi-polynomial for all fields, Advances in Cryptology - CRYPTO 2011, 724-742 (2011), Heidelberg: Springer, Heidelberg · Zbl 1287.94064 · doi:10.1007/978-3-642-22792-9_41
[26] Ding, J., Kleinjung, T.: Degree of regularity for HFE-. Cryptology ePrint Archive, Report 2011/570 (2011). http://eprint.iacr.org/2011/570
[27] Ding, J.; Schmidt, D.; Fischlin, M.; Katzenbeisser, S., Solving degree and degree of regularity for polynomial systems over a finite fields, Number Theory and Cryptography, 34-49 (2013), Heidelberg: Springer, Heidelberg · Zbl 1291.94074 · doi:10.1007/978-3-642-42001-6_4
[28] Ding, J.; Yang, B-Y; Gaborit, P., Degree of regularity for HFEv and HFEv-, Post-Quantum Cryptography, 52-66 (2013), Heidelberg: Springer, Heidelberg · Zbl 1306.94046 · doi:10.1007/978-3-642-38616-9_4
[29] Dubois, V.; Gama, N.; Abe, M., The degree of regularity of HFE systems, Advances in Cryptology - ASIACRYPT 2010, 557-576 (2010), Heidelberg: Springer, Heidelberg · Zbl 1290.94066 · doi:10.1007/978-3-642-17373-8_32
[30] Eder, C.; Faugère, JC, A survey on signature-based algorithms for computing Gröbner bases, J. Symb. Comput., 80, 719-784 (2017) · Zbl 1412.68306 · doi:10.1016/j.jsc.2016.07.031
[31] Faugère, JC, A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139, 1-3, 61-88 (1999) · Zbl 0930.68174 · doi:10.1016/S0022-4049(99)00005-5
[32] Faugère, J.C.: A new efficient algorithm for computing Gröbner bases without reduction to zero: F5. In: Proceedings ISSAC 2002, pp. 75-83. ACM Press (2002) · Zbl 1072.68664
[33] Faugère, J-C; Levy-dit-Vehel, F.; Perret, L.; Wagner, D., Cryptanalysis of MinRank, Advances in Cryptology - CRYPTO 2008, 280-296 (2008), Heidelberg: Springer, Heidelberg · Zbl 1183.94033 · doi:10.1007/978-3-540-85174-5_16
[34] Faugère, J., Safey El Din, M., Spaenlehauer, P.: Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology. In: International Symposium on Symbolic and Algebraic Computation (ISSAC 2010), Munich, Germany, 25-28 July 2010, pp. 257-264 (2010). doi:10.1145/1837934.1837984 · Zbl 1321.68529
[35] Faugère, JC; Safey El Din, M.; Spaenlehauer, PJ, Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): algorithms and complexity, J. Symb. Comput., 46, 4, 406-437 (2011) · Zbl 1226.13017 · doi:10.1016/j.jsc.2010.10.014
[36] Gabidulin, EM, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21, 1, 3-16 (1985) · Zbl 0585.94013
[37] Gabidulin, EM; Paramonov, AV; Tretjakov, OV; Davies, DW, Ideals over a non-commutative ring and their application in cryptology, Advances in Cryptology — EUROCRYPT ’91, 482-489 (1991), Heidelberg: Springer, Heidelberg · Zbl 0766.94009 · doi:10.1007/3-540-46416-6_41
[38] Gaborit, P., Murat, G., Ruatta, O., Zémor, G.: Low rank parity check codes and their application to cryptography. In: Proceedings of the Workshop on Coding and Cryptography (WCC 2013), Bergen, Norway (2013). www.selmer.uib.no/WCC2013/pdfs/Gaborit.pdf
[39] Gaborit, P.; Ruatta, O.; Schrek, J., On the complexity of the rank syndrome decoding problem, IEEE Trans. Inf. Theory, 62, 2, 1006-1019 (2016) · Zbl 1359.94847 · doi:10.1109/TIT.2015.2511786
[40] Gaborit, P.; Ruatta, O.; Schrek, J.; Zémor, G.; Pointcheval, D.; Vergnaud, D., New results for rank-based cryptography, Progress in Cryptology - AFRICACRYPT 2014, 1-12 (2014), Cham: Springer, Cham · Zbl 1288.94062 · doi:10.1007/978-3-319-06734-6_1
[41] Gaborit, P.; Ruatta, O.; Schrek, J.; Zémor, G.; Mosca, M., RankSign: an efficient signature algorithm based on the rank metric, Post-Quantum Cryptography, 88-107 (2014), Cham: Springer, Cham · Zbl 1355.94055 · doi:10.1007/978-3-319-11659-4_6
[42] 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) · Zbl 1359.94848 · doi:10.1109/TIT.2016.2616127
[43] Granboulan, L.; Joux, A.; Stern, J.; Dwork, C., Inverting HFE is quasipolynomial, Advances in Cryptology - CRYPTO 2006, 345-356 (2006), Heidelberg: Springer, Heidelberg · Zbl 1161.94400 · doi:10.1007/11818175_20
[44] Hoffstein, J.; Pipher, J.; Silverman, JH; Buhler, JP, NTRU: a ring-based public key cryptosystem, Algorithmic Number Theory, 267-288 (1998), Heidelberg: Springer, Heidelberg · Zbl 1067.94538 · doi:10.1007/BFb0054868
[45] Kipnis, A.; Shamir, A.; Wiener, M., Cryptanalysis of the HFE public key cryptosystem by relinearization, Advances in Cryptology — CRYPTO’ 99, 19-30 (1999), Heidelberg: Springer, Heidelberg · Zbl 0940.94012 · doi:10.1007/3-540-48405-1_2
[46] Lazard, D.; van Hulzen, JA, Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, Computer Algebra, 146-156 (1983), Heidelberg: Springer, Heidelberg · Zbl 0539.13002 · doi:10.1007/3-540-12868-9_99
[47] Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings ISSAC 2014, pp. 296-303. ACM, New York (2014). doi:10.1145/2608628.2608664 · Zbl 1325.65061
[48] Levy-dit-Vehel, F., Perret, L.: Algebraic decoding of rank metric codes. Talk at the Special Semester on Gröbner Bases - Workshop D1, pp. 1-19 (2006). https://ricamwww.ricam.oeaw.ac.at/specsem/srs/groeb/download/Levy.pdf
[49] Loidreau, P.; Lange, T.; Takagi, T., A new rank metric codes based encryption scheme, Post-Quantum Cryptography, 3-17 (2017), Cham: Springer, Cham · Zbl 1437.94070 · doi:10.1007/978-3-319-59879-6_1
[50] Misoczki, R., Tillich, J.P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes (2012). http://eprint.iacr.org/2012/409
[51] Otmani, A.; Talé-Kalachi, H.; Ndjeya, S., Improved cryptanalysis of rank metric schemes based on Gabidulin codes, Des. Codes Cryptogr., 86, 9, 1983-1996 (2018) · Zbl 1411.94081 · doi:10.1007/s10623-017-0434-5
[52] Ourivski, AV; Johansson, T., New technique for decoding codes in the rank metric and its cryptography applications, Probl. Inf. Transm., 38, 3, 237-246 (2002) · Zbl 1026.94023 · doi:10.1023/A:1020369320078
[53] Overbeck, R.; Dawson, E.; Vaudenay, S., A new structural attack for GPT and variants, Progress in Cryptology - Mycrypt 2005, 50-63 (2005), Heidelberg: Springer, Heidelberg · Zbl 1126.94335 · doi:10.1007/11554868_5
[54] Storjohann, A.: Algorithms for matrix canonical forms. Ph.D. thesis, Swiss Federal Institute of Technology - ETH (2000)
[55] Lévy-dit Vehel, F., Perret, L.: Algebraic decoding of codes in rank metric. In: Communication at YACC06, Porquerolles, France, June 2006 · Zbl 1191.68280
[56] Verbel, J.; Baena, J.; Cabarcas, D.; Perlner, R.; Smith-Tone, D.; Ding, J.; Steinwandt, R., On the complexity of “superdetermined” minrank instances, Post-Quantum Cryptography, 167-186 (2019), Cham: Springer, Cham · Zbl 1509.94136 · doi:10.1007/978-3-030-25510-7_10
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.