On Ideal Lattices and Gr\"{o
In this paper, we draw a connection between ideal lattices and Gr\"{obner bases in the multivariate polynomial rings over integers. We study extension of ideal lattices in $\mathbb{Z[x]/\langle f \rangle$ (Lyubashevsky \& Micciancio, 2006) to ideal lattices in $\mathbb{Z[x_1,\ldots,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,\ldots,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,\ldots,x_n]$ that give rise to full rank lattices.
1409.7788.tex
\documentclass[11pt,a4paper,reqno,twoside]{amsart}

%\documentclass[conference]{IEEEtran}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{xspace}
\usepackage{amsmath}
\usepackage{setspace}
\usepackage{amscd}
\usepackage{natbib}
\usepackage{setspace}
\usepackage{enumerate}
\usepackage[english]{babel}
\usepackage{tikz}
\usetikzlibrary{matrix}
\tikzstyle{l} = [draw, -latex,thick]

  \parskip 1.0ex
  
  
\newtheorem{theorem}{Theorem}[section]
       \newtheorem{lemma}[theorem]{Lemma}
       \newtheorem{proposition}[theorem]{Proposition}
       \newtheorem{corollary}[theorem]{Corollary}
    \newtheorem{definition}[theorem]{Definition}
       \newtheorem{remark}[theorem]{Remark}
       \newtheorem{claim}[theorem]{Claim}     
       \newtheorem{example}[theorem]{Example}  
       
\newcommand{\Lm}{\mathrm{LM}}%for leading term
\newcommand{\LmPrec}{{\mathrm{LM}}_{\prec}}%leading term including the
				%default notation of term order
\newcommand{\Lt}{\mathrm{LT}}%for leading term
\newcommand{\LtPrec}{\mathrm{LT}_{\prec}}%leading term including the
				%default notation of term order
\newcommand{\PolRing}{k[x_{1},\ldots,x_{n}]}%default notation of
				%polynomial ring
\newcommand{\SetOfAllMonomials}{{\mathbb{Z}}_{\geq 0}^{n}}

\newcommand{\Kernel}{\mathrm{ker}}%for leading term
\newcommand{\Image}{\mathrm{im}}%for leading term

%=====================================
%% Some pretty etc.'s, etc...
\newcommand{\cf}{{\em cf.}\xspace }
\newcommand{\eg}{{\em e.g.},\xspace }
\newcommand{\ie}{{\em i.e.},\xspace }
\newcommand{\etal}{{\em et al.}\ }
\newcommand{\etc}{{\em etc.}\@\xspace}
%=====================================
%Residue Class Ring is the same as Quotient Ring and Factor Ring.

