
arXiv: 2504.02695
We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al. [BHIRW24], who gave a polynomial-time reduction from $\mathsf{3SAT}$ to the (gap) $\mathsf{MAXLIN}$ problem-a class of CSPs with linear equations over finite fields-we derive ETH-hardness for several lattice problems. First, we show that for any $p \in [1, \infty)$, there exists an explicit constant $γ> 1$ such that $\mathsf{CVP}_{p,γ}$ (the $\ell_p$-norm approximate Closest Vector Problem) does not admit a $2^{o(n)}$-time algorithm unless ETH is false. Our reduction is deterministic and proceeds via a direct reduction from (gap) $\mathsf{MAXLIN}$ to $\mathsf{CVP}_{p,γ}$. Next, we prove a randomized ETH-hardness result for $\mathsf{SVP}_{p,γ}$ (the $\ell_p$-norm approximate Shortest Vector Problem) for all $p > 2$. This result relies on a novel property of the integer lattice $\mathbb{Z}^n$ in the $\ell_p$ norm and a randomized reduction from $\mathsf{CVP}_{p,γ}$ to $\mathsf{SVP}_{p,γ'}$. Finally, we improve over prior reductions from $\mathsf{3SAT}$ to $\mathsf{BDD}_{p, α}$ (the Bounded Distance Decoding problem), yielding better ETH-hardness results for $\mathsf{BDD}_{p, α}$ for any $p \in [1, \infty)$ and $α> α_p^{\ddagger}$, where $α_p^{\ddagger}$ is an explicit threshold depending on $p$. We additionally observe that prior work implies ETH hardness for the gap minimum distance problem ($γ$-$\mathsf{MDP}$) in codes.
FOS: Computer and information sciences, Computer Science - Computational Complexity, Computer Science - Cryptography and Security, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Computational Complexity (cs.CC), Cryptography and Security (cs.CR)
FOS: Computer and information sciences, Computer Science - Computational Complexity, Computer Science - Cryptography and Security, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Computational Complexity (cs.CC), Cryptography and Security (cs.CR)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
