Top

Designs, Codes and Cryptography

Published in:

19-07-2023

Revisiting algebraic attacks on MinRank and on the rank decoding problem

Authors: Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, Jean-Pierre Tillich

Published in: Designs, Codes and Cryptography | Issue 11/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The Rank Decoding problem (RD) is at the core of rank-based cryptography. Cryptosystems such as ROLLO and RQC, which made it to the second round of the NIST Post-Quantum Standardization Process, as well as the Durandal signature scheme, rely on it or its variants. This problem can also be seen as a structured version of MinRank, which is ubiquitous in multivariate cryptography. Recently, Bardet et al. (in: Canteaut and Ishai, Advances in cryptology—EUROCRYPT 2020, Springer, Cham, 2020; Advances in cryptology—ASIACRYPT 2020, international conference on the theory and application of cryptology and information security, 2020. Proceedings, 2020) proposed attacks based on two new algebraic modelings, namely the MaxMinors modeling which is specific to RD and the Support-Minors modeling which applies to MinRank in general. Both improved significantly the complexity of algebraic attacks on these two problems. In the case of RD and contrarily to what was believed up to now, these new attacks were shown to be able to outperform combinatorial attacks and this even for very small field sizes. However, we prove here that the analysis performed in Bardet et al. (in: Advances in cryptology—ASIACRYPT 2020, international conference on the theory and application of cryptology and information security, 2020. Proceedings, 2020) for one of these attacks which consists in mixing the MaxMinors modeling with the Support-Minors modeling to solve RD is too optimistic and leads to underestimate the overall complexity. This is done by exhibiting linear dependencies between these equations and by considering an \({{\mathbb {F}}}_{q^m}\) version of these modelings which turns out to be instrumental for getting a better understanding of both systems. Moreover, by working over \({{\mathbb {F}}}_{q^m}\) rather than over \({{\mathbb {F}}}_{q}\), we are able to drastically reduce the number of variables in the system and we (i) still keep enough algebraic equations to be able to solve the system, (ii) are able to analyze rigorously the complexity of our approach. This new approach may improve the older MaxMinors approach on RD from Bardet et al. (in: Canteaut and Ishai, Advances in cryptology—EUROCRYPT 2020, Springer, Cham, 2020; Advances in cryptology—ASIACRYPT 2020, international conference on the theory and application of cryptology and information security, 2020. Proceedings, 2020) for certain parameters. We also introduce a new hybrid approach on the Support-Minors system whose impact is much more general since it applies to any MinRank problem. This technique improves significantly the complexity of the Support-Minors approach for small to moderate field sizes.

previous article Plane curves giving rise to blocking sets over finite fields

next article A further study on bridge structures and constructing bijective S-boxes for low-latency masking

Available only for authorised users

A more canonical definition will be given in Sect. 2.

For instance in \({{\mathbb {F}}}_{q^2}\), \(f=\beta _1z_1+\beta _2z_2\) admits all multiples of \((\beta _2/\beta _1,1)\) as solution, whereas \({{\,\textrm{Unfold}\,}}(f) = \lbrace z_1,z_2\rbrace \) admits only (0, 0) as a solution in the algebraic closure of \({{\mathbb {F}}}_{q^2}\).

For affine systems, degree falls correspond to linear combinations between polynomials of a given degree that yield nonzero polynomials of smaller degree.

We abusively use the same name \(\varphi :{{\mathbb {F}}}_{q}^{m\times n}\rightarrow {{\mathbb {F}}}_{q}^{mn}\) and \({{\mathbb {F}}}_{q}^{m\times (n-a)}\rightarrow {{\mathbb {F}}}_{q}^{m(n-a)}\).

Aguilar Melchor C., Aragon N., Bettaieb S., Bidoux L., Blazy O., Deneuville J.C., Gaborit P., Hauteville A., Zémor G.: Ouroboros-R. First round submission to the NIST post-quantum cryptography call (2017). https://pqc-ouroborosr.org.

Aguilar Melchor C., Aragon N., Bettaieb S., Bidoux L., Blazy O., Deneuville J.C., Gaborit P., Zémor G.: Rank quasi cyclic (RQC). First round submission to the NIST post-quantum cryptography call (2017). https://pqc-rqc.org.

