Paper 2024/086
On Hilbert-Poincaré series of affine semi-regular polynomial sequences and related Gröbner bases
Abstract
Gröbner bases are nowadays central tools for solving various problems in commutative algebra and algebraic geometry. A typical use of Gröbner bases is is the multivariate polynomial system solving, which enables us to construct algebraic attacks against post-quantum cryptographic protocols. Therefore, the determination of the complexity of computing Gröbner bases is very important both in theory and in practice: One of the most important cases is the case where input polynomials compose an (overdetermined) affine semi-regular sequence. The first part of this paper aims to present a survey on Gröbner basis computation and its complexity. In the second part, we shall give an explicit formula on the (truncated) Hilbert-Poincaré series associated to the homogenization of an affine semi-regular sequence. Based on the formula, we also study (reduced) Gröbner bases of the ideals generated by an affine semi-regular sequence and its homogenization. Some of our results are considered to give mathematically rigorous proofs of the correctness of methods for computing Gröbner bases of the ideal generated by an affine semi-regular sequence.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Mathematical Foundations for Post-Quantum Cryptography, Mathematics for Industry Series, Springer
- Keywords
- Gröbner basesHilbert-Poincaré seriessolving degreedegree of regularitypost-quantum cryptography
- Contact author(s)
-
m-kudo @ fit ac jp
kazuhiro @ rikkyo ac jp - History
- 2024-03-03: revised
- 2024-01-19: received
- See all versions
- Short URL
- https://ia.cr/2024/086
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/086,
author = {Momonari Kudo and Kazuhiro Yokoyama},
title = {On Hilbert-Poincaré series of affine semi-regular polynomial sequences and related Gröbner bases},
howpublished = {Cryptology ePrint Archive, Paper 2024/086},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/086}},
url = {https://eprint.iacr.org/2024/086}
}
