On the Inapproximability of the Shortest Vector in a Lattice Within Some Constant Factor

Author(s)
Micciancio, Danielle
Thumbnail
DownloadMIT-LCS-TM-574.pdf (843.4Kb)
Metadata
Show full item record
Abstract
We show that computing the approximate length of the shortest vector in a lattice within a factor c is NP-hard for randomized reductions for any constant c < ? (2).
Date issued
1998-01
URI
https://hdl.handle.net/1721.1/149274
Series/Report no.
MIT-LCS-TM-574
Collections