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

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

CABOARA, MASSIMO;
2008-01-01

Abstract

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
2008
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/123721
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact