Paper 2024/528

The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences

Momonari Kudo, Fukuoka Institute of Technology
Kazuhiro Yokoyama, Rikkyo University
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.