**Author:** Daniele Micciancio

IEEE
Transactions on Information Theory,
**47**(3):1212-1215 (March 2001)

[BibTeX] [PostScript] [PDF] [doi:10.1109/18.915688]

**Abstract:** We give a new simple proof of the
NP-hardness of the closest vector problem. In addition to being
much simpler than all previously known proofs, the new proof
yields new interesting results about the complexity of the
closest vector problem with preprocessing. This is a variant of
the closest vector problem in which the lattice is specified in
advance, and can be preprocessed for an arbitrarily long amount
of time before the target vector is revealed. We show that there
are lattices for which the closest vector problem remains hard,
regardless of the amount of preprocessing.