## Improved hardness results for unique shortest vector problem

### Divesh Aggarwal and Chandan Dubey

In submission, 2012.

We give several improvements on the known hardness of the unique shortest vector problem.

- 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.
- 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.
- 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.
- We give a deterministic reduction from search-uSVP_{\gamma} to decision-uSVP_{\gamma/2}.

## BibTeX Citation

@inproceedings{AggDub12, author = {Divesh Aggarwal and Chandan Dubey}, title = {Improved hardness results for unique shortest vector problem}, booktitle = {In submission}, year = {2012}, }

## Files and Links

- There are currently no associated files available.