\begin{document}
%\doublespacing
\title[On Ideal lattices and Gr\"{o}bner Bases]
{On Ideal Lattices and Gr\"{o}bner Bases}
\author[Maria Francis and  Ambedkar Dukkipati]{Maria Francis and  Ambedkar Dukkipati}
\email{mariaf@csa.iisc.ernet.in \\ ad@csa.iisc.ernet.in}
\address{Department of Computer Science \& Automation\\Indian Institute of Science, Bangalore - 560012}
\large
%======================Abstract=================
\maketitle
\begin{abstract}  
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]/\langle f \rangle$ (Lyubashevsky \& Micciancio, 2006) to ideal
lattices in  $\mathbb{Z}[x_1,\ldots,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,\ldots,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,\ldots,x_n]$ that give 
rise to full rank lattices.  
\end{abstract}
%\maketitle
%\vspace{-2ex}
%================================================
\section{Introduction}
\label{Introduction} 
\noindent After \cite{Ajtai:1996:Znascryptoprimitive} built functions
that on an average generated hard instances of standard lattice
problems, research progressed in the direction of building
cryptographic primitives based on them. 
The fundamental challenge to this direction of research was describing
lattices as $n \times n$ integer matrices since that meant the size of
the key and the computation time of the cryptographic functions will 
be atleast quadratic in $n$. \cite{Micciancio:2002:CyclicLattices}
used a class of lattices called `cyclic lattices' to build certain
efficient one-way functions called generalized compact knapsack
functions.  

Lattices that are closed under cyclic shifts are called cyclic
lattices and these are integer lattices that are also ideals in
$\mathbb{Z}[x]/\langle x^n -1 \rangle$.
The advantage of cyclic lattices is that they have a compact
representation and therefore the time taken for  
these functions is almost linear in $n$
\citep{Micciancio:2002:CyclicLattices}.
But one way functions are of
theoretical interest and can not be used to build useful  
cryptographic primitives
\citep{Lyubashevsky:2006:Ideallatticefirstdef}.
In \citep{Lyubashevsky:2006:Ideallatticefirstdef} a new class of
lattices called `ideal lattices' were introduced and efficient
collision resistant hash functions were designed using them.

Ideal lattices are ideals in a quotient ring $\mathbb{Z}[x]/\langle f
\rangle$, for any monic polynomial $f \in \mathbb{Z}[x]$, that are also
lattices. This is due to the fact that $\mathbb{Z}[x]/\langle f
\rangle$ is isomorphic to ${\mathbb{Z}}^{N}$ if and only if $f$ is
monic. In fact, in cryptographic applications the choice of
$f$ is further  restricted to irreducible polynomials. Over the years,
ideal lattices have been used to build several  
cryptographic primitives that include digital signatures \citep{Micciancio:2008:EfficientSign}, hash functions \citep{Lyubashevsky:2006:Ideallatticefirstdef} and  identification schemes \citep{Lyubashevsky:2008:Ideallattice}.

On the other hand, any extension of solutions of problems from one
variable case to 
multivariate case, in particular, in algebra, have led to important
theories, an  example being the theory of Gr\"obner bases introduced
by \cite{Buchberger:1965:thesis},
%A direct extension from $A[x]$ to
%$A[x_1,\ldots,x_n]$, where $A$ is a  Noetherian, commutative ring,
%fails often as even basic algorithms like the division algorithm do
%not give unique results for different order of inputs.
that
has become a standard tool in algorithmic aspects of commutative
algebra and algebraic geometry. The reason is computing Gr\"{o}bner
bases of ideals in multivariate case is enough to extend solutions of
various problems from univariate to multivariate case. 
%When we consider
%the Gr\"obner basis for a set of multivariate polynomials instead of
%the set of polynomials itself, extending algorithmic techniques from
%the univariate polynomial ring to the corresponding multivariate case
%becomes feasible.
In this paper, we study ideal lattices from an
algebraic point of view, and show how Gr\"obner bases play a role in the
study of extending ideal lattices from univariate case to multivariate
case. In fact, we give a necessary and sufficient condition for residue
class polynomial rings over $\mathbb{Z}$ to have ideal lattices, in
terms of `short reduced Gr\"{o}bner bases' that was introduced
in~\citep{FrancisDukkipati:2013:freeZmodule}. 

%Ideal
%lattices in $\mathbb{Z}[x]/\langle f \rangle$ require that the
%generator of the ideal in $\mathbb{Z}[x]$ , $f$ to be monic. Can we
%directly extend the concept of ideal lattices to $
%\mathbb{Z}[x_1,\ldots,x_n]$ by considering ideals with monic
%generators? As with everything in the multivariate case we need to
%compute the Gr\"obner basis of the ideal. In fact, we show that we
%need to compute the `short reduced Gr\"obner basis' of the ideal
%defined in \citep{FrancisDukkipati:2013:freeZmodule} and check if it
%is monic. Here, we show how certain results associated with ideal
%lattices in the one variable case can be extended to the corresponding
%multivariate case.


% \noindent Ideal lattices have gained prominence recently in cryptography 
% because of the hardness of certain standard lattice problems like the shortest vector problem (SVP) in these structures
% \citep{ Micciancio:2002:CyclicLattices,Lyubashevsky:2006:Ideallatticefirstdef,Lyubashevsky:2008:Ideallattice,Micciancio:2008:EfficientSign}. 
% Ideal lattices are integer lattices with an additional algebraic structure that they are ideals as well in $\mathbb{Z}[x]/\langle f \rangle$, 
% where $f$ is a monic polynomial. 
%The reason for interest in these str in cryptography is because integer lattices have been used  in recent times as a cryptographic primitive \citep{Ajtai:1996:Znascryptoprimitive}.\\
% Cyclic lattices are defined as integer lattices that are ideals in $\mathbb{Z}[x]/\langle x^n -1\rangle$ for some $n \in \mathbb{N}$ \citep{Micciancio:2002:CyclicLattices}. 
% They are `cyclic' since for every $v$ in the lattice, the cyclic shift of its elements is also in the lattice. 
\subsection*{Contributions}
%In this paper, we study ideal lattices from an algebraic point of
%view, in particular we study how to extend ideal lattices to a
%multivariate case.
In this paper, we study ideal lattices in the multivariate case.  That
is, given an ideal $\mathfrak{a}$ in $\mathbb{Z}[x_1,\ldots,x_n]$ we
study cases for which ideals in
$\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ are also lattices. As in the
univariate counterpart, we show that ideal lattices in the
multivariate case are also a generalization of introduced objects called
multivariate cyclic lattices.  
%In this paper, we study cyclic lattices, locate ideal lattices in
%$\mathbb{Z}[x_1,\ldots,x_n]$ and determine a characterization for
%full rank lattices.  
%Ideal lattices  in $\mathbb{Z}[x]$ are a generalization of cyclic
%lattices and we show that in $\mathbb{Z}[x_1,\ldots,x_n]$ too ideal
%lattices can be viewed as a generalization of cyclic lattices but the
%cyclicity will have to be viewed in $n$ dimensions.
We show that ideal lattices exists only when the residue class
polynomial ring over $\mathbb{Z}$ is a free $\mathbb{Z}$-module, for
which we give a characterization based on short reduced Gr\"obner
bases. Short reduced Gr\"obner bases were introduced
in~\citep{FrancisDukkipati:2013:freeZmodule} to characterize free
$A$-modules $A[x_1,\ldots,x_n]/\mathfrak{a}$, where $A$ is a
Noetherian ring and $\mathfrak{a}$ is an ideal in
$A[x_1,\ldots,x_n]$. 
%Ideal lattices in $\mathbb{Z}[x]$ are seen as a generalization of cyclic lattices. We study cyclic lattices in  $\mathbb{Z}[x_1,\ldots,x_n]$ and also show how the notion of cyclic changes in the multivariate case.
%When we extend ideal lattices to multiple variables, the first question we need to address is 
%if all ideals in  $\mathbb{Z}[x_1,\ldots,x_n]$ give rise to ideal lattices. We see that freeness of the quotient ring $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ determines if ideals in the $\mathbb{Z}$-module
%are lattices. Therefore, determining if the residue class polynomial ring, $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ is free or not  becomes the first step in identifying ideal lattices.
%We also prove that  if the polynomial ring $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ has torsion elements then it can never have ideal lattices. 
For the construction of many cryptographic primitives full rank lattices are essential and we derive the condition for an ideal lattice in the multivariate case to be a full rank lattice. We also give an example
of a class of binomial ideals in $\mathbb{Z}[x_1,\ldots,x_n]$,  where the residue class polynomial ring gives rise to full rank integer lattices.
% If the $\mathbb{Z}$-module, $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ is finitely generated
% and free we prove that all ideals in the quotient ring are lattices. 
% We also show that if the polynomial ring $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ has torsion elements then it can never have ideal lattices. 
% For the construction of many cryptographic primitives full rank lattices are essential and we derive the condition for an ideal lattice in the multivariate case to be a full rank lattice. We also give an example
% of a class of binomial ideals in $\mathbb{Z}[x_1,\ldots,x_n]$ where the residue class polynomial ring gives rise to full rank integer lattices.
%The rest of the paper is organized as follows: 
\subsection*{Outline of the paper}The rest of the paper is organized as follows. 
In Section~\ref{Preliminaries}, we look at preliminaries relating to lattices and ideal lattices. 
In Section~\ref{cycliclattices}, we study cyclic lattices in the multivariate case. 
In Section~\ref{ideallattices}, we prove that only free and finitely generated $\mathbb{Z}$-modules have ideal lattices. 
Finally, we give a characterization for ideal lattices to be full rank in Section~\ref{fullrank}.
% In the next section, Section ~\ref{canonicalrep}, we use Gr\"obner basis
%techniques to arrive at a canonical representation of the $\mathbb{Z}$-module, $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$. Using this, we arrive at an isomorphic direct sum of its invariant factors given by the structure theorem.  In the following section, Section ~\ref{Characterization}, we give the the condition that is necessary and sufficient for the quotient ring to
%be isomorphic to an integer lattice. IFor that first we briefly discuss the definition of reduced Gr\"obner basis over a ring as described in \cite{Pauer:2007:Grobnerbasisrings}. 
% Pauer's definition ensures the construction of a unique reduced Gr\"obner basis for the ideal which helps us arrive at the characterization. We give an example of an ideal, lattice ideal, 
% for which the associated quotient ring is free. We then give the Macaulay Basis Theorem for rings.
%==========================================
\section{Background \& Preliminaries}
\label{Preliminaries}
%\subsection{Integer Lattices}
Let $\Bbbk$ be a field, $A$ a Noetherian commutative ring,
$\mathbb{Z}$ the ring of integers and $\mathbb{N}$ the set of positive
integers including zero. Let $\mathbb{R}^m$ be the $m$-dimensional
Euclidean space.

A polynomial ring in an indeterminate $x$ is denoted by $A[x]$. In the
multivarite case polynomial ring in indeterminates $x_1,\ldots,x_n$
over $A$ is denoted by  $A[x_1,\ldots,x_n]$.  
A monomial $x_{1}^{\alpha_{1}} \ldots x_{n}^{\alpha_{n}}$ in
$x_1,\ldots, x_n$ is denoted by   $x^{\alpha}$,
where  $\alpha\in {\mathbb{Z}}_{\ge 0}^n$.
If an ideal $\mathfrak{a}$
in $A[x_1,\ldots,x_n]$ is generated by
$f_{1},\ldots, f_{s} \in A[x_1,\ldots,x_n]$
then we write
$\mathfrak{a}= \langle f_{1},\ldots, f_{s} \rangle$. 

%We assume that there is a monomial order $\prec$ on the monomials in the indeterminates %$x_{1},\ldots,x_{n}$. 
%With respect to this monomial order, we have the leading monomial ($\mathrm{lm}_\prec$), leading %coefficient ($\mathrm{lc}_\prec$), leading term ($\mathrm{lt}_\prec$) and degree of a polynomial %($\mathrm{deg}_\prec$), 
%where $\mathrm{lt}_\prec(f) = \mathrm{lc}_\prec(f)\mathrm{lm}_\prec(f)$ and $\mathrm{deg}_\prec(f) %= \mathrm{deg}_\prec(\mathrm{lm}_\prec(f))$ in $A[x_{1},\ldots,x_{n}]$. 
%With this notation, the leading term ideal (or initial ideal) of a set
%$S \subseteq A[x_{1},\ldots,x_{n}]$, is  $\langle\mathrm{lt}_\prec(S)
%\rangle = \langle \{\mathrm{lt}_\prec(f) \mid f \in S \} \rangle$.

Now we recall some preliminaries on lattices. For a
good exposition one can refer to
\citep{Micciancio:2002:LatticesCrypto}.  
%\subsection{Lattices}
%Since this paper is about ideals in residue class polynomial rings over $\mathbb{Z}$ that are integer lattices as well, we give some basic information about lattices \citep{Micciancio:2002:LatticesCrypto}.
\begin{definition}
A lattice in $\mathbb{R}^m$ is the set 
\begin{displaymath}
 \mathcal{L}(b_1,\ldots,b_n) = \{\sum_{i=1}^{n} x_ib_i \mid x_i \in \mathbb{Z}\}
\end{displaymath}
of all integral combinations of $n$ linearly independent vectors $b_1, \ldots, b_n$ in $\mathbb{R}^m (m\ge n)$.
\end{definition}
The integers $n$ and $m$ are called the rank and dimension of the
lattice, respectively. The sequence of vectors $b_1, \ldots, b_n$ is
called a lattice basis. When $n=m$, we say that $\mathcal{L}$ is full
rank or full dimensional. 
 An example of $n$-dimensional lattice is the set $\mathbb{Z}^n$ of 
all vectors with integral coordinates. In sequel, whenever we mention
lattices we mean integer lattices,  lattices where the basis vectors
have integer coordinates.   
Integer lattices are additives subgroups of $\mathbb{Z}^N$, $N \in
\mathbb{N}$.    

An ideal lattice\footnote{We feel that the definition given in
\citep{Lyubashevsky:2006:Ideallatticefirstdef} is not mathematically accurate which
reads as the following. \textit{An
ideal lattice is an integer lattice $\mathcal{L} \subseteq
\mathbb{Z}^N$ such that it is also an ideal in 
$\mathbb{Z}[x]/ \langle f \rangle$, i.e.  $\mathcal{L} = \{g \mod  f \mid g \in
\mathfrak{A}\}$ for some monic polynomial $f \in \mathbb{Z}[x]$ of
degree $N$ and ideal $\mathfrak{A} \subseteq \mathbb{Z}[x]/ \langle f
\rangle$.}} 
%endfootnote
is an integer lattice $\mathcal{L} \subseteq \mathbb{Z}^N$ that is also an
ideal in $\mathbb{Z}[x]/ \langle f \rangle$ for some monic polynomial
$f\in \mathbb{Z}[x]$.   
We now formally define ideal lattices in one variable.
%Definition:Ideal Lattice in univariate case
\begin{definition}
Given a monic polynomial  $f\in \mathbb{Z}[x]$,    
an ideal lattice is an integer lattice $\mathcal{L} \subseteq
\mathbb{Z}^N$ such that it is isomorphic, as a
$\mathbb{Z}$-module, to an ideal $\mathfrak{A}$ in $\mathbb{Z}[x]/
\langle f \rangle$. 
\end{definition}
The following $\mathbb{Z}$-module homomorphism between $\mathbb{Z}[x]/\langle f \rangle$ and $\mathbb{Z}^N$, where $f$ is a monic polynomial of degree $N$, further elucidates the definition of ideal lattices.
\begin{align*} 
 \psi :  \mathbb{Z}[x]/\langle f \rangle &\longrightarrow \mathbb{Z}^N \\
         \sum\limits_{i=0}^{N-1} a_i x^{i} + \langle f \rangle &\longmapsto (a_0 , \cdots, a_{N-1}).
\end{align*}
Clearly, $\psi$ is an isomorphism that implies all
$\mathbb{Z}$-modules (including ideals) in $\mathbb{Z}[x]/\langle f
\rangle$ are isomorphic to sublattices (subgroups) of $\mathbb{Z}^N$.  
Therefore,  all ideals in $\mathbb{Z}[x]/\langle f \rangle$ are ideal
lattices. The main aim of this paper is to extend the concept of ideal
lattices to the multivariate case. 

%=================================================
\section{Multivariate Cyclic Lattices}
\label{cycliclattices}
%Initially, ideal lattices in $\mathbb{Z}[x]$ were built as a generalization of cyclic lattices \citep{Lyubashevsky:2006:Ideallatticefirstdef}. 
%In this section, we see how cyclic lattices can be extended to a multivariate case.
%Let us examine the definition of cyclic lattices in $\mathbb{Z}[x]$.
Before we look into the multivariate case we recall the definition of cyclic
lattices. 
\begin{definition}\label{cycliclatticesdef1}
 A set $\mathcal{L}$ in $\mathbb{Z}^N$ is a cyclic lattice
\begin{enumerate}[(i)]
\item for all $v,w \in \mathcal{L}$, $v+w$ is also in $\mathcal{L}$,
\item for all $v \in \mathcal{L}$, $-v$ is also in $\mathcal{L}$, and
\item for all $v \in \mathcal{L}$, a cyclic shift of $v$ is also in $\mathcal{L}$.
\end{enumerate}
\end{definition}
One can easily verify the following fact.
\begin{lemma}\label{cycliclatticesdef2}
  A set $\mathcal{L}$ in $\mathbb{Z}^N$ is a cyclic lattice if $\mathcal{L}$ is an ideal in $\mathbb{Z}[x]/\langle x^N-1 \rangle$. 
\end{lemma}
%The first two properties are taken care of since the structure is a subring. 
%The third property is satisfied because of the absorption property of
%the ideal (for all $v$ in the ideal $x.v$ is also in the ideal) and
%because we have quotiented it with $\langle x^n-1 \rangle$.
%Now we generalize cyclic lattices to the multivariate case by
%describing the cylicity in ideals, which are also lattices, in
Now consider 
$\mathbb{Z}[x_1,\ldots,x_n]/\langle {x_1}^{r_1} - 1,{x_2}^{r_2} - 1,\cdots, {x_n}^{r_n} - 1\rangle $, 
for some 
$r_{1},\ldots,r_{n} \in \mathbb{N}$. Let $\mathfrak{a} = \langle {x_1}^{r_1} - 1,\cdots, {x_n}^{r_n} - 1\rangle$ and $r_1 \times r_2 \times \cdots \times r_n = N$. We have $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ is a free $\mathbb{Z}$-module, isomorphic to ${\mathbb{Z}}^{N}$ with
$\mathcal{B} = \{{x_1} ^{\alpha_1}\ldots {x_n} 
^{\alpha_n} + \mathfrak{a}, \alpha_k \in \{0,\ldots,{r_k}-1\}\}$ as
a $\mathbb{Z}$-module basis. Given an element of the residue class polynomial ring,  
\begin{displaymath} 
\sum_{j=1}^N a_{(\alpha_{1j},\ldots,\alpha_{nj})}{x_1}
 ^{\alpha_{1j}}\ldots {x_n} ^{\alpha_{nj}} + \mathfrak{a},
 \end{displaymath}
 where
 $\alpha_{kj} \in \{0,\ldots, {r_k}-1\}$  and
 $a_{(\alpha_{1j},\ldots,\alpha_{nj})} \in \mathbb{Z}$, one can
 represent it using a tensor, $\mathcal{A} \in
 \mathbb{Z}^{r_1\times\cdots\times r_n}$ such that  
\begin{equation*}
\mathcal{A}_{i_1, \ldots, i_n} = a_{(i_1 -1, \ldots, i_n - 1)},
\end{equation*}
where ${A}_{i_1, \ldots, i_n}$ denotes $(i_1, \ldots, i_n)$ element in the tensor 
$\mathcal{A}$.  

Now consider $\mathbb{Z}^{N}$ and suppose $r_{1},\ldots,r_{n} \in \mathbb{N}$ such that 
$r_1 \times r_2 \times \cdots \times r_n = N$. Given a lattice 
$\mathcal{L} \subseteq \mathbb{Z}^N$ where 
$ \mathbb{Z}^N = \mathbb{Z} ^{r_1 \times \cdots \times r_n}$, 
it is easy to see that a one-to-one correspondence exists between a vector in 
$\mathcal{L}$ and a tensor in $\mathbb{Z} ^{r_1 \times \cdots \times r_n}$.

Let $\mathcal{A}$ be a tensor in $\mathbb{Z} ^{r_1 \times \cdots \times r_n} $.  
We  define a $(n-1) ^\text{\tiny{th}}$ order tensor  for each 
$r_i \in \{1,\ldots,n\}$ and denote it as $A_{i}(j)$ where 
$A_{i}(j) \in \mathbb{Z} ^{r_1 \times r_2 \times \cdots \times r_{i-1} \times r_{i+1} \times \cdots \times r_n}$.  
We have,
\begin{displaymath}
A_{i}(j)_{(k_1,\ldots,k_{i-1},k_{i+1},\ldots,k_n)} = \mathcal{A} _{(k_1,\ldots,k_{i-1},j,k_{i+1},\ldots,k_n)}, \hspace{5pt} j\in \{0,\ldots, r_i - 1\}.
\end{displaymath} 
%Note that $A_{i}(j)$ is a $(n-1)
%^\text{\tiny{th}}$ order tensor corresponding to the value $x_i =
%j$ and $A_{i}(j+1)$ tensor contains the coefficients of the basis
%elements obtained by multiplying the basis elements corresponding to
%$A_{i}(j)$ with $x_i$.  
We construct the following ordered set of $(n-1)^ \text{\tiny{th}}$ order tensors for each $r_i \in \{1,\ldots,n\}$,
\begin{displaymath}
 \mathcal{A}_{i} = (A_{i}(0), A_{i}(1), \cdots, A_{i}(r_i - 1)).
\end{displaymath}
Using this set, we introduce the notion of multivariate cyclic shifts. 
%They are defined for each $i \in \{1,\ldots,n\}$. 
\begin{definition}
Let $\mathcal{L} \subseteq \mathbb{Z}^N = \mathbb{Z} ^{r_1 \times \cdots \times r_n}$ be a lattice and $\mathcal{A} \in  \mathbb{Z} ^{r_1 \times \cdots \times r_n}$, a tensor in $\mathcal{L}$. The ${i}^{\mathrm{th}}$-multivariate cyclic shift of $\mathcal{A}$, $\sigma_{i}(\mathcal{A})$ is a cyclic shift of elements in the ordered set, $\mathcal{A}_{i} $. 
\end{definition}
Observe that multiplying an element in $\mathbb{Z}[x_{1},\ldots,x_{n}]/\langle {x_1}^{r_1} - 1,\cdots, {x_n}^{r_n} - 1\rangle$ with $x_i$ results in a cyclic shift in the ordered set, $\mathcal{A}_{i}$.  This is
also equivalent to a cyclic permutation in the $n^\text{\tiny{th}}$ order tensor along the $i ^\text{\tiny{th}}$ direction. 

We now formerly define multivariate cyclic lattices. 
\begin{definition}
 A set $\mathcal{L}$ in $\mathbb{Z}^N = \mathbb{Z} ^{r_1 \times \cdots \times r_n}$ is a multivariate cyclic lattice if
\begin{enumerate}[(i)]
\item for all $v,w \in \mathcal{L}$, $v+w$ is also in $\mathcal{L}$,
\item for all $v \in \mathcal{L}$, $-v$ is also in $\mathcal{L}$, and
\item for all $v \in \mathcal{L}$, a $i^{\mathrm{th}}$-multivariate cyclic shift of $v$ is also in $\mathcal{L}$ for all $i \in \{1,\ldots,n\}$.
\end{enumerate}
\end{definition}
We illustrate this with the following example. 
\begin{example} \label{cyclicexample}
Consider the case when $n = 3$ and we have $r_1 = 2$, $r_2 = 2$ and $r_3 = 3$. The quotient ring associated to it is $\mathbb{Z}[x_1,x_2,x_3]/\langle {x_1}^2 - 1, {x_2}^2 -1, {x_3}^3 -1\rangle$. It is isomorphic to the space of $3^\text{\tiny {rd}}$ order tensors, $\mathbb{Z}^{2 \times 2 \times 3} (\cong \mathbb{Z}^{12})$. The following set of monomials form the set of coset representatives for a $\mathbb{Z}$-module basis, 
\begin{displaymath}
\{1,x_1,x_2, x_3, {x_3}^2, x_1x_2, x_1x_3, x_1{x_3}^2,x_2x_3,x_2{x_3}^2, x_1x_2x_3,x_1x_2{x_3}^2\}.
\end{displaymath} 
Any element in the residue class ring can be represented as a $3^\text{\tiny {rd}}$ order tensor, $\mathcal{A} \in \mathbb{Z}^{2 \times 2 \times 3}$. Let $a_{x^\alpha}$ be the coefficient of the basis element, $x^\alpha$. We can represent $\mathcal{A}$ as follows,\\
\begin{tikzpicture}[ 
             x = {(4em,4em)} , 
             y ={(-6em, 4em)} ,
             z = {(0em, 4em)}] 
\node (b0) at (-1,1,2) {$\mathcal{A} = $};
\node (b1) at (0,0,0) {$a_1$};
\node (b2) at (1,0,0) {$a_{x_3}$};
\node (b3) at (2,0,0) {$a_{{x_3}^2}$};
\node (b4) at (0,1,0) {$a_{x_2}$};
\node (b5) at (1,1,0) {$a_{{x_2}{x_3}}$};
\node (b6) at (2,1,0) {$a_{{x_2}{x_3}^2}$};
\node (t1) at (0,0,1) {$a_{x_1}$};
\node (t2) at (1,0,1) {$a_{{x_1}{x_3}}$};
\node (t3) at (2,0,1) {$a_{{x_1}{x_3}^2}$};
\node (t4) at (0,1,1) {$a_{{x_1}{x_2}}$};
\node (t5) at (1,1,1) {$a_{{x_1}{x_2}{x_3}}$};
\node (t6) at (2,1,1) {$a_{{x_1}{x_2}{x_3}^2}$};
          
\draw (b1) -- (b2) -- (b3) -- (b6) -- (b5) -- (b4) -- (b1);
\draw (t1) -- (t2) -- (t3) -- (t6) -- (t5) -- (t4) -- (t1);
\draw (t2) -- (t5);
\draw (b2) -- (b5);
 \foreach \x in {1,2,3,4,5,6} {
     \draw (b\x) -- (t\x);
     }
\end{tikzpicture}.\\
The following tensors represent  $A_3(0)$, $A_3(1)$ and $A_3(2)$ respectively. \\
\begin{tikzpicture}[ 
             x = {(4em,4em)} , 
             y ={(-6em, 4em)} ,
             z = {(0em, 4em)}] 
%\node (b0) at (-1,1,2) {$\mathcal{A} = $};
\node (b1) at (0,0,0) {$a_1$};
\node (b2) at (1,0,0) {$a_{x_3}$};
\node (b3) at (2,0,0) {$a_{{x_3}^2}$};
\node (b4) at (0,1,0) {$a_{x_2}$};
\node (b5) at (1,1,0) {$a_{{x_2}{x_3}}$};
\node (b6) at (2,1,0) {$a_{{x_2}{x_3}^2}$};
\node (t1) at (0,0,1) {$a_{x_1}$};
\node (t2) at (1,0,1) {$a_{{x_1}{x_3}}$};
\node (t3) at (2,0,1) {$a_{{x_1}{x_3}^2}$};
\node (t4) at (0,1,1) {$a_{{x_1}{x_2}}$};
\node (t5) at (1,1,1) {$a_{{x_1}{x_2}{x_3}}$};
\node (t6) at (2,1,1) {$a_{{x_1}{x_2}{x_3}^2}$};
          
\draw (b1) --  (b4);
\draw (b2) -- (b5);
\draw (b3) -- (b6);
\draw (t1) --  (t4);
\draw (t2) -- (t5);
\draw (t3) -- (t6);

 \foreach \x in {1,2,3,4,5,6} {
     \draw (b\x) -- (t\x);
     }
\end{tikzpicture}.
%\begin{tikzpicture}[ 
%             x = {(4em,4em)} , 
%             y ={(-6em, 4em)} ,
%             z = {(0em, 4em)}] 
%%\node (b0) at (-1,1,2) {$S_z(0)= $};
%\node (b1) at (0,0,0) {$a_1$};
%\node (b4) at (0,1,0) {$a_y$};
%\node (t1) at (0,0,1) {$a_x$};
%\node (t4) at (0,1,1) {$a_{xy}$};
%          
%\draw (b1) --  (b4) -- (b1);
%\draw (t1) --  (t4) -- (t1);
% \foreach \x in {1,4} {
%     \draw (b\x) -- (t\x);
%     }
%\end{tikzpicture},
%\begin{tikzpicture}[ 
%             x = {(4em,4em)} , 
%             y ={(-6em, 4em)} ,
%             z = {(0em, 4em)}] 
%%\node (b0) at (0,1,1) {$S_z(1)= $};
%\node (b2) at (1,0,0) {$a_z$};
%\node (b5) at (1,1,0) {$a_{yz}$};
%\node (t2) at (1,0,1) {$a_{xz}$};
%\node (t5) at (1,1,1) {$a_{xyz}$};
%          
%\draw (t2) -- (t5);
%\draw (b2) -- (b5);
% \foreach \x in {2,5} {
%     \draw (b\x) -- (t\x);
%     }
%\end{tikzpicture},
%\begin{tikzpicture}[ 
%             x = {(4em,4em)} , 
%             y ={(-6em, 4em)} ,
%             z = {(0em, 4em)}] 
%%\node (b0) at (-1,1,2) {$S_z(2)= $};
%\node (b3) at (2,0,0) {$a_{z^2}$};
%\node (b6) at (2,1,0) {$a_{yz^2}$};
%\node (t3) at (2,0,1) {$a_{xz^2}$};
%\node (t6) at (2,1,1) {$a_{xyz^2}$};
%          
%\draw  (b3) -- (b6);
%\draw (t3) -- (t6) ;
% \foreach \x in {3,6} {
%     \draw (b\x) -- (t\x);
%     }
%\end{tikzpicture}. 
\\ $A_3(0)$, $A_3(1)$ and $A_3(2)$ represent $2 ^\text{\tiny{nd}}$ order tensors corresponding to ${x_3}=0$, ${x_3} =1$ and ${x_3}=2$ respectively. Similarly, 
$A_2(0)$ and $A_2(1)$ represent $2^ \text{\tiny{nd}}$ order tensors corresponding to ${x_2}=0$ and ${x_2} =1$ and $A_1(0)$ and $A_1(1)$ represent $2^ \text{\tiny{nd}}$ order tensors corresponding to ${x_1}=0$ and ${x_1} =1$.  Multiplying with ${x_3}$ here results in a cyclic rotation
of $A_3(0)$, $A_3(1)$ and $A_3(2)$. 
\end{example} 
Multiplying with a monomial ${x_1}^{\alpha_1}\cdots{x_n}^{\alpha_n}$ in the general case results in a composition of $\alpha_i$ shifts in  $\mathcal{A}_{i}$ for each $ i \in \{1, \ldots, n\}$. 
The commutativity of multiplication is taken care of as the shifts act on an independent set of subtensors and this makes the order of the composition of cyclic shifts irrelevant, i.e. the order in which we perform the cyclic shifts between $\mathcal{A}_{i}$ and $\mathcal{A}_{j}$ does not matter for 
$i,j \in \{1,\ldots,n\}$.  

Finally we state the following.
\begin{proposition}
Every ideal in
\begin{displaymath}
\mathbb{Z}[x_1,\ldots,x_n]/\langle {x_1}^{r_1} - 1,{x_2}^{r_2} - 1,\cdots,
{x_n}^{r_n} - 1\rangle
\end{displaymath}
is a multivariate cyclic lattice.
\end{proposition}

% \section{****We do not need this Section****Structure of $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$}\label{structureofZmodule}
% When we  extend ideal lattices to multivariate case the algebraic structure that we consider is $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$.  The question we have to first address is for all ideals $\mathfrak{a} \subseteq \mathbb{Z}[x_{1},\ldots,x_{n}]$ is the $\mathbb{Z}$-module, $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ 
% isomorphic to $\mathbb{Z}^N, N \in \mathbb{N}$. To study this we employ Gr\"obner basis methods over rings.
% % Clearly, we have to  only consider ideals such that the $\mathbb{Z}$-module, $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ 
% %is finitely generated. We will see from the sections below that freeness of the $\mathbb{Z}$-module determines whether the ideals in the quotient ring are lattices.  
% \cite{Buchberger:1965:thesis} introduced the algorithmic theory of Gr\"obner bases for ideals in polynomial rings over a field $\Bbbk$.
% % Since then the theory of Gr\"obner bases has become a standard tool in computational ideal theory and algebraic
% % geometry. 
% One can extend the definition of Gr\"obner bases in the case of polynomial rings over fields to rings. The reader can refer to the exposition given in 
% \citep[Chapter 4, Sections 4.1, 4.2 and
%   4.3.1]{Adams:1994:introtogrobnerbasis} for more details.
% 
% ****** Here we need to state that if
% $\mathbb{Z}[x_{1},\ldots,x_{n}]/\langle G \rangle$ is finitely
% generated  then there are finitely many ``pseudo standard
% monomials''**** hence the mapping (1)*******
% 
% Consider an ideal $\mathfrak{a} \subseteq A[x_1,\ldots,x_n]$.  Let $G = \{g_i: i = 1, \ldots, t\}$ be a Gr\"obner basis for $\mathfrak{a}$. 
% Recall that, $J_{x^{\alpha}} = \{i : \mathrm{lm}(g_i)\mid x^{\alpha},  g_i \in G \}$  
% and $I_{J_{x^{\alpha}}} = \langle \{\mathrm{lc}(g_i) : i \in J_{x^{\alpha}}\} \rangle$ \cite[Chapter 4, Section 4.2 and 4.3.1]{Adams:1994:introtogrobnerbasis}. We refer to $I_{J_{x^{\alpha}}}$ as the leading coefficient ideal
% w.r.t. $G$.
% Consider $A/I_{J_{x^{\alpha}}}$.  We assume that the coefficient ring $A$ has effective coset representatives \cite[Chapter 4, Page 226]{Adams:1994:introtogrobnerbasis}. 
% Let $C_{J_{x^{\alpha}}}$ represent a set of coset representatives of the equivalence classes in  $A/I_{J_{x^{\alpha}}}$.
% Let $f \in  A[x_1,\ldots,x_n]$. On reducing $f$ with $G$ we get $f = \sum\limits_{i=1}^m a_i x^{\alpha_i} \text{ mod } \langle G \rangle$, where $a_i \in A$. 
% % Consider the set $M = \{a_ix^{\alpha_i} : a_i \in C_{J_{x^{\alpha_i}}},  x^{\alpha_i} \in F\} $. 
% If $A[x_{1},\ldots,x_{n}]/\langle G \rangle$ is a finitely generated $A$-module of size $m$, 
% then corresponding to coset representatives, $C_{J_{x^{\alpha_1}}}, \ldots, C_{J_{x^{\alpha_m}}}$, there exists an $A$-module homomorphism,
% \begin{equation} \label{equation}
% \begin{split}
%  \phi :  A[x_{1},\ldots,x_{n}]/\langle G \rangle &\longrightarrow A/I_{J_{x^{\alpha_1}}} \times \cdots \times A/I_{J_{x^{\alpha_m}}}\\
%          \sum\limits_{i=1}^m a_i x^{\alpha_i} + \langle G \rangle &\longmapsto (c_1 +I_{J_{x^{\alpha_1}}}  , \cdots, c_m + I_{J_{x^{\alpha_m}}}) ,
% \end{split}
% \end{equation}
% where $c_i = a_i \text{  mod  } I_{J_{x^{\alpha_i}}}$ and  $c_i \in C_{J_{x^{\alpha_i}}}$. Note that $\phi$ depends on the choice of coset representatives, $C_{J_{x^{\alpha_1}}}, \ldots, C_{J_{x^{\alpha_m}}}$. Given a Gr\"obner basis $G$ for 
% $\mathfrak{a}$ and the set of coset representatives $C_J$ for the saturated subsets $J$, every $f \in  A[x_1,\ldots,x_n]$ has a unique normal form \cite[Chapter 4, Theorem 4.3.3.]{Adams:1994:introtogrobnerbasis}.
% \par The mapping $\phi$ is  surjective by construction.  Consider $f + \mathfrak{a}, g + \mathfrak{a}$ where $f,g \in  A[x_1,\ldots,x_n]$.
% On reducing $f,g$ with $G$, we get $f = \sum\limits_{i=1}^m a_i x^{\alpha_i} \text{ mod } \langle G \rangle$ and 
% $g = \sum\limits_{i=1}^m b_i x^{\alpha_i} \text{ mod } \langle G \rangle$, where $a_i,b_i  \in A$. 
% Let $\phi(f) = (c_1 +I_{J_{x^{\alpha_1}}}  , \cdots, c_m + I_{J_{x^{\alpha_m}}}) $ 
% and $\phi(g)=(d_1+I_{J_{x^{\alpha_1}}}  , \cdots, d_m+ I_{J_{x^{\alpha_m}}} )$, where $c_i = a_i \text{  mod  } I_{J_{x^{\alpha_i}}}$,  $d_i=b_i \text{  mod  } I_{J_{x^{\alpha_i}}}$ 
% and  $c_i,d_i\in C_{J_{x^{\alpha_i}}}$. Let $c_i = d_i \text{  mod  } I_{J_{x^{\alpha_i}}}$ for all $i \in \{1,\ldots,m\}$. Then $c_i = d_i$ since the set 
% of coset representatives,  $C_{J_{x^{\alpha_i}}}$ is fixed.  This implies,  $f - g$ is an 
% element of $\mathfrak{a}$ and $f + \mathfrak{a} = g + \mathfrak{a}$. Hence, $\phi$ is injective and an $A$-module isomorphism.
% 
% \par Consider the case when $I_{J_{x^{\alpha_i}}} = \{0\}, \text{for all } i \in \{1,\ldots,m\}$. We then have $C_{J_{x^{\alpha_i}}} = \mathbb{Z}$, $\text{for all } i \in \{1,\ldots,m\}$. 
% This implies  $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a} \cong \mathbb{Z}^m$.  That is $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ is a free $\mathbb{Z}$-module.  
% \par From the structure theorem for finitely generated modules over a PID \citep[Chapter 3, Theorem 7.1]{Adkins:1994:moduletheory}  we know that for a finitely generated $\mathbb{Z}$-module, 
% there exists a direct sum of cyclic submodules isomorphic to it. Thus  $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ is isomorphic to  a direct sum of a free component and submodules with torsion. 
% We state the structure theorem
% below. 
% \begin{theorem}[Structure Theorem]\label{structuretheorem}
%  Let $M \ne 0$ be a finitely generated module over the PID $R$. 
%  If the rank of $M$ is $n$, the $M$ is isomorphic to a direct sum of cyclic submodules 
%  \begin{displaymath}
%   M \cong R/\langle w_1 \rangle \oplus \cdots \oplus  R/\langle w_n \rangle
%  \end{displaymath}
% such that  $\langle w_i \rangle \ne R$  and $w_i \mid w_{i+1}$. 
% \end{theorem}
  % We observe that the free part corresponds to the $w_i = 0$ factors
  % in the decomposition.

%==========================================================================
\section{Multivariate Ideal Lattices and Short Reduced Gr\"obner
  Basis} \label{ideallattices}
Ideal lattices in the multivariate case can be defined in a similar way. A
multivariate ideal lattice is an integer lattice $\mathcal{L}
\subseteq \mathbb{Z}^N$ that is also an ideal in $\mathbb{Z}[x]/
\mathfrak{a}$ for some ideal $\mathfrak{a} \subseteq
\mathbb{Z}[x_{1},\ldots,x_{n}]$. The definition is as follows. 
%Definition:Ideal Lattice in multivariate case
\begin{definition}
Given an ideal $\mathfrak{a}\subseteq \mathbb{Z}[x_{1},\ldots,x_{n}]$,    
a multivariate ideal lattice is an integer lattice
$\mathcal{L} \subseteq \mathbb{Z}^N$
such that it is isomorphic, as a
$\mathbb{Z}$-module, to an ideal
$\mathfrak{A}$ in $\mathbb{Z}[x_{1},\ldots,x_{n}]/ \mathfrak{a}$.  
\end{definition}
In sequel, we mention multivariate ideal lattices as just ideal
lattices and it should be clear from the context. 

The $\mathbb{Z}$-module structure of
$\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ is crucial  in locating
ideal lattices in  $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$. In
general, for a Noetherian ring $A$, one can use Gr\"{o}bner basis
methods to determine the $A$-module structure of
$A[x_{1},\ldots,x_{n}]/\mathfrak{a}$, where $\mathfrak{a}$ is an ideal
in $A[x_{1},\ldots,x_{n}]$
\citep{FrancisDukkipati:2013:freeZmodule}. We describe this briefly
below. 

Consider an ideal $\mathfrak{a} \subseteq A[x_1,\ldots,x_n]$.  Let $G
= \{g_i: i = 1, \ldots, t\}$  be a Gr\"obner basis for $\mathfrak{a}$. 
Let $J_{x^{\alpha}} = \{i : \mathrm{lm}(g_i)\mid x^{\alpha},  g_i \in G \}$  
and $I_{J_{x^{\alpha}}} = \langle \{\mathrm{lc}(g_i) : i \in
J_{x^{\alpha}}\} \rangle$. Here $\mathrm{lm}(g_{i})$ denotes leading
monomial of the polynomial $g_{i}$ and $\mathrm{lm}(g_{i})$ denotes
leading coefficient. 
%\cite[Chapter 4, Section 4.2 and 4.3.1]{Adams:1994:introtogrobnerbasis}. 
We refer to $I_{J_{x^{\alpha}}}$ as the leading coefficient ideal
w.r.t. $G$.
%Consider $A/I_{J_{x^{\alpha}}}$.
Here we assume that the coefficient ring $A$ has effective coset
representatives \citep[pp 226]{Adams:1994:introtogrobnerbasis}. 
Let $C_{J_{x^{\alpha}}}$ represent a set of coset representatives of the equivalence classes in  $A/I_{J_{x^{\alpha}}}$.
On reducing $f \in  A[x_1,\ldots,x_n]$ with $G$ we get $f =
\sum\limits_{i=1}^m a_i x^{\alpha_i} \mathrm{mod} \langle G \rangle$,
where $a_i \in A, i=1,\ldots,m$.   
% Consider the set $M = \{a_ix^{\alpha_i} : a_i \in C_{J_{x^{\alpha_i}}},  x^{\alpha_i} \in F\} $. 
If $A[x_{1},\ldots,x_{n}]/\langle G \rangle$ is a finitely generated $A$-module of size $m$,
then corresponding to coset representatives, $C_{J_{x^{\alpha_1}}}, \ldots, C_{J_{x^{\alpha_m}}}$, there exists an $A$-module isomorphism~\citep{FrancisDukkipati:2013:freeZmodule}
\begin{equation} \label{equation}
\begin{split}
 \phi :  A[x_{1},\ldots,x_{n}]/\langle G \rangle &\longrightarrow A/I_{J_{x^{\alpha_1}}} \times \cdots \times A/I_{J_{x^{\alpha_m}}}\\
         \sum\limits_{i=1}^m a_i x^{\alpha_i} + \langle G \rangle &\longmapsto (c_1 +I_{J_{x^{\alpha_1}}}  , \cdots, c_m + I_{J_{x^{\alpha_m}}}) ,
\end{split}
\end{equation}
where $c_i = a_i \text{  mod  } I_{J_{x^{\alpha_i}}}$ and  $c_i \in C_{J_{x^{\alpha_i}}}$. 
% We will prove below that all ideals in a free and finitely generated $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ are ideal lattices and that ideal lattices cannot exist in a $\mathbb{Z}$-module that has torsion submodules.
%\subsection{Free and finitely generated
%$\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ }
When $I_{J_{x^{\alpha_i}}} = \{0\}, \text{for all } i \in
\{1,\ldots,m\}$ we have $C_{J_{x^{\alpha_i}}} = A$,
$\text{for all } i \in \{1,\ldots,m\}$.  
This implies  $A[x_{1},\ldots,x_{n}]/\mathfrak{a} \cong A^m$. In this
case, in
particular, when $A=\mathbb{Z}$,
$\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ is a free
$\mathbb{Z}$-module. One can conclude that corresponding to every
ideal in $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ there exists a
subgroup in $\mathbb{Z}^{n}$, hence it is an ideal lattice. 
\begin{proposition}
Every ideal in a free and finitely generated $\mathbb{Z}$-module,  
$\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ is an ideal lattice. 
\end{proposition}
% \proof
% A free and finitely generated $\mathbb{Z}$-module, $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ 
% is isomorphic to $\mathbb{Z}^N ,$ for some  $N \in \mathbb{N}$, i.e. $I_{J_{x^{\alpha_i}}} = \{0\}, \text{for all } i \in \{1,\ldots,m\}$ in 
% Equation~\eqref{equation}. 
% In the isomorphism, all ideals map to subgroups of $\mathbb{Z}^N$ and therefore all ideals are ideal lattices.
% \endproof
%\subsection{Finitely generated $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ with torsion submodules}
Our next step is to determine if residue class polynomial rings with torsion submodules contain ideal lattices. 
Using the structure theorem for finitely generated modules over a PID \citep[Chapter 3, Theorem 7.1]{Adkins:1994:moduletheory}, determination of the existence of  ideal lattices in a 
finitely generated $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ with torsion is relatively straightforward. 
%We show below that if a finitely generated $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ is not free then no ideal in it is a lattice. 
\begin{proposition}
If  a finitely generated $\mathbb{Z}$-module,
$\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ is not free then no ideal in
$\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ is an integer lattice. 
\end{proposition}
\proof
We have from the structure theorem over a PID,
\begin{displaymath}
 \mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a} \cong \mathbb{Z}^l \oplus \mathbb{Z}/\langle w_1 \rangle \oplus \cdots \oplus \mathbb{Z}/\langle w_k \rangle.
\end{displaymath}
If there is no free part then clearly the residue class ring does not have an ideal lattice. 
Let $G$ be the Gr\"obner basis of the ideal, $\mathfrak{a}$. 
Assume there exists an ideal $\mathfrak{A} \subseteq \mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ such that it is an integer lattice.  
Let $x^{\alpha_r} + \mathfrak{a} \in \mathfrak{A}$ be an element such that the leading coefficient ideal of $x^{\alpha_r}$ in $\mathbb{Z}$, $I_{J_{x^{\alpha_r}}}$ is equal to $\{0\}$. 
This implies that the set of coset representatives, $C_{J_{x^{\alpha_r}}} = \mathbb{Z}$ and therefore the monomial corresponds to the free part. 
Consider the ideal generated by $x^{\alpha_r} + \mathfrak{a}$. Since the $\mathbb{Z}$-module is not free we have  $I_{J_{x^{\alpha_j}}} \ne \{0\}$ for some monomial $x^{\alpha_j}$ in Equation~\eqref{equation}. 
Let $c \in C_{J_{x^{\alpha_j}}}$.
% Also, consider the element $c_i x^{\alpha_i} + \mathfrak{a} \in  \mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ such that $c_i \in C_{J_{x^{\alpha_i}}}$ where 
% $C_{J_{x^{\alpha_i}}} \ne \mathbb{Z}$. There will always exist such a monomial since the $\mathbb{Z}$-module is not free which implies some $I_{J_{x^{\alpha_i}}}$ is not equal to the zero ideal in
% Equation~\eqref{equation}. 
We have, $c x^{\alpha_j }x^{\alpha_r}  + \mathfrak{a} \in \langle x^{\alpha_r} + \mathfrak{a} \rangle $. This implies the ideal generated by a free element contains torsion elements. Thus the $\mathbb{Z}$-module 
$\mathfrak{A}$ has torsion elements and is not isomorphic to an integer lattice which is a contradiction.
\endproof
Thus we have the following result.
\begin{corollary}
 Every ideal, $\mathfrak{a}$ in  $\mathbb{Z}[x_{1},\ldots,x_{n}]$ is
 an ideal lattice if and only if
 $\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ is a free and finitely
 generated $\mathbb{Z}$-module. 
\end{corollary}

To test whether a $\mathbb{Z}$-module
$\mathbb{Z}[x_{1},\ldots,x_{n}]/\mathfrak{a}$ is free, 
algorithmically, one needs the notion of `short reduced Gr\"obner bases'
introduced in~\citep{FrancisDukkipati:2013:freeZmodule}. We describe
this here for any polynomial ring over a Noetherian ring, $A$.
\begin{definition}
 Let $\mathfrak{a} \subseteq A[x_1,\ldots,x_n]$ be an ideal.  
 A reduced Gr\"obner basis $G$ of $\mathfrak{a}$  is called a short reduced Gr\"obner basis if for each $x^\alpha \in \mathrm{lm}(G)$, the length of the generating set for its leading coefficient ideal
 is minimal. 
\end{definition}
The reduced Gr\"obner basis in the above definition is as described in
\citep{Pauer:2007:Grobnerbasisrings}. Short reduced Gr\"obner basis is
a reduced Gr\"obner basis   with an additional condition that the
length of the generating set of  the leading coefficient ideals in the basis is minimal.
When  $A = \mathbb{Z}$ in the above proposition, short reduced Gr\"obner basis is the reduced Gr\"obner basis of  $\mathfrak{a}$ where the generator of the leading coefficient ideal is taken as the $gcd$ of all generators.

We now give the characterization. 
\begin{proposition}\label{Proposition for characterization}
Let $\mathfrak{a} \subseteq A[x_1,\ldots,x_n]$ be a non-zero ideal such that $A[x_1,\ldots,x_n]/\mathfrak{a}$ is finitely generated. Let $G$ be a  short reduced Gr\"obner basis for $\mathfrak{a}$ w.r.t. some monomial ordering. Then,
\begin{displaymath}
A[x_1,\ldots,x_n]/\mathfrak{a} \cong A^N, \hspace{10pt} \text{ for some } N \in \mathbb{N}
\end{displaymath}
if and only if $G$ is monic.
\end{proposition}
% If the short reduced 
% Gr\"obner basis of $\mathfrak{a}$ is monic, then it is equivalent to the case where $I_{J_{x^{\alpha_i}}} = \{0\}$, $\forall i$ in Equation~\eqref{equation}.  We then have from the above characterization,
% $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a} \cong \mathbb{Z}^N,$ for some  $N \in \mathbb{N}$.
We can summarize the results in this section by the theorem below.
\begin{theorem}
The $\mathbb{Z}$-module,  $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ has ideal lattices if and only if the short reduced Gr\"obner basis of $\mathfrak{a}$ is monic.
\end{theorem}
We illustrate this by an example. 
\begin{example}
Let  $\mathfrak{a} = \langle 3 x^2, 5x^2,y \rangle$ be an ideal in
$\mathbb{Z}[x,y]$. The short reduced Gr\"obner basis for the ideal is
$G= \{x^2,y\}$. Since $G$ is monic $\mathbb{Z}[x,y]/\mathfrak{a}$ is
free and isomorphic to $\mathbb{Z}^2$. All ideals in it are ideal
lattices. For example the ideal generated by $6x+\langle x^2,y
\rangle$ is isomorphic to the lattice, $\mathcal{L}([(0,6)])$. Note
  that here $\mathcal{L}([(0,6)])$ denotes the subgroup generated by
    $(0,6)$ in ${\mathbb{Z}}^{2}$.
