The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -