Publications: Abstract

# Improved hardness results for unique shortest vector problem

## Divesh Aggarwal and Chandan Dubey

 We give several improvements on the known hardness of the unique shortest vector problem. \begin{itemize} \item We give a deterministic reduction from the shortest vector problem to the unique shortest vector problem. As a byproduct, we get deterministic NP-hardness for unique shortest vector problem in the \ell_\infty norm. \item We give a randomized reduction from SAT to uSVP_{1+1/\tpoly(n)}. This shows that uSVP_{1+1/\tpoly(n)} is NP-hard under randomized reductions. \item We show that if GapSVP_{\gamma} \in coNP (or coAM) then uSVP_{\sqrt{\gamma}} \in coNP (coAM respectively). This improves previously known uSVP_{n^{1/4}} \in coAM \cite{Cai98} to uSVP_{(n/\log n)^{1/4}} \in coAM, and from uSVP_{n^{1/2}} \in coNP \cite{LM09} to uSVP_{n^{1/4}} \in coNP. \item We give a deterministic reduction from search-uSVP_{\gamma} to decision-uSVP_{\gamma/2}. \end{itemize}