Loading...
Please wait, while we are loading the content...
Similar Documents
Unique shortest vector problem for max norm is np-hard.
| Content Provider | CiteSeerX |
|---|---|
| Author | Khoat, Than Quang Tan, Nguyen Hong |
| Abstract | 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 ℓ ∞ 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 ℓp norm, are also shown to be NP-hard. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Unique Shortest Vector Problem Max Norm Exact Version Cryptosystems Base Crucial Role Vector Problem Unique Closest Vector Problem Proper Hardness Many Lattice Problem Many Public-key Cryptosystems Unique Subspace Avoiding Problem Lattice Theory Unique Generalized |
| Content Type | Text |
| Resource Type | Article |
