The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
다변량 공개 키 암호 시스템(MPKC)은 다변량 2차 방정식(MQ 문제)을 푸는 문제를 기반으로 구성됩니다. 다양한 다변량 체계 중에서 UOV는 NIST PQC 표준화 프로젝트의 최종 후보인 MAYO, QR-UOV 및 Rainbow와 같은 일부 서명 체계의 기초가 되므로 중요한 서명 체계입니다. 다변량 기법의 보안성을 분석하기 위해서는 특정 공격에 사용되는 다항방정식 체계에 대한 첫 번째 낙하 정도 또는 해결 정도를 분석해야 합니다. 첫 번째 낙하 정도 또는 해결 정도는 종종 시스템에 의해 생성된 이상의 힐베르트 계열과 관련이 있는 것으로 알려져 있습니다. 본 논문에서는 UOV 체계의 힐베르트 급수에 대해 연구하고, 보다 구체적으로는 UOV의 중심 지도에 사용된 2차 다항식에 의해 생성된 이념의 힐베르트 급수를 연구한다. 특히, 몇 가지 실험 결과를 이용하여 힐베르트 급수(Hilbert series)의 예측 공식을 도출합니다. 또한 이를 MAYO에 대한 화해 공격 분석에 적용한다.
Yasuhiko IKEMATSU
Kyushu University
Tsunekazu SAITO
NTT Social Informatics Laboratories
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Yasuhiko IKEMATSU, Tsunekazu SAITO, "Hilbert Series for Systems of UOV Polynomials" in IEICE TRANSACTIONS on Fundamentals,
vol. E107-A, no. 3, pp. 275-282, March 2024, doi: 10.1587/transfun.2023CIP0019.
Abstract: Multivariate public key cryptosystems (MPKC) are constructed based on the problem of solving multivariate quadratic equations (MQ problem). Among various multivariate schemes, UOV is an important signature scheme since it is underlying some signature schemes such as MAYO, QR-UOV, and Rainbow which was a finalist of NIST PQC standardization project. To analyze the security of a multivariate scheme, it is necessary to analyze the first fall degree or solving degree for the system of polynomial equations used in specific attacks. It is known that the first fall degree or solving degree often relates to the Hilbert series of the ideal generated by the system. In this paper, we study the Hilbert series of the UOV scheme, and more specifically, we study the Hilbert series of ideals generated by quadratic polynomials used in the central map of UOV. In particular, we derive a prediction formula of the Hilbert series by using some experimental results. Moreover, we apply it to the analysis of the reconciliation attack for MAYO.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2023CIP0019/_p
부
@ARTICLE{e107-a_3_275,
author={Yasuhiko IKEMATSU, Tsunekazu SAITO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Hilbert Series for Systems of UOV Polynomials},
year={2024},
volume={E107-A},
number={3},
pages={275-282},
abstract={Multivariate public key cryptosystems (MPKC) are constructed based on the problem of solving multivariate quadratic equations (MQ problem). Among various multivariate schemes, UOV is an important signature scheme since it is underlying some signature schemes such as MAYO, QR-UOV, and Rainbow which was a finalist of NIST PQC standardization project. To analyze the security of a multivariate scheme, it is necessary to analyze the first fall degree or solving degree for the system of polynomial equations used in specific attacks. It is known that the first fall degree or solving degree often relates to the Hilbert series of the ideal generated by the system. In this paper, we study the Hilbert series of the UOV scheme, and more specifically, we study the Hilbert series of ideals generated by quadratic polynomials used in the central map of UOV. In particular, we derive a prediction formula of the Hilbert series by using some experimental results. Moreover, we apply it to the analysis of the reconciliation attack for MAYO.},
keywords={},
doi={10.1587/transfun.2023CIP0019},
ISSN={1745-1337},
month={March},}
부
TY - JOUR
TI - Hilbert Series for Systems of UOV Polynomials
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 275
EP - 282
AU - Yasuhiko IKEMATSU
AU - Tsunekazu SAITO
PY - 2024
DO - 10.1587/transfun.2023CIP0019
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E107-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2024
AB - Multivariate public key cryptosystems (MPKC) are constructed based on the problem of solving multivariate quadratic equations (MQ problem). Among various multivariate schemes, UOV is an important signature scheme since it is underlying some signature schemes such as MAYO, QR-UOV, and Rainbow which was a finalist of NIST PQC standardization project. To analyze the security of a multivariate scheme, it is necessary to analyze the first fall degree or solving degree for the system of polynomial equations used in specific attacks. It is known that the first fall degree or solving degree often relates to the Hilbert series of the ideal generated by the system. In this paper, we study the Hilbert series of the UOV scheme, and more specifically, we study the Hilbert series of ideals generated by quadratic polynomials used in the central map of UOV. In particular, we derive a prediction formula of the Hilbert series by using some experimental results. Moreover, we apply it to the analysis of the reconciliation attack for MAYO.
ER -