Group Action on Groebner Bases of Saturated Zero-Dimensional Binomial Ideals

Fully saturated zero-dimensional binomial ideals (lattice ideals) describe lattices on Zn that are of interest in cryptanalysis. Gr¨obner basis computation for these ideals are computationally very intensive. We sketch a modified version of Buchberger’s algorithm for lattice ideals that are closed with respect to a group action on their indeterminates. The main idea is to exploit the symmetries of such ideals to avoid performing S-polynomial reductions that are “equivalent” with respect to the group action. Using our techniques the number of S-polynomials to be considered can be reduced by a factor up to the order of the group