### Hardness of approximating the shortest vector problem in latticesHardness of approximating the shortest vector problem in lattices

Access Restriction
Subscribed

 Author Khot, Subhash Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2005 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Approximation algorithms ♦ Cryptography ♦ Hardness of approximation ♦ Lattices ♦ Shortest vector problem Abstract Let $\textit{p}$ > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in $ℓ\textit{p}$ norm within a constant factor. Under the stronger assumption NP ⊈ $RTIME(2\textit{poly}(log$ $\textit{n})),$ we show that there is no polynomial-time algorithm with approximation ratio 2(log $n)^{1/2™ε}}$ where $\textit{n}$ is the dimension of the lattice and ε > 0 is an arbitrarily small constant.We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves $\textit{some}$ constant factor hardness. The reduction is based on BCH Codes. Its advantage is that the SVP instances produced by the reduction behave well under the augmented tensor product, a new variant of tensor product that we introduce. This enables us to boost the hardness factor to 2(log $n)^{1/2-ε}}.$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2005-09-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 52 Issue Number 5 Page Count 20 Starting Page 789 Ending Page 808

#### Open content in new tab

Source: ACM Digital Library