\end{example}
%================================================================
\section{Full Rank Lattices in Free, Finitely Generated $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$}\label{fullrank}
We recall that in the definition of ideal lattices in $\mathbb{Z}[x]$  the
choice of the polynomial $f$ in $\mathbb{Z}[x]/\langle f \rangle$ is
restricted to monic polynomials.  But in the construction of many
cryptographic primitives like collision resistant hash functions an
additional condition is imposed on $f$ that $f$ is an irreducible polynomial. 
This condition ensures that the lattice is full rank that is
fundamental in many cryptographic  constructions
\citep{Lyubashevsky:2006:Ideallatticefirstdef}.
In multivariate case, we derive a necessary and sufficient  condition
for ideal lattices to be full rank.  
\begin{proposition}
 Let $\{g_1,\ldots,g_t\}$ be a monic short reduced Gr\"obner basis of an ideal $\mathfrak{a}$ in $\mathbb{Z}[x_1,\ldots,x_n]$ such that $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a} \cong \mathbb{Z}^N$ for some $N \in \mathbb{N}$.
All ideals in $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ are full rank
lattices if and only if $\mathfrak{a}$ is a prime ideal.
\end{proposition}
\proof
Let $\mathfrak{a} = \langle g_1,\cdots,g_t \rangle$ be a prime ideal. Consider an ideal $\mathfrak{A} = \langle f_1 + \mathfrak{a}, \cdots,  f_s + \mathfrak{a} \rangle$ in  $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$.
Since $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a} \cong \mathbb{Z}^N$ we have a finite basis, $\mathcal{B} = \{b_1 + \mathfrak{a}, \ldots,b_N + \mathfrak{a}\}$.
We have to prove that there are $N$ linearly independent vectors in $\mathfrak{A}$.
Consider $f_1b_1,\ldots,f_1b_N$. Let $c_1f_1b_1 + \cdots + c_Nf_1b_N \in \langle g_1, \cdots, g_t\rangle$. This implies $f_1(c_1b_1 + \cdots + c_Nb_N) \in \langle g_1, \cdots, g_t\rangle$. 
Since $\langle g_1,\cdots,g_t \rangle$ is a prime ideal, either
$f_1 \in \langle g_1,\cdots,g_t \rangle$ or $(c_1b_1 + \cdots + c_Nb_N)\in\langle g_1,\cdots,g_t \rangle$. But both cases cannot happen. Therefore $c_i = 0$ for all $i \in \{1, \ldots,N\}$.
This implies that  $f_1b_1 + \mathfrak{a},\ldots,f_1b_N + \mathfrak{a}$ are linearly independent and the ideal lattice is full rank.

