Deterministic Hardness-of-Approximation of Unique-SVP and GapSVP in ℓ p \ell_{p} norms for p > 2 p>2

Yahli Hecht, Muli Safra · 2025

Read Deterministic Hardness-of-Approximation of Unique-SVP and GapSVP in ℓ p \ell_{p} norms for p > 2 p>2 by Yahli Hecht, Muli Safra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16991.txt.

Introduction

Yahli Hecht and Muli Safra prove firm hardness results for lattice problems in a 2025 paper. The Shortest Vector Problem asks for the shortest nonzero vector in a lattice. A lattice is a regular grid of points in high dimensions. The unique variant promises one shortest vector stands apart.

Earlier hardness results relied on randomized arguments, except one norm. The authors now prove deterministic hardness for every relevant norm family. No efficient algorithm can approximate these problems within set ratios. That conclusion rests on standard assumptions about hard logic problems. For some norms, the forbidden approximation ratios grow huge. The results improve on earlier randomized work by Haviv and Regev. They matter because lattice problems underpin proposed post-quantum cryptography.

Catalog record

CREATORYahli Hecht, Muli Safra
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16991

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Deterministic Hardness-of-Approximation of Unique-SVP and GapSVP in ℓ p \ell_{p} norms for p > 2 p>2 Yahli Hecht, Muli Safra Abstract We establish deterministic hardness of approximation results for the Shortest Vector Problem in ℓ p \ell_{p} norm ( 𝖲𝖵𝖯 p \mathsf{SVP}_{p} ) and for Unique-SVP ( 𝗎𝖲𝖵𝖯 p \mathsf{uSVP}_{p} )—namely, instances promised to have a unique shortest vector—for all p > 2 p>2 . Previously, no deterministic hardness results were known, except for ℓ ∞ \ell_{\infty} . For every p > 2 p>2 , we prove constant-ratio hardness: no polynomial-time algorithm approximates 𝖲𝖵𝖯 p \mathsf{SVP}_{p}\, or 𝗎𝖲𝖵𝖯 p \mathsf{uSVP}_{p}\, within a ratio of 2 − o ⁡ ( 1 ) \sqrt{2}-o(1) , assuming 3SAT ∉ DTIME ​ ( 2 O ⁡ ( n 2 / 3 ​ log ⁡ n ) ) \textsf{3SAT}\notin\text{DTIME}(2^{O(n^{2/3}\log n)}) , and, respectively, Unambiguous-3SAT ∉ DTIME ​ ( 2 O ⁡ ( n 2 / 3 ​ log ⁡ n ) ) \textsf{Unambiguous-3SAT}\notin\text{DTIME}(2^{O(n^{2/3}\log n)}) . We also show that for any ε > 0 \varepsilon>0 there exists p ε > 2 p_{\varepsilon}>2 such that for every p ≥ p ε p\geq p_{\varepsilon} : no polynomial-time algorithm approximates 𝖲𝖵𝖯 p \mathsf{SVP}_{p}\, within a ratio of 2 ( log ⁡ n ) 1 − ε 2^{(\log n)^{1-\varepsilon}} , assuming NP ⊈ DTIME ​ ( n ( log ⁡ n ) ε ) \text{NP}\nsubseteq\text{DTIME}(n^{(\log n)^{\varepsilon}}) ; and within a ratio of n 1 / ( log ⁡ log ⁡ ( n ) ) ε n^{1/(\log\log(n))^{\varepsilon}} , assuming NP ⊈ SUBEXP \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 𝗎𝖲𝖵𝖯 p \mathsf{uSVP}_{p}\, under the assumptions Unambiguous-3SAT ⊈ DTIME ​ ( n ( log ⁡ n ) ε ) \textsf{Unambiguous-3SAT}\not\subseteq\text{DTIME}(n^{(\log n)^{\varepsilon}}) and Unambiguous-3SAT ⊈ SUBEXP \textsf{Unambiguous-3SAT}\not\subseteq\text{SUBEXP} , improving the previously known 1 + o ⁡ ( 1 ) 1+o(1) [Stephens-Davidowitz, Approx 2016]. Strengthening the hardness of uSVP at weaker approximation ratios has direct cryptographic impact. By the reduction of Lyubashevsky and Micciancio [Lyubashevsky, Micciancio, CRYPTO 2009], hardness for γ \gamma – 𝗎𝖲𝖵𝖯 p \mathsf{uSVP}_{p} carries over to 1 γ {\frac{1}{\gamma}} – 𝖡𝖣𝖣 p \mathsf{BDD}_{p} (Bounded Distance Decoding). Thus, understanding the hardness of uSVP improves worst-case guarantees for the two core problems that underpin security in lattice-based cryptography. MnLargeSymbols’164 MnLargeSymbols’171 1 Introduction A lattice {\mathcal{L}}\subseteq\mathbb{R}^{n} is the additive group of all integer linear combinations of d linearly independent vectors. Given a linearly independent matrix M\in\mathbb{R}^{n\times d} , we write {\mathcal{L}}[M]\stackrel{{\scriptstyle def}}{{=}}\{M\cdot\vec{a}\mid\vec{a}\in\mathbb{Z}^{d}\}. For p\in[1,\infty] , the \ell_{p} norm is \lVert x\rVert_{p}=\big(\sum_{i}\lvert x_{i}\rvert^{p}\big)^{1/p} for p<\infty and \lVert x\rVert_{\infty}=\max_{i}\lvert x_{i}\rvert . The length of the shortest nonzero vector is \lambda_{1}^{(p)}({\mathcal{L}})\stackrel{{\scriptstyle def}}{{=}}\min_{v\in{\mathcal{L}}\setminus\{0\}}\lVert v\rVert_{p}, equivalently, the smallest r such that the closed \ell_{p} -ball B_{p}(0,r) contains a nonzero lattice point. More generally, the k -th successive minimum \lambda_{k}^{(p)}({\mathcal{L}}) is the least r for which B_{p}(0,r) contains k linearly independent lattice vectors. The main goal of this paper is to establish deterministic hardness of approximation results for two lattice problems, known as SVP and uSVP . In the \gamma – \mathsf{SVP}_{p}\, problem ( \gamma>1 ), we are given a basis M for {\mathcal{L}}[M] and a radius r , and the goal is to distinguish between the case of \lambda_{1}^{(p)}({\mathcal{L}}[M])\leq r and the case of \lambda_{1}^{(p)}({\mathcal{L}}[M])\geq\gamma r . In the \gamma – \mathsf{uSVP}_{p}\, problem, the YES instances are promised to satisfy \lambda_{2}^{(p)}({\mathcal{L}}[M])\geq\gamma\,\lambda_{1}^{(p)}({\mathcal{L}}[M]) . In words, the shortest vector in \mathcal{L}[M] is unique—the only non-zero vectors in the lattice that are of length less than \gamma\lambda_{1}(\mathcal{L}[M]) are its multiples. A closely related problem is BDD . In the \frac{1}{\gamma} – \mathsf{BDD}_{p} , we are given a basis M and a target vector \vec{t} such that \text{dist}({\mathcal{L}}[M],\vec{t})\leq\frac{1}{\gamma}\lambda_{1}^{(p)} , find the lattice vector closest to \vec{t} . Formal definitions appear in the preliminaries ( Section 2 ). Hardness of SVP. The study of the computational hardness of the shortest vector problem ( SVP ) has a long history. The first hardness result, due to van Emde Boas [ 55 ] , established NP-hardness of SVP in the \ell_{\infty} norm. Ajtai [ 7 ] proved NP-hardness in \ell_{2} , for an inapproximation ratio slightly larger than 1 and via a randomized reduction . Micciancio [ 42 , 43 ] improved the inapproximability ratio within 2^{1/p}-o(1) for all 1\leq p<\infty . For high p , Khot [ 31 ] proved hardness of approximation to within p^{1-\varepsilon} . Khot [ 32 ] later achieved the hardness for every constant inapproximation ratio, by constructing GapSVP instances with an additional structure and utilizing a variant of the tensor product to amplify the gap. Both Micciancio’s and Khot’s reductions are randomized . Allowing random quasi-polynomial reductions, Khot [ 32 ] also established hardness for a ratio of 2^{\log^{{\frac{1}{2}}-\varepsilon}n} . Haviv and Regev [ 27 , 28 ] improved the ratio to 2^{\log^{1-\varepsilon}n} . Under the stronger yet plausible assumption NP \not\subseteq\text{RSUBEXP}=\cap_{\gamma>0}{\text{\small RTIME}(2^{n^{\gamma}})} the ratio reaches n^{O(1/\log\log n)} . Hardness of Unique-SVP. For the unique variant, Kumar and Sivakumar [ 37 ] first proved NP-hardness in \ell_{2} , albeit under randomized reductions. Khoat and Tan [ 38 ] proved NP-hardness of exact uSVP in \ell_{\infty} . In \ell_{p} , the best unconditional hardness factors remain very close to one: Aggarwal and Dubey [ 4 ] proved hardness within 1+1/\mathrm{poly}(n) , and Stephens-Davidowitz [ 54 ] achieved 1+O(\log n/n) . More recently, Jin and Xue [ 29 ] presented a fine-grained hardness result, reaching an inapproximability ratio of 1+\varepsilon . Under certain nonstandard assumptions, [ 10 ] established hardness for every constant ratio \gamma\geq 1 . Lyubashevsky and Micciancio [ 40 ] provided further evidence for the hardness of uSVP , by proving equivalence to GapSVP up to a small polynomial factor of \sqrt{n/\log n} . 1.1 Our results All of the above mentioned hardness of approximation results for \mathsf{SVP}_{p}\, and \mathsf{uSVP}_{p}\, have relied on randomized reductions (beyond \ell_{\infty} ). At the cost of restricting attention to p>2 , we obtain deterministic reductions that match—and sometimes substantially improve upon—existing hardness results. For SVP , we prove hardness of approximation within \sqrt{2}-o(1) for every p>2 , under deterministic sub-exponential reductions. When p is sufficiently large, we deterministically match and strengthen the best known randomized results in the high- p regime, improving the n^{O(1/\log\log n)} ratio of Haviv and Regev [ 28 ] . Theorem 1.1 ( SVP , {p>2} ) . For every constant p>2 , deciding GapSVP in \ell_{p} is hard to approximate within a ratio \sqrt{2}-o(1) , unless 3\textsf{SAT}\in\text{DTIME}\left(2^{O(n^{2/3}\log n)}\right) . Theorem 1.2 ( SVP , high p ) . For every \varepsilon>0 there exists p_{\varepsilon}>2 such that for every p\geq p_{\varepsilon} , GapSVP in \ell_{p} is hard to approximate within a ratio 2^{(\log n)^{1-\varepsilon}} , unless \text{NP}\subseteq\text{DTIME}\left(n^{(\log n)^{\varepsilon}}\right) . Furthermore, under the stronger assumption \text{NP}\nsubseteq\text{SUBEXP} , GapSVP is hard to approximate within a ratio n^{1/(\log\log n)^{\varepsilon}} . Result \ell_{p} Approx. ratio Assumption Prior works Theorem 1.1 p>2 \sqrt{2}-o(1) 3\textsf{SAT}\notin\text{DTIME}\!\left(2^{O(n^{2/3}\log n)}\right) — Theorem 1.2 p\geq p_{\varepsilon} 2^{(\log n)^{1-\varepsilon}} \text{NP}\not\subseteq\text{DTIME}\!\left(n^{(\log n)^{\varepsilon}}\right) 2^{(\log n)^{1-\varepsilon}} ; \text{NP}\not\subseteq\text{RTIME}\!\left(n^{(\log n)^{c}}\right) ; [ 28 ] Theorem 1.2 p\geq p_{\varepsilon} n^{1/(\log\log n)^{\varepsilon}} \text{NP}\nsubseteq\text{SUBEXP} n^{O(1/(\log\log n))} ; \text{NP}\nsubseteq\text{RSUBEXP} ; [ 28 ] Prior hardness results for uSVP lag far behind those for SVP , failing to reach even constant inapproximability

Read the complete text