# Information Security and Cryptography Research Group

## 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,
}