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

Files and Links

  • There are currently no associated files available.