[Resource Topic] 2008/366: Unique Shortest Vector Problem for max norm is NP-hard

Welcome to the resource topic for 2008/366

Unique Shortest Vector Problem for max norm is NP-hard

Authors: Than Quang Khoat, Nguyen Hong Tan


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.

ePrint: https://eprint.iacr.org/2008/366

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .