Improved Hardness of BDD and SVP Under Gap-(S)ETH
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916867430416384 |
|---|---|
| author | Bennett, Huck Peikert, Chris Tang, Yi |
| author_facet | Bennett, Huck Peikert, Chris Tang, Yi |
| contents | We show improved fine-grained hardness of two key lattice problems in the $\ell_p$ norm: Bounded Distance Decoding to within an $α$ factor of the minimum distance ($\mathrm{BDD}_{p, α}$) and the (decisional) $γ$-approximate Shortest Vector Problem ($\mathrm{SVP}_{p,γ}$), assuming variants of the Gap (Strong) Exponential Time Hypothesis (Gap-(S)ETH). Specifically, we show:
1. For all $p \in [1, \infty)$, there is no $2^{o(n)}$-time algorithm for $\mathrm{BDD}_{p, α}$ for any constant $α> α_\mathsf{kn}$, where $α_\mathsf{kn} = 2^{-c_\mathsf{kn}}$ and $c_\mathsf{kn}$ is the $\ell_2$ kissing-number constant, assuming $c_\mathsf{kn} > 0$ and that non-uniform Gap-ETH holds.
2. For all $p \in [1, \infty)$, there is no $2^{o(n)}$-time algorithm for $\mathrm{BDD}_{p, α}$ for any constant $α> α^\ddagger_p$, where $α^\ddagger_p$ is explicit and satisfies $α^\ddagger_p = 1$ for $1 \leq p \leq 2$, $α^\ddagger_p < 1$ for all $p > 2$, and $α^\ddagger_p \to 1/2$ as $p \to \infty$, unless randomized Gap-ETH is false.
3. For all $p \in [1, \infty) \setminus 2 \mathbb{Z}$ and all $C > 1$, there is no $2^{n/C}$-time algorithm for $\mathrm{BDD}_{p, α}$ for any constant $α> α^\dagger_{p, C}$, where $α^\dagger_{p, C}$ is explicit and satisfies $α^\dagger_{p, C} \to 1$ as $C \to \infty$ for any fixed $p \in [1, \infty)$, assuming $c_\mathsf{kn} > 0$ and that non-uniform Gap-SETH holds.
4. For all $p > p_0 \approx 2.1397$, $p \notin 2\mathbb{Z}$, and all $C > C_p$, there is no $2^{n/C}$-time algorithm for $\mathrm{SVP}_{p, γ}$ for some constant $γ> 1$, where $C_p > 1$ is explicit and satisfies $C_p \to 1$ as $p \to \infty$, unless randomized Gap-SETH is false. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2109_04025 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Improved Hardness of BDD and SVP Under Gap-(S)ETH Bennett, Huck Peikert, Chris Tang, Yi Computational Complexity Cryptography and Security Data Structures and Algorithms We show improved fine-grained hardness of two key lattice problems in the $\ell_p$ norm: Bounded Distance Decoding to within an $α$ factor of the minimum distance ($\mathrm{BDD}_{p, α}$) and the (decisional) $γ$-approximate Shortest Vector Problem ($\mathrm{SVP}_{p,γ}$), assuming variants of the Gap (Strong) Exponential Time Hypothesis (Gap-(S)ETH). Specifically, we show: 1. For all $p \in [1, \infty)$, there is no $2^{o(n)}$-time algorithm for $\mathrm{BDD}_{p, α}$ for any constant $α> α_\mathsf{kn}$, where $α_\mathsf{kn} = 2^{-c_\mathsf{kn}}$ and $c_\mathsf{kn}$ is the $\ell_2$ kissing-number constant, assuming $c_\mathsf{kn} > 0$ and that non-uniform Gap-ETH holds. 2. For all $p \in [1, \infty)$, there is no $2^{o(n)}$-time algorithm for $\mathrm{BDD}_{p, α}$ for any constant $α> α^\ddagger_p$, where $α^\ddagger_p$ is explicit and satisfies $α^\ddagger_p = 1$ for $1 \leq p \leq 2$, $α^\ddagger_p < 1$ for all $p > 2$, and $α^\ddagger_p \to 1/2$ as $p \to \infty$, unless randomized Gap-ETH is false. 3. For all $p \in [1, \infty) \setminus 2 \mathbb{Z}$ and all $C > 1$, there is no $2^{n/C}$-time algorithm for $\mathrm{BDD}_{p, α}$ for any constant $α> α^\dagger_{p, C}$, where $α^\dagger_{p, C}$ is explicit and satisfies $α^\dagger_{p, C} \to 1$ as $C \to \infty$ for any fixed $p \in [1, \infty)$, assuming $c_\mathsf{kn} > 0$ and that non-uniform Gap-SETH holds. 4. For all $p > p_0 \approx 2.1397$, $p \notin 2\mathbb{Z}$, and all $C > C_p$, there is no $2^{n/C}$-time algorithm for $\mathrm{SVP}_{p, γ}$ for some constant $γ> 1$, where $C_p > 1$ is explicit and satisfies $C_p \to 1$ as $p \to \infty$, unless randomized Gap-SETH is false. |
| title | Improved Hardness of BDD and SVP Under Gap-(S)ETH |
| topic | Computational Complexity Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2109.04025 |