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
Criptossistemas multivariados de chave pública (MPKC) são construídos com base no problema de resolução de equações quadráticas multivariadas (problema MQ). Entre vários esquemas multivariados, o UOV é um esquema de assinatura importante, uma vez que está subjacente a alguns esquemas de assinatura, como MAYO, QR-UOV e Rainbow, que foi finalista do projeto de padronização PQC do NIST. Para analisar a segurança de um esquema multivariado, é necessário analisar o primeiro grau de queda ou grau de resolução do sistema de equações polinomiais utilizado em ataques específicos. Sabe-se que o primeiro grau de queda ou grau de resolução muitas vezes está relacionado à série de Hilbert do ideal gerado pelo sistema. Neste artigo, estudamos a série de Hilbert do esquema UOV e, mais especificamente, estudamos a série de ideais de Hilbert gerada por polinômios quadráticos utilizados no mapa central do UOV. Em particular, derivamos uma fórmula de previsão da série de Hilbert usando alguns resultados experimentais. Além disso, aplicamo-lo à análise do ataque de reconciliação à 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.
Copiar
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
Copiar
@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},}
Copiar
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 -