Analysis of partial key recovery attack on multivariate cryptographic transformations using rank systems
DOI:
https://doi.org/10.30837/rt.2022.2.209.06Keywords:
cryptosecurity, cryptanalysis, rank experiments, attack analysis, postquantum periodAbstract
The Rainbow signature scheme, proposed by Ding and Schmidt in 2005, is one of the oldest and most studied signature schemes in multidimensional cryptography. The Rainbow, based on the unbalanced Oil and Vinegar signature scheme, has the necessary cryptocurrency since 1999 with the right parameters. Interest in multivariate cryptography has increased in the last decade, as it is considered to be quantum-stable.
Cryptanalysis of the Rainbow and its predecessors was actively developed in the early 2000s. Attacks from this era include the MinRank attack, the HighRank attack, the Bill-Gilbert attack, the UOV agreement attack, and the Rainbow bandwidth attack. After 2008, cryptanalysis seemed to have stopped, until the Rainbow's participation in the NIST PQC project, which motivated the continuation of cryptanalysis. During the second round of NIST, Bardett and others proposed a new algorithm for solving the MinRank problem. This dramatically increased the effectiveness of MinRank's attack, although not enough to threaten the parameters provided to NIST. A less memory-intensive version of this algorithm was suggested by Baena et al. Perlner and Smith-Tone analyzed the Rainbow bandwidth attack in depth, which showed that the attack was more effective than previously thought. This prompted the Rainbow team to increase slightly the parameters for the third round. During the third round, Bellens introduced a new attack that reduced the Rainbow's security by 220 times for SL 1. The Rainbow team claimed that despite the new attacks, the Rainbow's parameters still met NIST requirement.
The purpose of this article is to present two new (partial) key recovery attacks on multivariate cryptographic transformations using rank systems.
References
Jintai Ding and Dieter Schmidt. Rainbow, a new multivariable polynomial signature scheme. In John Ioannidis, Angelos Keromytis, and Moti Yung, editors, ACNS 05, volume 3531 of LNCS, pages 164–175. Springer, Heidelberg, June 2005. 1.
Jacques Patarin. The oil and vinegar signature scheme. In Dagstuhl Workshop on Cryptography September, 1997, 1997. 1, 5.
Aviad Kipnis, Jacques Patarin, and Louis Goubin. Unbalanced oil and vinegar signature schemes. In Jacques Stern, editor, EUROCRYPT’99, volume 1592 of LNCS, pages 206–222. Springer, Heidelberg, May 1999. 1.
Aviad Kipnis and Adi Shamir. Cryptanalysis of the oil & vinegar signature scheme. In Hugo Krawczyk, editor, CRYPTO’98, volume 1462 of LNCS, pages 257–266. Springer, Heidelberg, August 1998. 1, 3, 4.
Bo-Yin Yang and Jiun-Ming Chen. Building secure tame-like multivariate public-key cryptosystems: The new TTS. In Colin Boyd and Juan Manuel Gonz ́alez Nieto, editors, ACISP 05, volume 3574 of LNCS, pages 518–531. Springer, Hedelberg, July 2005. 1.
Olivier Billet and Henri Gilbert. Cryptanalysis of Rainbow. In Roberto De Prisco and Moti Yung, editors, SCN 06, volume 4116 of LNCS, pages 336–347. Springer, Heidelberg, September 2006. 1
Louis Goubin and Nicolas Courtois. Cryptanalysis of the TTM cryptosystem. In Tatsuaki Okamoto, editor, ASIACRYPT 2000, volume 1976 of LNCS, pages 44–57. Springer, Heidelberg, December 2000. 1.
Jintai Ding, Bo-Yin Yang, Chia-Hsin Owen Chen, Ming-Shing Chen, and Chen-Mou Cheng. New differential-algebraic attacks and reparametrization of Rainbow. In Steven M. Bellovin, Rosario Gennaro, Angelos D. Keromytis, and Moti Yung, editors, ACNS 08, volume 5037 of LNCS, pages 242–257. Springer, Heidelberg, June 2008. 1, 2.
Magali Bardet, Maxime Bros, Daniel Cabarcas, Philippe Gaborit, Ray A. Perlner, Daniel Smith-Tone, Jean-Pierre Tillich, and Javier A. Verbel. Improvements of algebraic attacks for solving the rank decoding and MinRank problems. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part I, volume 12491 of LNCS, pages 507–536. Springer, Heidelberg, December 2020. 1, 2, 4, 5.
John Baena, Pierre Briaud, Daniel Cabarcas, Ray Perlner, Daniel Smith-Tone, and Javier Verbel. Improving support-minors rank attacks: applications to GeMSS and rainbow. Cryptology ePrint Archive, Report 2021/1677, 2021. https://eprint.iacr.org/2021/1677. 1
Ray Perlner and Daniel Smith-Tone. Rainbow band separation is better than we thought. Cryptology ePrint Archive, Report 2020/702, 2020. https://eprint.iacr.org/2020/702. 1
Ward Beullens. Improved cryptanalysis of UOV and rainbow. In Anne Canteaut and Fran ̧cois-Xavier Standaert, editors, EUROCRYPT 2021, Part I, volume 12696 of LNCS, pages 348–373. Springer, Heidelberg, October 2021. 1, 1, 1, 2, 2, 3, 4, 5 14 Ward Beullens.
Response to recent paper by Ward Beullens. https://troll.iis.sinica.edu.tw/by-publ/recent/response-ward.pdf, 2020. 1.
Daniel Lazard. Gr ̈obner bases, Gaussian elimination and resolution of systems of algebraic equations. In European Conference on Computer Algebra, pages 146– 156. Springer, 1983. 2.
Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir. Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In Bart Preneel, editor, EUROCRYPT 2000, volume 1807 of LNCS, pages 392–407. Springer, Heidelberg, May 2000. 2.
Wael Said Abdelmageed Mohamed, Jintai Ding, Thorsten Kleinjung, Stanislav Bulygin, and Johannes Buchmann. Pwxl: A parallel wiedemann-xl algorithm for solving polynomial equations over gf (2). In Conference on Symbolic Computation and Cryptography, page 89, 2010. 2.
Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, and Bo-Yin Yang. Solving quadratic equations with XL on parallel architectures. In Emmanuel Prouff and Patrick Schaumont, editors, CHES 2012, volume 7428 of LNCS, pages 356–373. Springer, Heidelberg, September 2012. 2, 5.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
