IACR News item: 06 February 2013
Kuan Cheng
ePrint Report
In this paper, first, it is proved that finding the approximate shortest vector could be Karp-reduced to GapSVP.
Second, it is proved that shortest vector problem itself could be reduced to GapSVP with a quite small gap.
Third, we improve the complexity results of uSVP, proving uSVP could be reduced from SVP (our results are better than any known result). What\'s more, we prove that the search version of uSVP could be reduced to decisional version of uSVP with almost the same gap.
Additional news items may be found on the IACR news page.