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

Full description

Saved in:
Bibliographic Details
Main Authors: Yasuhiko Ikematsu, Shuhei Nakamura, Tsuyoshi Takagi
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