Aguilar Melchor C., Aragon N., Bettaieb S., Bidoux L., Blazy O., Deneuville J.C., Gaborit P., Zémor G., Couvreur A., Hauteville A.: Rank quasi cyclic (RQC). Second round submission to the NIST post-quantum cryptography call (2019). https://pqc-rqc.org.

Aguilar Melchor C., Aragon N., Bettaieb S., Bidoux L., Blazy O., Bros M., Couvreur A., Deneuville J.C., Gaborit P., Zémor G., Hauteville A.: Rank quasi cyclic (RQC). Second Round submission to NIST Post-Quantum Cryptography call (2020). https://pqc-rqc.org.

Aguilar Melchor C., Aragon N., Dyseryn V., Gaborit P., Zémor G.: LRPC codes with multiple syndromes: near ideal-size KEMs without ideals (2022). arXiv:2206.11961.

Alagic G., Jacob A., Apon D., Cooper D., Dang Q., Kelsey J., Liu Y.K., Miller C., Moody D., Peralta R., Perlner R., Robinson A., Smith-Tone D.: Status report on the second round of the NIST post-quantum cryptography standardization process. Tech. Rep. NISTIR 8309, NIST (2020). https://doi.org/10.6028/NIST.IR.8309, https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf.

Aragon N., Blazy O., Deneuville J.C., Gaborit P., Hauteville A., Ruatta O., Tillich J.P., Zémor G.: LAKE – Low rAnk parity check codes Key Exchange. First round submission to the NIST post-quantum cryptography call (2017). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/LAKE.zip.