Conversely, assume that $\mathfrak{a}$ is not a prime ideal. 
Then there exists $l,h \in  \mathbb{Z}[x_1,\ldots,x_n]$ such that $lh \in \langle g_1,\cdots,g_t \rangle$ but $l \not\in \langle g_1,\cdots,g_t \rangle$ and 
$h \not\in \langle g_1,\cdots,g_t \rangle$. This implies, $l = \sum_{i=1}^{N} c_ib_i$ and $h = \sum_{i=1}^{N} d_ib_i$ where $b_i + \mathfrak{a} \in \mathcal{B}$, the basis
for $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ and $c_i,d_i \in \mathbb{Z}$. 
%We have, $lh = \sum_{i=1}^{t} k_ig_i$, $k_i \in \mathbb{Z}[x_1,\ldots,x_n]$. 
Consider the ideal lattice $\langle l + \mathfrak{a}\rangle$. We have $lh \in \langle g_1,\cdots,g_t\rangle$. This implies $l\sum_{i=1}^{N}d_ib_i \in \langle g_1,\cdots,g_t\rangle$. 
But $l\not\in \langle g_1,\cdots,g_t\rangle$ and $\sum_{i=1}^{N} d_ib_i \not\in \langle g_1,\cdots,g_t\rangle$. The set $\{lb_1 + \mathfrak{a}, \ldots, lb_N + \mathfrak{a}\}$ contains linearly dependent vectors and the rank 
of the ideal lattice $\langle l + \mathfrak{a}\rangle$ is $\lneq N$. 
% This implies that the ideal lattice $\langle l + \mathfrak{a}\rangle$ is not full rank. 
Therefore, if the ideal $\mathfrak{a}$ is not a prime ideal then there are lattices in $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$ that are not full rank.
\endproof
%\subsection{Prime ideals in $\mathbb{Z}[x_1,\ldots,x_n]$}
% Therefore determining if an ideal is prime or not is vital if ideal lattices in the multivariate case
% need to find practical applications. 
Determining if an ideal is prime or not is key to ideal lattices 
finding a practical application.
An algorithm for primality testing in polynomial rings over any commutative, Noetherian ring, $A$ can be found in \citep{Gianni:1988:primailitytesting}. 
%In the section below, 
%\subsubsection{Lattice ideals in $\mathbb{Z}[x_1,\ldots,x_n]$}

