Paper 2008/366

Unique Shortest Vector Problem for max norm is NP-hard

Than Quang Khoat and Nguyen Hong Tan

Abstract

The unique Shortest vector problem (uSVP) in lattice theory plays a crucial role in many public-key cryptosystems. The security of those cryptosystems bases on the hardness of uSVP. However, so far there is no proof for the proper hardness of uSVP even in its exact version. In this paper, we show that the exact version of uSVP for $\ell_\infty$ norm is NP-hard. Furthermore, many other lattice problems including unique Subspace avoiding problem, unique Closest vector problem and unique Generalized closest vector problem, for any $\ell_p$ norm, are also shown to be NP-hard.

Note: The paper deals with the hardness of some lattice problems related to some public-key cryptosystems.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Unique shortest vector problemunique closest vector problemunique subspace avoiding problemLatticeNP-hardLattice-based cryptosystems
Contact author(s)
quangkhoat @ gmail com
History
2008-09-28: revised
2008-08-27: received
See all versions
Short URL
https://ia.cr/2008/366
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/366,
      author = {Than Quang Khoat and Nguyen Hong Tan},
      title = {Unique Shortest Vector Problem for max norm is NP-hard},
      howpublished = {Cryptology ePrint Archive, Paper 2008/366},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/366}},
      url = {https://eprint.iacr.org/2008/366}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.