Loading...
research article
Improved hardness results for unique shortest vector problem
The unique shortest vector problem on a rational lattice is the problem of finding the shortest non-zero vector under the promise that it is unique (up to multiplication by -1). We give several incremental improvements on the known hardness of the unique shortest vector problem (uSVP) using standard techniques. This includes a deterministic reduction from the shortest vector problem to the uSVP, the NP-hardness of uSVP on (1 + 1/poly(n))-unique lattices, and a proof that the decision version of uSVP defined by Cai [4] is in co-NP for n(1/4)-unique lattices. (C) 2016 Published by Elsevier B.V.
Type
research article
Web of Science ID
WOS:000380069200007
Authors
Publication date
2016
Publisher
Published in
Volume
116
Issue
10
Start page
631
End page
637
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
October 18, 2016
Use this identifier to reference this record