Fine-grained deterministic hardness of the shortest vector problem
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918402769027072 |
|---|---|
| author | Hittmeir, Markus |
| author_facet | Hittmeir, Markus |
| contents | Let $γ$-$\mathsf{GapSVP}_p$ be the decision version of the shortest vector problem in the $\ell_p$-norm with approximation factor $γ$, let $n$ be the lattice rank and $0<\varepsilon\leq 1$. We prove that there is no algorithm that solves $(2-\varepsilon)$-$\mathsf{GapSVP}_p$ uniformly for all $p\in\mathbb{N}$ in time\[
2^{2^{o(p)}}\cdot 2^{o(n)},\] unless the Exponential Time Hypothesis is false. The proof is based on a deterministic Karp reduction from a constrained variant of the subset-sum problem to $\mathsf{GapSVP}_p$ for fixed $p$. While most hardness results for the shortest vector problem in finite norms rely on randomized reductions, our method is entirely deterministic. As a consequence, we also obtain a deterministic Karp reduction from the standard subset-sum problem to $(2-\varepsilon)$-$\mathsf{GapSVP}_{\infty}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_01626 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fine-grained deterministic hardness of the shortest vector problem Hittmeir, Markus Number Theory 11H06, 11Y16 Let $γ$-$\mathsf{GapSVP}_p$ be the decision version of the shortest vector problem in the $\ell_p$-norm with approximation factor $γ$, let $n$ be the lattice rank and $0<\varepsilon\leq 1$. We prove that there is no algorithm that solves $(2-\varepsilon)$-$\mathsf{GapSVP}_p$ uniformly for all $p\in\mathbb{N}$ in time\[ 2^{2^{o(p)}}\cdot 2^{o(n)},\] unless the Exponential Time Hypothesis is false. The proof is based on a deterministic Karp reduction from a constrained variant of the subset-sum problem to $\mathsf{GapSVP}_p$ for fixed $p$. While most hardness results for the shortest vector problem in finite norms rely on randomized reductions, our method is entirely deterministic. As a consequence, we also obtain a deterministic Karp reduction from the standard subset-sum problem to $(2-\varepsilon)$-$\mathsf{GapSVP}_{\infty}$. |
| title | Fine-grained deterministic hardness of the shortest vector problem |
| topic | Number Theory 11H06, 11Y16 |
| url | https://arxiv.org/abs/2511.01626 |