Cryptology ePrint Archive: Report 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.

Category / Keywords: Unique shortest vector problem, unique closest vector problem, unique subspace avoiding problem, Lattice, NP-hard, Lattice-based cryptosystems

Date: received 25 Aug 2008, last revised 28 Sep 2008

Contact author: quangkhoat at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20080928:082710 (All versions of this report)

Short URL: ia.cr/2008/366

Discussion forum: Show discussion | Start new discussion