Revision #1 Authors: Divesh Aggarwal, Chandan Dubey

Accepted on: 18th September 2015 07:31

Downloads: 1122

Keywords:

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.

TR13-076 Authors: Divesh Aggarwal, Chandan Dubey

Publication: 24th May 2013 13:47

Downloads: 3728

Keywords:

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}$.