License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2008.1738
URN: urn:nbn:de:0030-drops-17380
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1738/
Arvind, V. ;
Joglekar, Pushkar S.
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.
BibTeX - Entry
@InProceedings{arvind_et_al:LIPIcs:2008:1738,
author = {V. Arvind and Pushkar S. Joglekar},
title = {{Some Sieving Algorithms for Lattice Problems}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {25--36},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-08-8},
ISSN = {1868-8969},
year = {2008},
volume = {2},
editor = {Ramesh Hariharan and Madhavan Mukund and V Vinay},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1738},
URN = {urn:nbn:de:0030-drops-17380},
doi = {10.4230/LIPIcs.FSTTCS.2008.1738},
annote = {Keywords: Lattice problems, sieving algorithm, closest vector problem}
}
|
Keywords: |
|
Lattice problems, sieving algorithm, closest vector problem |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
|
Issue Date: |
|
2008 |
|
Date of publication: |
|
05.12.2008 |
