Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
This provides a theoretical foundation for lattice-based cryptography by establishing deterministic hardness results across norms, which is crucial for security proofs in cryptographic applications.
The paper tackles the hardness of approximating the shortest vector problem (SVP) for lattices in all finite ℓ_p norms, showing that under a complexity assumption, it is hard to approximate within a factor of 2^{(log n)^{1 - o(1)}} via a deterministic reduction, improving upon prior results that lacked deterministic reductions even for exact SVP in the Euclidean norm.
We show that, assuming NP $\not\subseteq$ $\cap_{δ> 0}$DTIME$\left(\exp{n^δ}\right)$, the shortest vector problem for lattices of rank $n$ in any finite $\ell_p$ norm is hard to approximate within a factor of $2^{(\log n)^{1 - o(1)}}$, via a deterministic reduction. Previously, for the Euclidean case $p=2$, even hardness of the exact shortest vector problem was not known under a deterministic reduction.