ETH Zürich » Computer Science » Theory » Cryptography

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}