Paper 2022/987

A Signature-Based Gröbner Basis Algorithm with Tail-Reduced Reductors (M5GB)

Manuel Hauke, Graz University of Technology
Lukas Lamster, Graz University of Technology
Reinhard Lüftenegger, Graz University of Technology
Christian Rechberger, Graz University of Technology
Abstract

Gröbner bases are an important tool in computational algebra and, especially in cryptography, often serve as a boilerplate for solving systems of polynomial equations. Research regarding (efficient) algorithms for computing Gröbner bases spans a large body of dedicated work that stretches over the last six decades. The pioneering work of Bruno Buchberger in 1965 can be considered as the blueprint for all subsequent Gröbner basis algorithms to date. Among the most efficient algorithms in this line of work are signature-based Gröbner basis algorithms, with the first of its kind published in the late 1990s by Jean-Charles Faugère under the name $\texttt{F5}$. In addition to signature-based approaches, Rusydi Makarim and Marc Stevens investigated a different direction to efficiently compute Gröbner bases, which they published in 2017 with their algorithm $\texttt{M4GB}$. The ideas behind $\texttt{M4GB}$ and signature-based approaches are conceptually orthogonal to each other because each approach addresses a different source of inefficiency in Buchberger's initial algorithm by different means. We amalgamate those orthogonal ideas and devise a new Gröbner basis algorithm, called $\texttt{M5GB}$, that combines the concepts of both worlds. In that capacity, $\texttt{M5GB}$ merges strong signature-criteria to eliminate redundant S-pairs with concepts for fast polynomial reductions borrowed from $\texttt{M4GB}$. We provide proofs of termination and correctness and a proof-of-concept implementation in C++ by means of the Mathic library. The comparison with a state-of-the-art signature-based Gröbner basis algorithm (implemented via the same library) validates our expectations of an overall faster runtime for quadratic overdefined polynomial systems that have been used in comparisons before in the literature and are also part of cryptanalytic challenges.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Gröbner basis signature-based M4GB tail-reduction algebraic analysis
Contact author(s)
hauke @ math tugraz at
lukas lamster @ iaik tugraz at
reinhard lueftenegger @ iaik tugraz at
christian rechberger @ iaik tugraz at
History
2022-08-03: approved
2022-08-02: received
See all versions
Short URL
https://ia.cr/2022/987
License
Creative Commons Attribution-NonCommercial-ShareAlike
CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2022/987,
      author = {Manuel Hauke and Lukas Lamster and Reinhard Lüftenegger and Christian Rechberger},
      title = {A Signature-Based Gröbner Basis Algorithm with Tail-Reduced Reductors ({M5GB})},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/987},
      year = {2022},
      url = {https://eprint.iacr.org/2022/987}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.