We now give an example of a class of binomial ideals that are prime and give rise to free residue class polynomial rings. 
A lattice ideal, $\mathfrak{a}_\mathcal{L}$ in $\Bbbk[x_1,\ldots,x_n]$ is defined as the binomial ideal generated by $\{x^{v^+} - x^{v^-}\}$ 
where $v^+$ and $v^-$ are non-negative with disjoint support and $v^+ - v^- \in \mathcal{L}$, where $\mathcal{L}$
is a lattice \citep{Katsabekis:2010:latticeideal}. 
Lattice ideals in polynomial rings over $\mathbb{Z}$ can be defined in the same way.  
In this case, the binomial ideal is generated over the polynomial ring, $\mathbb{Z}[x_1,\ldots,x_n]$.  
The generators of the ideal are binomials with the terms having opposite sign and the coefficients of both the terms equal to absolute value $1$. 
One can show that the short reduced Gr\"obner basis of the lattice ideal is monic \citep{FrancisDukkipati:2013:freeZmodule}. 
In this case, by Proposition ~\ref{Proposition for characterization}, $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}_\mathcal{L}$ is free. 
\begin{theorem}
Every ideal in $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}_\mathcal{L}$,
where $\mathfrak{a}_\mathcal{L}$ is a lattice ideal,  is an ideal lattice. 
\end{theorem}
\noindent The saturation of an integer lattice, $\mathcal{L}\subseteq \mathbb{Z}^m$ is the lattice, 
 \begin{displaymath}
  Sat(\mathcal{L}) = \{\alpha \in \mathbb{Z}^m \mid d\alpha \in \mathcal{L} \text{ for some } d \in \mathbb{Z}, d \ne 0\}.
 \end{displaymath}
 We say that an integer lattice $\mathcal{L}$ is saturated if $\mathcal{L} =  Sat(\mathcal{L})$. It can be easily shown that the lattice ideal $\mathfrak{a}_\mathcal{L}$ is prime if and only if
