On Ideal Lattices and Gr\"obner Bases

In this paper, we draw a connection between ideal lattices and Gr"{o}bner bases in the multivariate polynomial rings over integers. We study extension of ideal lattices in $\mathbb{Z}[x]\mathrm{/}⟨f⟩$ (Lyubashevsky & Micciancio, 2006) to ideal lattices in $\mathbb{Z}[x_1,\dots ,x_n]\mathrm{/}\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"obner 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.