Recent progress in the security evaluation of multivariate public‐key cryptography
Abstract Multivariate public‐key cryptography (MPKC) is considered a leading candidate for post‐quantum cryptography (PQC). It is based on the hardness of the multivariate quadratic polynomial (MQ) problem, which is a problem of finding a solution to a system of quadratic equations over a finite fie...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2023-03-01
|
| Series: | IET Information Security |
| Online Access: | https://doi.org/10.1049/ise2.12092 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832559590483427328 |
|---|---|
| author | Yasuhiko Ikematsu Shuhei Nakamura Tsuyoshi Takagi |
| author_facet | Yasuhiko Ikematsu Shuhei Nakamura Tsuyoshi Takagi |
| author_sort | Yasuhiko Ikematsu |
| collection | DOAJ |
| description | Abstract Multivariate public‐key cryptography (MPKC) is considered a leading candidate for post‐quantum cryptography (PQC). It is based on the hardness of the multivariate quadratic polynomial (MQ) problem, which is a problem of finding a solution to a system of quadratic equations over a finite field. In this paper, we survey some recent progress in the security analysis of MPKC. Among various existing multivariate schemes, the most important one is the Rainbow signature scheme proposed by Ding et al. in 2005, which was later selected as a finalist in the third round of the PQC standardization project by the National Institute of Standards and Technology. Under the circumstances, some recent research studies in MPKC have focussed on the security analysis of the Rainbow scheme. In this paper, the authors first explain efficient algorithms for solving the MQ problem and the research methodology for estimating their complexity in MPKC. Then, the authors survey some recent results related to the security analysis of the Rainbow scheme. In particular, the authors provide a detailed description of the complexity analysis for solving the bi‐graded polynomial systems studied independently by Nakamura et al. and Smith‐Tone et al., and then expound the rectangular MinRank attack against Rainbow proposed by Beullens. |
| format | Article |
| id | doaj-art-e2a22f47cb884da69729ba40fd8d45b3 |
| institution | Kabale University |
| issn | 1751-8709 1751-8717 |
| language | English |
| publishDate | 2023-03-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Information Security |
| spelling | doaj-art-e2a22f47cb884da69729ba40fd8d45b32025-02-03T01:29:43ZengWileyIET Information Security1751-87091751-87172023-03-0117221022610.1049/ise2.12092Recent progress in the security evaluation of multivariate public‐key cryptographyYasuhiko Ikematsu0Shuhei Nakamura1Tsuyoshi Takagi2Institute of Mathematics for Industry Kyushu University Nishi‐ku Fukuoka JapanDepartment of Liberal Arts and Basic Sciences Nihon University Narashino Chiba JapanDepartment of Mathematical Informatics The University of Tokyo Bunkyo‐ku Tokyo JapanAbstract Multivariate public‐key cryptography (MPKC) is considered a leading candidate for post‐quantum cryptography (PQC). It is based on the hardness of the multivariate quadratic polynomial (MQ) problem, which is a problem of finding a solution to a system of quadratic equations over a finite field. In this paper, we survey some recent progress in the security analysis of MPKC. Among various existing multivariate schemes, the most important one is the Rainbow signature scheme proposed by Ding et al. in 2005, which was later selected as a finalist in the third round of the PQC standardization project by the National Institute of Standards and Technology. Under the circumstances, some recent research studies in MPKC have focussed on the security analysis of the Rainbow scheme. In this paper, the authors first explain efficient algorithms for solving the MQ problem and the research methodology for estimating their complexity in MPKC. Then, the authors survey some recent results related to the security analysis of the Rainbow scheme. In particular, the authors provide a detailed description of the complexity analysis for solving the bi‐graded polynomial systems studied independently by Nakamura et al. and Smith‐Tone et al., and then expound the rectangular MinRank attack against Rainbow proposed by Beullens.https://doi.org/10.1049/ise2.12092 |
| spellingShingle | Yasuhiko Ikematsu Shuhei Nakamura Tsuyoshi Takagi Recent progress in the security evaluation of multivariate public‐key cryptography IET Information Security |
| title | Recent progress in the security evaluation of multivariate public‐key cryptography |
| title_full | Recent progress in the security evaluation of multivariate public‐key cryptography |
| title_fullStr | Recent progress in the security evaluation of multivariate public‐key cryptography |
| title_full_unstemmed | Recent progress in the security evaluation of multivariate public‐key cryptography |
| title_short | Recent progress in the security evaluation of multivariate public‐key cryptography |
| title_sort | recent progress in the security evaluation of multivariate public key cryptography |
| url | https://doi.org/10.1049/ise2.12092 |
| work_keys_str_mv | AT yasuhikoikematsu recentprogressinthesecurityevaluationofmultivariatepublickeycryptography AT shuheinakamura recentprogressinthesecurityevaluationofmultivariatepublickeycryptography AT tsuyoshitakagi recentprogressinthesecurityevaluationofmultivariatepublickeycryptography |