$\mathcal{L}$ is saturated. Note that prime lattice ideals are also called toric ideals. For more details on toric ideals in $\Bbbk[x_1,\ldots,x_n]$ one can refer to \citep{Bigatti:1999:toricideals}. 
The definitions related to toric ideals can be extended to polynomial rings over $\mathbb{Z}$ in a similar way. Thus, toric ideals in $\mathbb{Z}[x_1,\ldots,x_n]$  give rise to full rank integer lattices.
 \section*{Summary}
In this paper, we studied ideal lattices in the multivariate case
and showed the use of Gr\"obner bases in locating them. 
%we extended ideal lattices in $\mathbb{Z}[x]/\langle f
%\rangle$ to the multivariate case, $\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$. 
We also introduced multivariate cyclic lattices to draw parallels
between the univariate and multivariate cases. In particular, we showed
that ideal lattices in multivariate case are a generalization of
multivariate cyclic lattices. Using short reduced Gr\"obner bases, we
have given an algorithmic method to identify ideals in
$\mathbb{Z}[x_1,\ldots,x_n]$ that give rise to ideal lattices in  
$\mathbb{Z}[x_1,\ldots,x_n]/\mathfrak{a}$.
Generating lattices of full rank is important for cryptographic applications and we 
 provide a necessary and sufficient condition for ideals in
 $\mathbb{Z}[x_1,\ldots,x_n]$ for the same.
 %Finally, we have provided a class of binomial ideals in the 