Aragon N., Blazy O., Deneuville J.C., Gaborit P., Hauteville A., Ruatta O., Tillich J.P., Zémor G.: LOCKER – LOw rank parity ChecK codes EncRyption. First round submission to the NIST post-quantum cryptography call (2017). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/LOCKER.zip.

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 (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.: Improvement of Generic Attacks on the Rank Syndrome Decoding Problem. Working paper or preprint (2017). https://hal.archives-ouvertes.fr/hal-01618464.

11.

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, June 17–22, 2018. pp. 2421–2425. IEEE (2018). https://doi.org/10.1109/ISIT.2018.8437464.

12.

Aragon N., Blazy O., Deneuville J.C., Gaborit P., Hauteville A., Ruatta O., Tillich J.P., Zémor G., Aguilar Melchor C., Bettaieb S., Bidoux L., Bardet M., Otmani A.: ROLLO (merger of Rank-Ouroboros, LAKE and LOCKER). Second round submission to the NIST post-quantum cryptography call (2019). https://pqc-rollo.org.

13.

Aragon N., Blazy O., Gaborit P., Hauteville A., Zémor G.: Durandal: a rank metric based signature scheme. In: Advances in Cryptology—EUROCRYPT 2019—38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part III. LNCS, vol. 11478, pp. 728–758. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-17659-4_25.

14.

Baena J., Briaud P., Cabarcas D., Perlner R.A., Smith-Tone D., Verbel J.A.: Improving support-minors rank attacks: applications to GeMSS and Rainbow. IACR Cryptol. ePrint Arch., accepted for publication in CRYPTO 2022, p. 1677 (2021). https://eprint.iacr.org/2021/1677.

15.

Bardet M., Briaud P.: An algebraic approach to the rank support learning problem. In: Cheon J.H., Tillich J.P. (eds.) Post-Quantum Cryptography, vol. 12841, pp. 442–462. LNCS. Springer, Cham (2021).CrossRef

16.

Bardet M., Briaud P., Bros M., Gaborit P., Neiger V., Ruatta O., Tillich J.: An algebraic attack on rank metric code-based cryptosystems. In: Canteaut A., Ishai Y. (eds.) Advances in Cryptology—EUROCRYPT 2020, pp. 64–93. Springer, Cham (2020) arXiv:1910.00810.

17.

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: Advances in Cryptology—ASIACRYPT 2020, International Conference on the Theory and Application of Cryptology and Information Security, 2020. Proceedings. pp. 507–536 (2020). https://doi.org/10.1007/978-3-030-64837-4_17.

18.

Bellini E., Caullery F., Gaborit P., Manzano M., Mateu V.: Improved Veron identification and signature schemes in the rank metric. In: Proc. IEEE Int. Symposium Inf. Theory—ISIT 2019, pp. 1872–1876. IEEE, Paris (2019). arXiv:1903.10212.

19.

Bellini E., Gaborit P., Hasikos A., Mateu V.: Enhancing code based zero-knowledge proofs using rank metric. In: Krenn S., Shulman H., Vaudenay S. (eds.) Cryptology and Network Security—19th International Conference, CANS 2020, Vienna, Austria, 14–16 December 2020, Proceedings. Lecture Notes in Computer Science, vol. 12579, pp. 570–592. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-65411-5_28.

20.

Bellini E., Esser A., Sanna C., Verbel J.: MR-DSS—smaller MinRank-based (ring-)signatures. In: Cheon J.H. Johansson J.T. (eds.) Post-Quantum Cryptography 2022. LNCS, vol. 13512. Springer, Berlin (2022). https://eprint.iacr.org/2022/973.

21.

Bellini E., Esser A., Sanna C., Verbel J.: MR-DSS—smaller MinRank-based (ring-)signatures. IACR Cryptology ePrint Archive, version 20220921:142218. Report 2022/973 (2022). https://eprint.iacr.org/2022/973.

22.

Beullens W.: Improved cryptanalysis of UOV and Rainbow. In: Canteaut A., Standaert F.X. (eds.) Advances in Cryptology—EUROCRYPT 2021. Lecture Notes in Computer Science, vol. 12696, pp. 348–373. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_13.

23.

Beullens W.: Breaking Rainbow takes a weekend on a laptop. In: Advances in Cryptology—CRYPTO 2022. LNCS, Springer, Berlin (2022). https://eprint.iacr.org/2022/214.

24.

Bidoux L., Briaud P., Bros M., Gaborit P.: RQC revisited and more cryptanalysis for rank-based cryptography (2022). arXiv:2207.01410.

25.

Bruns W., Vetter U.: Determinantal Rings. LNCS, vol. 1327. Springer, Berlin (1988).

26.

Buss J.F., Frandsen G.S., Shallit J.O.: The computational complexity of some problems of linear algebra. J. Comput. Syst. Sci. 58(3), 572–596 (1999).MathSciNetCrossRefMATH

27.

Cabarcas D., Smith-Tone D., Verbel J.: Key recovery attack for ZHFE. In: Post-Quantum Cryptography 2017. LNCS, vol. 10346, pp. 289–308. Utrecht, The Netherlands (2017). https://doi.org/10.1007/978-3-319-59879-6_17.

28.

Chabaud F., Stern J.: The cryptographic security of the syndrome decoding problem for rank distance codes. In: Advances in Cryptology—ASIACRYPT 1996, vol. 1163, pp. 368–381. LNCS. Springer, Kyongju (1996).

29.

Courtois N.: Efficient zero-knowledge authentication based on a linear algebra problem MinRank. In: Advances in Cryptology—ASIACRYPT 2001. LNCS, vol. 2248, pp. 402–421. Springer, Gold Coast, Australia (2001), https://doi.org/10.1007/3-540-45682-1_24.

30.

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

31.

Cox D., Little J., O’Shea D.: Ideals, Varieties, and algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, New York. (2015). https://doi.org/10.1007/978-3-319-16721-3.

32.

Debris-Alazard T., Tillich J.P.: A polynomial attack on a NIST proposal: Ranksign, a code-based signature in rank metric. Preprint, IACR Cryptology ePrint Archive (2018). https://eprint.iacr.org/2018/339.pdf.

33.

Faugère J.C., Levy-dit-Vehel F., Perret L.: Cryptanalysis of Minrank. In: Wagner D. (ed.) Advances in Cryptology—CRYPTO 2008. LNCS, vol. 5157, pp. 280–296. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_16.

34.

Gabidulin E.M.: Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1), 3–16 (1985).MathSciNetMATH

35.

Gabidulin E.M., Paramonov A.V., Tretjakov O.V.: Ideals over a non-commutative ring and their applications to cryptography. In: Advances in Cryptology—EUROCRYPT’91. pp. 482–489. LNCS, No. 547. Brighton (1991).

36.

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

37.

