Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-076 | 18th September 2015 07:30

Improved hardness results for unique shortest vector problem

RSS-Feed




Revision #1
Authors: Divesh Aggarwal, Chandan Dubey
Accepted on: 18th September 2015 07:31
Downloads: 1207
Keywords: 


Abstract:

The unique shortest vector problem on a rational lattice is the problem of finding the shortest non-zero vector under the promise that it is unique (up to multiplication by -1). We give several incremental improvements on the known hardness of the unique shortest vector problem (uSVP) using standard techniques. This includes a deterministic reduction from the shortest vector problem to the uSVP, the NP-hardness of uSVP on (1 + 1/poly(n))-unique
lattices, and a proof that the decision version of uSVP defined by Cai \cite{Cai98} is in co-NP for
$n^{1/4}$-unique lattices.


Paper:

TR13-076 | 15th May 2013 09:24

Improved hardness results for unique shortest vector problem


Abstract:

We give several improvements on the known hardness of the unique shortest vector problem in lattices, i.e., the problem of finding a shortest vector in a given lattice given a promise that the shortest vector is unique upto a uniqueness factor $\gamma$.
We give a deterministic reduction from the shortest vector problem to the unique shortest vector problem. Before this, only a randomized reduction \cite{KS01} was known. This implies that if SVP is NP-hard, then uSVP is NP-hard.
We also give a (randomized) reduction from SAT to uSVP on an $n$-dimensional lattice with uniqueness factor $1 + 1/poly(n)$. This improves the result of Kumar-Sivakumar\cite{KS01} showing that $uSVP_{1+1/poly(n)}$ is NP-hard under randomized reductions.

Additionally, we show that if $GapSVP_{\gamma}$ is in co-NP (or co-AM) then $uSVP_{\sqrt{\gamma}}$ is in co-NP (co-AM respectively). This improves previously known $uSVP_{n^{1/4}} \in $ co-AM proof by Cai \cite{Cai98} to $uSVP_{(n/\log n)^{1/4}} \in$ co-AM, and additionally generalizes it to $uSVP_{n^{1/4}} \in$ co-NP. Note that when we say that $uSVP \in $ co-NP or co-AM , we mean the decision version that was implicitly defined in Cai \cite{Cai98}.

We also show that the decision-$uSVP$ is {\bf NP}-hard for randomized reductions, which does not follow from Kumar-Sivakumar \cite{KS01}. We also give a deterministic reduction from search-$uSVP_{\gamma}$ to decision-$uSVP_{\gamma/2}$.



ISSN 1433-8092 | Imprint