IEICE TRANSACTIONS on Fundamentals
Hilbert Series for Systems of UOV Polynomials
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.3 pp.275-282
- Publication Date
- 2024/03/01
- Publicized
- 2023/09/11
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2023CIP0019
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
Authors
Yasuhiko IKEMATSU
Kyushu University
Tsunekazu SAITO
NTT Social Informatics Laboratories
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