Gaborit P., Schrek J., Zémor G.: Full cryptanalysis of the chen identification protocol. In: Post-Quantum Cryptography—4th International Workshop, PQCrypto 2011, Taipei, Taiwan, 29 November–2 December 2011. Proceedings, pp. 35–50 (2011). https://doi.org/10.1007/978-3-642-25405-5_3.

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., Zémor G.: New results for rank-based cryptography. In: Progress in Cryptology—AFRICACRYPT 2014. LNCS, vol. 8469, pp. 1–12 (2014).

40.

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

41.

Gaborit P., Hauteville A., Phan D.H., Tillich J.P.: Identity-based encryption from rank metric. In: Advances in Cryptology—CRYPTO (2017). https://doi.org/10.1007/978-3-319-63697-9_7.

42.

Goubin L., Courtois N.: Cryptanalysis of the TTM cryptosystem. In: Okamoto T. (ed.) Advances in Cryptology–ASIACRYPT 2000, vol. 1976, pp. 44–57. LNCS. Springer, Berlin (2000).CrossRef

43.

Hoffstein J., Pipher J., Silverman J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler J. (ed.) Algorithmic Number Theory, 3rd International Symposium, ANTS-III, Portland, OR, USA, 21–25 June 1998, Proceedings. LNCS, vol. 1423, pp. 267–288. Springer, Berlin (1998).

44.

Kipnis A., Shamir A.: Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Advances in Cryptology—CRYPTO’99. LNCS, vol. 1666, pp. 19–30. Springer, Santa Barbara (1999). https://doi.org/10.1007/3-540-48405-1.

45.

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.

46.

Loidreau P.: Asymptotic behaviour of codes in rank metric over finite fields. Des. Codes Cryptogr. 71(1), 105–118 (2014).MathSciNetCrossRefMATH

47.

Misoczki R., Tillich J.P., Sendrier N., Barreto P.S.L.M.: MDPC-McEliece: New McEliece variants from moderate density parity-check codes (2012). https://doi.org/10.1109/ISIT.2013.6620590, http://eprint.iacr.org/2012/409.

48.

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). https://doi.org/10.1023/A:1020369320078.MathSciNetCrossRefMATH

49.

Overbeck R.: A new structural attack for GPT and variants. In: Mycrypt. LNCS, vol. 3715, pp. 50–63 (2005).

50.

Petzoldt A., Chen M., Yang B., Tao C., Ding J.: Design principles for HFEv- based multivariate signature schemes. In: Iwata T., Cheon J.H. (eds.) Advances in Cryptology—ASIACRYPT 2015—21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, 29 November–3 December 2015, Proceedings, Part I. LNCS, vol. 9452, pp. 311–334. Springer, Cham (2015). https://doi.org/10.1007/978-3-662-48797-6_14.

51.

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

52.

Stern J.: A new identification scheme based on syndrome decoding. In: Stinson D. (ed.) Advances in Cryptology–CRYPTO’93, vol. 773, pp. 13–21. LNCS. Springer, Berlin (1993).CrossRef

53.

Tao C., Petzoldt A., Ding J.: Efficient key recovery for all HFE signature variants. In: Malkin T., Peikert C. (eds.) Advances in Cryptology—CRYPTO 2021—41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part I. Lecture Notes in Computer Science, vol. 12825, pp. 70–93. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_4.

54.

Verbel J., Baena J., Cabarcas D., Perlner R., Smith-Tone D.: On the complexity of “superdetermined” Minrank instances. In: Post-Quantum Cryptography 2019. LNCS, vol. 11505, pp. 167–186. Springer, Chongqing (2019). https://doi.org/10.1007/978-3-030-25510-7_10.

Title: Revisiting algebraic attacks on MinRank and on the rank decoding problem
Authors: Magali Bardet
Pierre Briaud
Maxime Bros
Philippe Gaborit
Jean-Pierre Tillich
Publication date: 19-07-2023
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 11/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01265-x

Springer Professional

Revisiting algebraic attacks on MinRank and on the rank decoding problem

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 11/2023

Improved attacks against reduced-round Whirlwind

Guest editorial: Special issue on Mathematics of Zero-Knowledge

Proving knowledge of isogenies: a survey

New method for combining Matsui’s bounding conditions with sequential encoding method

Ligero: lightweight sublinear arguments without a trusted setup

Constructions of column-orthogonal strong orthogonal arrays via matchings of bipartite graphs

Premium Partner