%multivariate polynomial ring over $\mathbb{Z}$ as an example for
%ideals that result in full rank ideal lattices.  
\section*{Acknowledgments}
\footnotesize{
The authors would like to thank Debarghya Ghoshdastidar for useful
discussions on tensor representations of cyclic lattices in the
multivariate case.}
 {\footnotesize
%\bibliographystyle{jtbnew}
%\bibliography{bib2}
\begin{thebibliography}{15}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi
\providecommand{\selectlanguage}[1]{\relax}

\bibitem[{Adams \& {L}oustaunau(1994)}]{Adams:1994:introtogrobnerbasis}
\textsc{Adams, W. \& {L}oustaunau, P.} (1994).
\newblock \emph{{A}n {I}ntroduction to {G}r{\"o}bner {B}ases}.
\newblock American Mathematical Society.

\bibitem[{{A}dkins \& {W}eintraub(1992)}]{Adkins:1994:moduletheory}
\textsc{{A}dkins, W.~A. \& {W}eintraub, S.~H.} (1992).
\newblock \emph{{A}lgebra: {A}n {A}pproach {V}ia {M}odule {T}heory}.
\newblock Springer.

\bibitem[{Ajtai(1996)}]{Ajtai:1996:Znascryptoprimitive}
\textsc{Ajtai, M.} (1996).
\newblock {G}enerating {H}ard instances of {L}attice {P}roblems ({E}xtended
  {A}bstract).
\newblock In: \emph{{P}roceedings of the 1996 {ACM} {S}ymposium on the {T}heory
  of {C}omputing, {STOC}} (\textsc{Miller, G.~L.}, ed.). {ACM}.

\bibitem[{Bigatti \emph{et~al.}(1999)Bigatti, {L}a Scala \&
  Robbiano}]{Bigatti:1999:toricideals}
\textsc{Bigatti, A., {L}a Scala, R. \& Robbiano, L.} (1999).
\newblock {C}omputing {T}oric {I}deals.
\newblock \emph{{J}ournal of {S}ymbolic {C}omputation} \textbf{27}(4), 351 --
  365.

\bibitem[{Buchberger(1965)}]{Buchberger:1965:thesis}
\textsc{Buchberger, B.} (1965).
\newblock \emph{{A}n {A}lgorithm for {F}inding a {B}asis for the {R}esidue
  {C}lass {R}ing of a {Z}ero-{D}imensional {P}olynomial {I}deal (in {G}erman)}.
\newblock Ph.D. thesis, University of Innsbruck, Austria.
\newblock (reprinted in~\cite{Buchberger:2006:thesistranslation}).

\bibitem[{Buchberger(2006)}]{Buchberger:2006:thesistranslation}
\textsc{Buchberger, B.} (2006).
\newblock Bruno {B}uchberger's {P}h{D} thesis 1965: {A}n algorithm for finding
  the basis elements of the residue class ring of a zero dimensional polynomial
  ideal.
\newblock \emph{Journal of Symbolic Computation} \textbf{41}, 475--511.

\bibitem[{Francis \& Dukkipati(2014)}]{FrancisDukkipati:2013:freeZmodule}
\textsc{Francis, M. \& Dukkipati, A.} (2014).
\newblock On reduced {G}r{\"o}bner basis and macaulay-buchberger basis theorem
  over noetherian rings.
\newblock \emph{Journal of Symbolic Computation}
  \textbf{DOI:10.1016/j.jsc.2014.01.001}.

\bibitem[{Gianni \emph{et~al.}(1988)Gianni, Trager \&
  Zacharias}]{Gianni:1988:primailitytesting}
\textsc{Gianni, P., Trager, B. \& Zacharias, G.} (1988).
\newblock Gröbner bases and primary decomposition of polynomial ideals.
\newblock \emph{Journal of {S}ymbolic {C}omputation} \textbf{6}(2–3), 149 --
  167.

\bibitem[{Katsabekis \emph{et~al.}(2010)Katsabekis, Morales \&
  Thoma}]{Katsabekis:2010:latticeideal}
\textsc{Katsabekis, A., Morales, M. \& Thoma, A.} (2010).
\newblock Binomial generation of the radical of a lattice ideal.
\newblock \emph{Journal of {A}lgebra} \textbf{324}(6), 1334 -- 1346.

\bibitem[{Lyubashevsky(2008)}]{Lyubashevsky:2008:Ideallattice}
\textsc{Lyubashevsky, V.} (2008).
\newblock {L}attice {B}ased {I}dentification {S}chemes {S}ecure {U}nder
  {A}ctive {A}ttacks.
\newblock In: \emph{{P}roceedings of the 11th {I}nternational {W}orkshop on
  {P}ractice and {T}heory in {P}ublic {K}ey {C}ryptography, 2008}
  (\textsc{Cramer, R.}, ed.), vol. 4939 of \emph{{L}ecture {N}otes in
  {C}omputer {S}cience}. {S}pringer.

\bibitem[{Lyubashevsky \&
  Micciancio(2006)}]{Lyubashevsky:2006:Ideallatticefirstdef}
\textsc{Lyubashevsky, V. \& Micciancio, D.} (2006).
\newblock {G}eneralized {C}ompact {K}napsacks {A}re {C}ollision {R}esistant.
\newblock In: \emph{{ICALP} (2)} (\textsc{Bugliesi, M., Preneel, B., Sassone,
  V. \& Wegener, I.}, eds.), vol. 4052 of \emph{{L}ecture {N}otes in {C}omputer
  {S}cience}. {S}pringer.

\bibitem[{Lyubashevsky \& Micciancio(2008)}]{Micciancio:2008:EfficientSign}
\textsc{Lyubashevsky, V. \& Micciancio, D.} (2008).
\newblock {A}symptotically {E}fficient {L}attice-{B}ased {D}igital
  {S}ignatures.
\newblock In: \emph{{T}heory of {C}ryptography {C}onference, 2008} (\textsc{R.,
  C.}, ed.), vol. 4948 of \emph{{L}ecture {N}otes in {C}omputer {S}cience}.
  {S}pringer.

\bibitem[{Micciancio(2002)}]{Micciancio:2002:CyclicLattices}
\textsc{Micciancio, D.} (2002).
\newblock {G}eneralized {C}ompact {K}napsacks, {C}yclic {L}attices, and
  {E}fficient {O}ne-{W}ay {F}unctions from {W}orst-{C}ase {C}omplexity
  {A}ssumptions.
\newblock In: \emph{Symposium on {F}oundations of {C}omputer {S}cience ({FOCS}
  2002) {P}roceedings}. {IEEE} {C}omputer {S}ociety.

\bibitem[{Micciancio \& Goldwasser(2002)}]{Micciancio:2002:LatticesCrypto}
\textsc{Micciancio, D. \& Goldwasser, S.} (2002).
\newblock \emph{Complexity of {L}attice {P}roblems: a cryptographic
  perspective}, vol. 671 of \emph{The {K}luwer {I}nternational {S}eries in
  {E}ngineering and {C}omputer {S}cience}.
\newblock Boston, Massachusetts: Kluwer {A}cademic {P}ublishers.

\bibitem[{Pauer(2007)}]{Pauer:2007:Grobnerbasisrings}
\textsc{Pauer, F.} (2007).
\newblock {G}r{\"o}bner {B}ases with {C}oefficients in {R}ings.
\newblock \emph{{J}ournal of {S}ymbolic {C}omputation} \textbf{42}(11-12).

\end{thebibliography}

}
\end{document}

1409.7788.extracted_bib
[{Adams \& {Loustaunau(1994)]{Adams:1994:introtogrobnerbasis \textsc{Adams, W. \& {Loustaunau, P. (1994). \newblock {An {Introduction to {Gr{\"obner {Bases. \newblock American Mathematical Society.
1409.7788.extracted_bib
[{{Adkins \& {Weintraub(1992)]{Adkins:1994:moduletheory \textsc{{Adkins, W.~A. \& {Weintraub, S.~H. (1992). \newblock {Algebra: {An {Approach {Via {Module {Theory. \newblock Springer.
1409.7788.extracted_bib
[{Ajtai(1996)]{Ajtai:1996:Znascryptoprimitive \textsc{Ajtai, M. (1996). \newblock {Generating {Hard instances of {Lattice {Problems ({Extended {Abstract). \newblock In: {Proceedings of the 1996 {ACM {Symposium on the {Theory of {Computing, {STOC (\textsc{Miller, G.~L., ed.). {ACM.
1409.7788.extracted_bib
[{Bigatti et~al.(1999)Bigatti, {La Scala \& Robbiano]{Bigatti:1999:toricideals \textsc{Bigatti, A., {La Scala, R. \& Robbiano, L. (1999). \newblock {Computing {Toric {Ideals. \newblock {Journal of {Symbolic {Computation 27(4), 351 -- 365.
1409.7788.extracted_bib
[{Buchberger(1965)]{Buchberger:1965:thesis \textsc{Buchberger, B. (1965). \newblock {An {Algorithm for {Finding a {Basis for the {Residue {Class {Ring of a {Zero-{Dimensional {Polynomial {Ideal (in {German). \newblock Ph.D. thesis, University of Innsbruck, Austria. \newblock (reprinted in~\cite{Buchberger:2006:thesistranslation).
1409.7788.extracted_bib
[{Buchberger(2006)]{Buchberger:2006:thesistranslation \textsc{Buchberger, B. (2006). \newblock Bruno {Buchberger's {Ph{D thesis 1965: {An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. \newblock Journal of Symbolic Computation 41, 475--511.
1409.7788.extracted_bib
[{Francis \& Dukkipati(2014)]{FrancisDukkipati:2013:freeZmodule \textsc{Francis, M. \& Dukkipati, A. (2014). \newblock On reduced {Gr{\"obner basis and macaulay-buchberger basis theorem over noetherian rings. \newblock Journal of Symbolic Computation DOI:10.1016/j.jsc.2014.01.001.
1409.7788.extracted_bib
[{Gianni et~al.(1988)Gianni, Trager \& Zacharias]{Gianni:1988:primailitytesting \textsc{Gianni, P., Trager, B. \& Zacharias, G. (1988). \newblock Gröbner bases and primary decomposition of polynomial ideals. \newblock Journal of {Symbolic {Computation 6(2–3), 149 -- 167.
1409.7788.extracted_bib
[{Katsabekis et~al.(2010)Katsabekis, Morales \& Thoma]{Katsabekis:2010:latticeideal \textsc{Katsabekis, A., Morales, M. \& Thoma, A. (2010). \newblock Binomial generation of the radical of a lattice ideal. \newblock Journal of {Algebra 324(6), 1334 -- 1346.
1409.7788.extracted_bib
[{Lyubashevsky(2008)]{Lyubashevsky:2008:Ideallattice \textsc{Lyubashevsky, V. (2008). \newblock {Lattice {Based {Identification {Schemes {Secure {Under {Active {Attacks. \newblock In: {Proceedings of the 11th {International {Workshop on {Practice and {Theory in {Public {Key {Cryptography, 2008 (\textsc{Cramer, R., ed.), vol. 4939 of {Lecture {Notes in {Computer {Science. {Springer.
1409.7788.extracted_bib
[{Lyubashevsky \& Micciancio(2006)]{Lyubashevsky:2006:Ideallatticefirstdef \textsc{Lyubashevsky, V. \& Micciancio, D. (2006). \newblock {Generalized {Compact {Knapsacks {Are {Collision {Resistant. \newblock In: {ICALP (2) (\textsc{Bugliesi, M., Preneel, B., Sassone, V. \& Wegener, I., eds.), vol. 4052 of {Lecture {Notes in {Computer {Science. {Springer.
1409.7788.extracted_bib
[{Lyubashevsky \& Micciancio(2008)]{Micciancio:2008:EfficientSign \textsc{Lyubashevsky, V. \& Micciancio, D. (2008). \newblock {Asymptotically {Efficient {Lattice-{Based {Digital {Signatures. \newblock In: {Theory of {Cryptography {Conference, 2008 (\textsc{R., C., ed.), vol. 4948 of {Lecture {Notes in {Computer {Science. {Springer.
1409.7788.extracted_bib
[{Micciancio(2002)]{Micciancio:2002:CyclicLattices \textsc{Micciancio, D. (2002). \newblock {Generalized {Compact {Knapsacks, {Cyclic {Lattices, and {Efficient {One-{Way {Functions from {Worst-{Case {Complexity {Assumptions. \newblock In: Symposium on {Foundations of {Computer {Science ({FOCS 2002) {Proceedings. {IEEE {Computer {Society.
1409.7788.extracted_bib
[{Micciancio \& Goldwasser(2002)]{Micciancio:2002:LatticesCrypto \textsc{Micciancio, D. \& Goldwasser, S. (2002). \newblock Complexity of {Lattice {Problems: a cryptographic perspective, vol. 671 of The {Kluwer {International {Series in {Engineering and {Computer {Science. \newblock Boston, Massachusetts: Kluwer {Academic {Publishers.
1409.7788.extracted_bib
[{Pauer(2007)]{Pauer:2007:Grobnerbasisrings \textsc{Pauer, F. (2007). \newblock {Gr{\"obner {Bases with {Coefficients in {Rings. \newblock {Journal of {Symbolic {Computation 42(11-12).