Paper 2024/528
The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences
Abstract
Determining the complexity of computing Gr\"{o}bner bases is an important problem both in theory and in practice, and for that the solving degree plays a key role. In this paper, we study the solving degrees for affine semi-regular sequences and their homogenized sequences. Some of our results are considered to give mathematically rigorous proofs of the correctness of methods for computing Gr\"{o}bner bases of the ideal generated by an affine semi-regular sequence. This paper is a sequel of the authors' previous work and gives additional results on the solving degrees and important behaviors of Gr\"obner basis computation. We also define the generalized degree of regularity for a sequence of homogeneous polynomials. For the ideal generated by the homogenization of an affine semi-regular sequence, we relate its generalized degree of regularity with its maximal Gr\"{o}bner basis degree (i.e., the solving degree for the homogenized sequence). The definition of a generalized (cryptographic) semi-regular sequence is also given, and it derives a new cryptographic assumption to estimate the security of cryptosystems. From our experimental observation, we raise a conjecture and some questions related to this generalized semi-regularity. These definitions and our results provide a theoretical formulation of (somehow heuristic) discussions done so far in the cryptographic community.
Note: 41 pages, Revised version (for example, we have added issues on complexity analysis and a generalization of contents of Subsection 2.3, see also Appendix A.3 - A.5), Accepted for presentation at Effective Methods in Algebraic Geometry (MEGA2024)
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Gröbner basessolving degreesemi-regular sequencesKoszul complexdegree of regularitymultivariate cryptography
- Contact author(s)
-
m-kudo @ fit ac jp
kazuhiro @ rikkyo ac jp - History
- 2024-09-23: last of 2 revisions
- 2024-04-04: received
- See all versions
- Short URL
- https://ia.cr/2024/528
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/528, author = {Momonari Kudo and Kazuhiro Yokoyama}, title = {The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/528}, year = {2024}, url = {https://eprint.iacr.org/2024/528} }