On Ideal Lattices and Gröbner Bases

Abstract

In this paper, we draw a connection between ideal lattices and Gröbner bases in the multivariate polynomial rings over integers. We study extension of ideal lattices in $\mathbb{Z}[x]/⟨f⟩$ (Lyubashevsky \& Micciancio, 2006) to ideal lattices in $\mathbb{Z}[x_1,\dots ,x_n]/\mathfrak{a}$, the multivariate case, where $f$ is a polynomial in $\mathbb{Z}[X]$ and $\mathfrak{a}$ is an ideal in $\mathbb{Z}[x_1,\dots ,x_n]$. Ideal lattices in univariate case are interpreted as generalizations of cyclic lattices. We introduce a notion of multivariate cyclic lattices and we show that multivariate ideal lattices are indeed a generalization of them. We show that the fact that existence of ideal lattice in univariate case if and only if $f$ is monic translates to short reduced Gröbner basis (Francis \& Dukkipati, 2014) of $\mathfrak{a}$ is monic in multivariate case. We, thereby, give a necessary and sufficient condition for residue class polynomial rings over $\mathbb{Z}$ to have ideal lattices. We also characterize ideals in $\mathbb{Z}[x_1,\dots ,x_n]$ that give rise to full rank lattices.

The following paper in the arxiv is the longer version of the same paper: arXiv:1410.2011