Some Sieving Algorithms for Lattice Problems

Abstract

We study the algorithmic complexity of lattice problems based on the
  sieving technique due to Ajtai, Kumar, and Sivakumar~\cite{aks}.
  Given a $k$-dimensional subspace $M\subseteq \R^n$ and a full rank
  integer lattice $\L\subseteq \Q^n$, the \emph{subspace avoiding
    problem} SAP, defined by Bl\"omer and Naewe \cite{blomer}, is to
  find a shortest vector in $\L\setminus M$. We first give a $2^{O(n+k
    \log k)}$ time algorithm to solve \emph{the subspace avoiding
    problem}.  Applying this algorithm we obtain the following
  results.
\begin{enumerate}
\item We give a $2^{O(n)}$ time algorithm to compute $i^{th}$
  successive minima of a full rank lattice $\L\subset \Q^n$ if $i$ is
  $O(\frac{n}{\log n})$. 
\item We give a $2^{O(n)}$ time algorithm to solve a restricted
  \emph{closest vector problem CVP} where the inputs fulfil a promise
  about the distance of the input vector from the lattice.
\item We also show that unrestricted CVP has a $2^{O(n)}$ exact
  algorithm if there is a $2^{O(n)}$ time exact algorithm for solving
  CVP with additional input $v_i\in \L, 1\leq i\leq n$, where
  $\|v_i\|_p$ is the $i^{th}$ successive minima of $\L$ for each $i$. 
\end{enumerate}
We also give a new approximation algorithm for SAP and the
\emph{Convex Body Avoiding problem} which is a generalization of SAP.
Several of our algorithms work for \emph{gauge} functions as metric,
where the gauge function has a natural restriction and is accessed by
an oracle.