ECCC-Report TR13-076https://eccc.weizmann.ac.il/report/2013/076Comments and Revisions published for TR13-076en-usFri, 18 Sep 2015 07:31:06 +0300
Revision 1
| Improved hardness results for unique shortest vector problem |
Divesh Aggarwal,
Chandan Dubey
https://eccc.weizmann.ac.il/report/2013/076#revision1The 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.Fri, 18 Sep 2015 07:31:06 +0300https://eccc.weizmann.ac.il/report/2013/076#revision1
Paper TR13-076
| Improved hardness results for unique shortest vector problem |
Chandan Dubey,
Divesh Aggarwal
https://eccc.weizmann.ac.il/report/2013/076We 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}$. Fri, 24 May 2013 13:47:54 +0300https://eccc.weizmann.ac.il/report/2013/076