{"ID":2853248,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.16991","arxiv_id":"2510.16991","title":"Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\\ell_p$ norms for $p\u003e2$","abstract":"We establish deterministic hardness of approximation results for the Shortest Vector Problem in $\\ell_p$ norm ($\\mathsf{SVP}_p$) and for Unique-SVP ($\\mathsf{uSVP}_p$) for all $p \u003e 2$. Previously, no deterministic hardness results were known, except for $\\ell_\\infty$. For every $p \u003e 2$, we prove constant-ratio hardness: no polynomial-time algorithm approximates $\\mathsf{SVP}_p$ or $\\mathsf{uSVP}_p$ within a ratio of $\\sqrt{2} - o(1)$, assuming $\\textsf{3SAT} \\notin \\text{DTIME}(2^{O(n^{2/3}\\log n)})$, and, $\\textsf{Unambiguous-3SAT} \\notin \\text{DTIME}(2^{O(n^{2/3}\\log n)})$. We also show that for any $\\varepsilon \u003e 0$ there exists $p_\\varepsilon \u003e 2$ such that for every $p \\ge p_\\varepsilon$: no polynomial-time algorithm approximates $\\mathsf{SVP}_p$ within a ratio of $2^{(\\log n)^{1- \\varepsilon}}$, assuming $\\text{NP} \\nsubseteq \\text{DTIME}(n^{(\\log n)^\\varepsilon})$; and within a ratio of $n^{1/(\\log\\log(n))^\\varepsilon}$, assuming $\\text{NP} \\nsubseteq \\text{SUBEXP}$. This improves upon [Haviv, Regev, Theory of Computing 2012], which obtained similar inapproximation ratios under randomized reductions. We obtain analogous results for $\\mathsf{uSVP}_p$ under the assumptions $\\textsf{Unambiguous-3SAT} \\not\\subseteq \\text{DTIME}(n^{(\\log n)^\\varepsilon})$ and $\\textsf{Unambiguous-3SAT} \\not\\subseteq \\text{SUBEXP}$, improving the previously known $1+o(1)$ [Stephens-Davidowitz, Approx 2016]. Strengthening the hardness of $\\textsf{uSVP}$ has direct cryptographic impact. By the reduction of Lyubashevsky and Micciancio [Lyubashevsky, Micciancio, CRYPTO 2009], hardness for $γ$-$\\mathsf{uSVP}_p$ carries over to ${\\frac{1}γ}$-$\\mathsf{BDD}_p$ (Bounded Distance Decoding). Thus, understanding the hardness of $\\textsf{uSVP}$ improves worst-case guarantees for two core problems that underpin security in lattice-based cryptography.","short_abstract":"We establish deterministic hardness of approximation results for the Shortest Vector Problem in $\\ell_p$ norm ($\\mathsf{SVP}_p$) and for Unique-SVP ($\\mathsf{uSVP}_p$) for all $p \u003e 2$. Previously, no deterministic hardness results were known, except for $\\ell_\\infty$. For every $p \u003e 2$, we prove constant-ratio hardness...","url_abs":"https://arxiv.org/abs/2510.16991","url_pdf":"https://arxiv.org/pdf/2510.16991v1","authors":"[\"Yahli Hecht\",\"Muli Safra\"]","published":"2025-10-19T20:17:26Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.CR\"]","methods":"[]","has_code":false}