Mind the Gap? Not for SVP Hardness Under ETH!

We define ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ to be a decision version of the Closest Vector Problem, where given a matrix $B$ over, say, integers, a target vector $𝒕$, and a radius $r$, the goal is to decide if there exists a lattice vector $𝒗\in ℒ(B)$ such that ${\Vert 𝒗-𝒕\Vert }_p\le r$, or for all lattice vectors $𝒗$, ${\Vert 𝒗-𝒕\Vert }_p>\gamma r$. Here $ℒ(B)$ is the lattice generated by the columns of $B$. Our first result says that for any $p\in [1,\mathrm{\infty })$, there is no sub-exponential (in the dimension of the lattice) algorithm for ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ for some (explicit) constant $\gamma >1$, unless the Exponential Time Hypothesis is false.

To prove this, we give a deterministic Karp reduction from $\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$ over, say, $n$ variables and $m$ equations to ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ in a lattice in $m$ dimensions.

We define ${\mathrm{𝖲𝖵𝖯}}_{p,\gamma }$ to be a decision version of the approximate shortest vector problem, where given a matrix $B$ over, say, integers, and a radius $r$, the goal is to decide if there exists a lattice vector $𝒗$ such that ${\Vert 𝒗\Vert }_p\le r$, or if for all lattice vectors $𝒗$, we have that ${\Vert 𝒗\Vert }_p>\gamma r$. Our main result is that for any $p>2$, unless the randomized Exponential Time Hypothesis is false, there is no sub-exponential time algorithm for ${\mathrm{𝖲𝖵𝖯}}_{p,\gamma }$ for an explicit constant $\gamma >1$.

To prove this theorem we show a novel property of the integer lattice ${\mathbb{Z}}^n$, which says that for any $p>2$ there are exponentially more lattice vectors close (in the ${\mathrm{\ell }}_p$ norm) to $\frac{1}{2}{\mathrm{𝟏}}_n$, than the number of short vectors, i.e., vectors around the origin. Then we borrow techniques from [11] to show that we can use the ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ instances constructed in the proof of Theorem 1.1 to generate an ${\mathrm{𝖲𝖵𝖯}}_{p,{\gamma }^{\prime }}$ instance for some ${\gamma }^{\prime }>1$ via a Karp reduction. Chaining together the efficient reductions from $\mathrm{𝟥}𝖲𝖠𝖳$ to (gap) $\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$, from (gap) $\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$ to ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ and from ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ to ${\mathrm{𝖲𝖵𝖯}}_{p,{\gamma }^{\prime }}$, we get our result.

We note that the reduction from $k$-$\mathrm{𝖲𝖠𝖳}$ to ${\mathrm{𝖢𝖵𝖯}}_{\mathrm{\infty }}$ and ${\mathrm{𝖲𝖵𝖯}}_{\mathrm{\infty }}$ in [25, Corollary 6.7] achieves a gap of ${\gamma }_p=1+2/(k-1)$. Therefore for $k=3$, they get a gap of $2$, and hence we know the $\mathrm{𝖤𝖳𝖧}$ hardness of ${\mathrm{𝖢𝖵𝖯}}_{\mathrm{\infty },\gamma }$ and ${\mathrm{𝖲𝖵𝖯}}_{\mathrm{\infty },\gamma }$ for $\gamma =2$ since their work.

We define ${\mathrm{𝖡𝖣𝖣}}_{p,\alpha }$ to be the following search problem. The input is a matrix $B$ over, say, integers and a target vector $𝒕$ under the promise that there exists a lattice vector $𝒗$ at a distance at most $\alpha \cdot {\lambda }_1^{(p)}(ℒ(B))$, where ${\lambda }_1^{(p)}(ℒ(B))$ is the length of the shortest non-zero vector in $ℒ(B)$ in the ${\mathrm{\ell }}_p$ norm. The goal is to find a lattice vector closest to $𝒕$. We show that for any $p\in [1,\mathrm{\infty })$, there is an efficient decision-to-search reduction from ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ over a lattice over integers to ${\mathrm{𝖡𝖣𝖣}}_{p,\alpha }$, for any constant $\gamma$ and $\alpha >{\alpha }_p^{‡}$, where ${\alpha }_p^{‡}$ is an explicit constant defined in Equation 4, such that ${\alpha }_p^{‡}=1$ for $p\in [1,2]$, for $p>2$, and ${\alpha }_p^{‡}\to 1/2$ as $p\to \mathrm{\infty }$.

As a consequence, combining this result with our reduction from (gap) $\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$ to ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$, we get that for any $p\in [1,\mathrm{\infty })$, $\alpha >{\alpha }_p^{‡}$, there is no sub-exponential time algorithm for ${\mathrm{𝖡𝖣𝖣}}_{p,\alpha }$, unless the randomized Exponential Time Hypothesis is false.

A linear code is a subspace of ${𝔽}_q^m$, for some prime power $q$. Given a full rank generator matrix $C\in {𝔽}_q^{m\times n}$, such that $1\le n\le m$, the $q$-ary code generated by $C$ is

The elements of $𝒞$ are known as codewords. The nearest codeword problem ($\mathrm{𝖭𝖢𝖯}$) asks to find the minimal Hamming distance between a given target vector and a codeword in a given linear code. This problem can be thought of as the code equivalent of the closest vector problem ($\mathrm{𝖢𝖵𝖯}$) over lattices. Similarly, the $\mathrm{𝖲𝖵𝖯}$ equivalent over codes is the minimum distance problem for linear codes ($\mathrm{𝖬𝖣𝖯}$), that asks to find the minimal Hamming weight of a non-zero code word in a given code. Observe that the $\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$ problem is essentially the $\mathrm{𝖭𝖢𝖯}$ problem in disguise.

In [70], the authors studied the $\mathrm{𝖲𝖤𝖳𝖧}$ and $\mathrm{𝖦𝖺𝗉𝖤𝖳𝖧}$ hardness of $\mathrm{𝖬𝖣𝖯}$ and $\mathrm{𝖭𝖢𝖯}$. They give a reduction from $k$-$\mathrm{𝖲𝖠𝖳}$ (Max-$k$-$\mathrm{𝖲𝖠𝖳}$) to ($\gamma$-approximate) $\mathrm{𝖭𝖢𝖯}$, establishing $\mathrm{𝖲𝖤𝖳𝖧}$ ($\mathrm{𝖦𝖺𝗉𝖤𝖳𝖧}$) hardness of ($\gamma$ approximate) $\mathrm{𝖭𝖢𝖯}$. Here $\gamma >1$ is a constant. Moreover, they give a reduction from $\gamma$-$\mathrm{𝖭𝖢𝖯}$ in rank $n$ to ${\gamma }^{\prime }$-$\mathrm{𝖬𝖣𝖯}$ in rank $Cn$ for constants $C$, ${\gamma }^{\prime }$, thereby showing $\mathrm{𝖦𝖺𝗉𝖤𝖳𝖧}$ hardness of ${\gamma }^{\prime }$-$\mathrm{𝖬𝖣𝖯}$. We note that this reduction can be thought of as a reduction from ${\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}}_{\epsilon }$ for a constant $\epsilon$ in $n$ variables to $\gamma$-$\mathrm{𝖬𝖣𝖯}$ in rank $n$, for another constant $\gamma$. Thus, we get $\mathrm{𝖤𝖳𝖧}$ hardness of $\gamma$-$\mathrm{𝖬𝖣𝖯}$ for some constant $\gamma$ for free.

$\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$ is one of the classical $\mathrm{𝖭𝖯}$-hard approximation problems [41]. An instance of $\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$ is of the form $(M,𝒗)$, where $M\in {𝔽}^{m\times n},𝒗\in {𝔽}^m$ have entries from a finite field $𝔽$. The goal is to find a vector $𝒙\in {𝔽}^n$ that satisfies as many linear equations $M_i\cdot 𝒙=v_i$ as possible. The gap version ${\mathrm{𝗀𝖺𝗉}}_{c,s}\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$ is a promise problem where an instance $(M,𝒗)$ is a $\mathrm{𝖸𝖤𝖲}$ instance if there exists a vector $𝒙\in {𝔽}^n$ that satisfies at least $cm$ of the linear equations, and a $\mathrm{𝖭𝖮}$ instance if every vector $𝒙\in {𝔽}^n$ satisfies at most $sm$ of the linear equations. [29] showed that there is a Karp reduction from $\mathrm{𝟥}𝖲𝖠𝖳$ to ${\mathrm{𝗀𝖺𝗉}}_{c,s}\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$ for $c=5/8$ and $s=5/8-\epsilon$ for an explicit constant $\epsilon >0$. This implies that ${\mathrm{𝗀𝖺𝗉}}_{c,s}\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$ is $\mathrm{𝖤𝖳𝖧}$ hard. From now on, we write ${\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}}_{\epsilon }$ to denote ${\mathrm{𝗀𝖺𝗉}}_{c,s}\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$ over ${𝔽}_2$, for $c=5/8$ and $s=5/8-\epsilon$.

To prove Theorem 1.1, we show a deterministic Karp reduction from ${\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}}_{\epsilon }$ to ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ for a constant $\gamma :={\left(1+8\epsilon /3\right)}^{1/p}$. Consider the following matrix-vector pair

where $I_m$ is the identity matrix. Consider the lattice generated by $B$. Appending $2I_m$ to $M$ ensures that distances between the lattice points in $ℒ(B)$ to the target vector $𝒕$ are computed modulo 2. Precisely, the presence of $2I_m$ enforces that for any lattice point $B𝒙$, the coordinates of the difference $B𝒙-𝒕$ remains within an equivalence class mod 2, effectively reducing the computations to over ${𝔽}_2$. Therefore, we are able to show that if the input was a $\mathrm{𝖸𝖤𝖲}$ instance of ${\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}}_{\epsilon }$, then there exists a lattice vector in $ℒ(B)$ that is at distance at most $r:={(3m/8)}^{1/p}$ from the target vector $𝒕$; and if the input was a $\mathrm{𝖭𝖮}$ instance of ${\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}}_{\epsilon }$, then for all lattice vectors in $ℒ(B)$, their distance to the target vector $𝒕$ is at least $\gamma r$. Thus, $(B,𝒕,r)$ is an instance of ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$.

Aggarwal and Stephens-Davidowitz [11] showed $\mathrm{𝖦𝖺𝗉𝖤𝖳𝖧}$ hardness of ${\mathrm{𝖲𝖵𝖯}}_{p,\gamma }$ for all $p>2$. Using ideas from Khot [48], they reduced an instance of (gap) $\mathrm{𝖤𝗑𝖺𝖼𝗍𝖲𝖾𝗍𝖢𝗈𝗏𝖾𝗋}$ over $m$ sets and a universe of size $k$, to ${\mathrm{𝖲𝖵𝖯}}_{p,\gamma }$, using an auxiliary gadget, a lattice-target pair $(B^{†},{𝒕}^{†})$ of dimension $d^{†}$. Precisely, they used the input $\mathrm{𝖤𝗑𝖺𝖼𝗍𝖲𝖾𝗍𝖢𝗈𝗏𝖾𝗋}$ instance to define a lattice $\widehat{ℒ}\subset {ℝ}^{m+k}$ generated by a matrix $\widehat{B}$, and a vector $\widehat{𝒕}$. Define

Denote the number of vectors at a radius at most $r$ around $𝒕$ in the lattice $ℒ(B)$ by $N_p(ℒ(B),r,𝒕)$. They show that for a certain choice of $B^{†}$, if the $\mathrm{𝖤𝗑𝖺𝖼𝗍𝖲𝖾𝗍𝖢𝗈𝗏𝖾𝗋}$ instance is a $\mathrm{𝖸𝖤𝖲}$ instance, then $N_p(ℒ(B),r,𝒕)$ is exponentially larger than $N_p(ℒ(B),\gamma r,𝒕)$ if it were a $\mathrm{𝖭𝖮}$ instance. Then they define a (generating set of a) lattice

for some $s$, and use a lattice sparsification algorithm (Section 2.5) to sample a random (sparser) sub-lattice ${ℒ}^{\prime \prime }\subseteq ℒ(B^{\prime })$ such that if the input $\mathrm{𝖤𝗑𝖺𝖼𝗍𝖲𝖾𝗍𝖢𝗈𝗏𝖾𝗋}$ instance was a $\mathrm{𝖸𝖤𝖲}$ instance, at least one lattice vector of length at most $r$ survives in ${ℒ}^{\prime \prime }$, and if it were a $\mathrm{𝖭𝖮}$ instance, then all lattice vectors of length at least $\gamma r$ die. Together with a reduction from $\mathrm{𝖦𝖺𝗉𝟥𝖲𝖠𝖳}$ to $\mathrm{𝖤𝗑𝖺𝖼𝗍𝖲𝖾𝗍𝖢𝗈𝗏𝖾𝗋}$, they get the $\mathrm{𝖦𝖺𝗉𝖤𝖳𝖧}$ hardness of ${\mathrm{𝖲𝖵𝖯}}_{p,\gamma }$ for all $p>2$.

They pick the gadget $(B^{†},{𝒕}^{†})$ so that if the input $\mathrm{𝖤𝗑𝖺𝖼𝗍𝖲𝖾𝗍𝖢𝗈𝗏𝖾𝗋}$ instance was a $\mathrm{𝖸𝖤𝖲}$ instance, then it blows up the number of short lattice vector exponentially, whereas if it were a $\mathrm{𝖭𝖮}$ instance, the number of short lattice vectors remains small. This corresponds to a gadget that has exponentially more close vectors than short vectors. (We usually call such a lattice-target pair a locally dense gadget.) They show that for all $p>2$, the integer lattice ${\mathbb{Z}}^d$, along with the vector $𝒕:=t\cdot {\mathrm{𝟏}}_d$ for some $t\in (0,1/2]$ satisfies this property. To see this, for any $\tau >0,t\in [0,1/2]$ define the theta function

Notice that

This implies that

Therefore, the theta function can be used to find an upper bound to the number of lattice vectors close to $𝒕$ in the ${\mathrm{\ell }}_p$ norm. In fact, the above inequality is quite strict. It has been shown [56, 37, 11] that ${\mathrm{\Theta }}_p(\tau ,𝒕)$ can be used to approximate the number of integer points in an ${\mathrm{\ell }}_p$ ball up to sub-exponential factors. Thus, there exists a vector of the form $t\cdot {\mathrm{𝟏}}_d$ for some $t\in (0,1/2]$ such that there are exponentially more close lattice vectors in the integer lattice than short lattice vectors if and only if there exists a $\tau >0$ and a $t\in (0,1/2]$ such that ${\mathrm{\Theta }}_p(\tau ,t)>{\mathrm{\Theta }}_p(\tau ,0)$. They show that this is true for all $p>2$ [11, Section 6].

Unfortunately, a similar reduction breaks down if we start from ${\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}}_{\epsilon }$ instead of $\mathrm{𝖤𝗑𝖺𝖼𝗍𝖲𝖾𝗍𝖢𝗈𝗏𝖾𝗋}$. This is because while counting the number of short (annoying) vectors in the no case (say $A$), they [11] exploit the fact that for any non-zero integer $\mathrm{\ell }$, ${\mathrm{dist}}_p(\widehat{ℒ},\mathrm{\ell }\widehat{𝒕})$ is sufficiently large. Therefore they only have to count the number of vectors in $ℒ(B^{†})$ around $\mathrm{\ell }{𝒕}^{†}$ in a much smaller radius. When we define the corresponding $\mathrm{𝖢𝖵𝖯}$ instance in Equation 1, for every even integer $2\mathrm{\ell }$, the vector $2\mathrm{\ell }𝒕\in ℒ(B)$, and therefore we cannot use a similar trick.

We can, however, construct a gadget that has a stronger property: for every even multiple of the target, $2\mathrm{\ell }{𝒕}^{†}$, it holds that the number of lattice points in $ℒ(B^{†})$ around ${𝒕}^{†}$ are exponentially more than those around $2\mathrm{\ell }{𝒕}^{†}$. This would compensate for the increase in radius incurred in our situation. In Section 4.1 we show that for all $p>2$ the integer lattice $(ℒ(B^{†})={\mathbb{Z}}^d)$ and the target ${𝒕}^{†}=\frac{1}{2}{\mathrm{𝟏}}_d$ satisfies this property. This is because with this choice, every even multiple would be an integer vector. Thus, for some , if the gadget satisfies the property that $N_p(ℒ(B^{†}),r^{\prime },{𝒕}^{†})$ is exponentially more than $N_p(ℒ(B^{†}),r,\mathrm{𝟎})$, then for every even integer $2\mathrm{\ell }$, it holds that $N_p(ℒ(B^{†}),r^{\prime },{𝒕}^{†})$ is exponentially more than $N_p(ℒ(B^{†}),r,2\mathrm{\ell }{𝒕}^{†})$.

One of the main technical ingredients, which could be of independent interest, is Theorem 4.1, where we use Fourier analysis to show that for any $p>2$, there always exists $\tau >0$ such that

Since ${\mathrm{\Theta }}_p(\tau ,1/2)$ and ${\mathrm{\Theta }}_p(\tau ,0)$ are absolutely convergent, this can be proved by analyzing the difference series

In other words, it suffices to show that for all $p>2$, there always exists $\tau >0$ such that $f_p(\tau )>0$. When $p$ is significantly bounded away from $2$, e.g., for $p\ge 2.2$, we can simply take a constant $\tau =2$, which yields

since $e^{-2{(z-1/2)}^p}-e^{-2z^p}>0$ for all $z\in {\mathbb{Z}}^{+}$. However, as $p$ gets closer to 2, if we still fix some constant $\tau$, we will need more than just the first term of the series, but the required number of terms will depend on $p$, making such an analysis no longer feasible.

Before illustrating our proof idea for $p$ close to $2$, let us first discuss the case for $p=2$. Interestingly, the above conclusion is known to be false for $p=2$ by [21, Corollary 1.2], i.e., for all $\tau >0$. We now introduce a novel approach to handle the $p=2$ case, which will also be instructive for the $p>2$ case. The fourth Jacobi theta function is defined by

Note that $f_2(\tau )=-{\vartheta }_4(0,e^{-\tau /4})$. It is well-known that the fourth Jacobi theta function ${\vartheta }_4(x,q)$ can be expressed in terms of the second Jacobi theta function

by Jacobi’s imaginary transformation [45]. Specifically, we can obtain

which implies for all $\tau >0$ and concludes the $p=2$ case. Essentially, the trick relies on Jacobi’s imaginary transformation, which turns an alternating series into a non-alternating series with all positive terms. So, this motivates us to find a transformation that can also rewrite $f_p(\tau )$ for $p>2$ in the spirit of the principles behind Jacobi’s imaginary transformation. Note that Jacobi’s imaginary transformation is obtained by the Poisson summation formula [63], which states that for any function¹¹1$L^1(ℝ)$ denotes the space of Lebesgue integrable functions on $ℝ$, i.e., $f\in L^1(ℝ)$ if . $s(z)\in L^1(ℝ)$, if its Fourier transform $\widehat{s}(x)\in L^1(ℝ)$, then

Following this new perspective, we outline the proof for the $p>2$ case as follows. We first slightly rewrite the difference series $f_p(\tau ):={\mathrm{\Theta }}_p(\tau ,1/2)-{\mathrm{\Theta }}_p(\tau ,0)$ to match the Poisson summation formula and let $p=2+\epsilon$ for $\epsilon >0$:

By Lemmas 4.2 and 4.3, we show that both $s_{\tau ,\epsilon }(z),{\widehat{s}}_{\tau ,\epsilon }(x)\in L^1(ℝ)$, to ensure that the Poisson summation formula ${\sum }_{z\in \mathbb{Z}}{s}_{\tau ,\epsilon }(z)={\sum }_{x\in \mathbb{Z}}{\widehat{s}}_{\tau ,\epsilon }(x)$ can be applied. Then it suffices to show that for any $\epsilon >0$, there exists some sufficiently small $\tau >0$ such that for every $x\in \mathbb{Z}$, . To find such $\tau$, we consider the asymptotic expansion for the Fourier transform of the super-Gaussian $g(z):=e^{-{\left|z\right|}^{2+\epsilon }}$, i.e., ${\widehat{g}}_{\epsilon }(x):={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}{e}^{-{\left|z\right|}^{2+\epsilon }-2\pi ixz}𝑑z$. This has been studied in [37] (restated as Lemma 2.2), which demonstrates that for all sufficiently large $x$. We then relate ${\widehat{s}}_{\tau ,\epsilon }(x)$ to ${\widehat{g}}_{\epsilon }(x^{\prime })$ where $x^{\prime }$ is obtained from $x$ by a translation and a scaling that depend on $\tau$ and $\epsilon$. Thus, for every $\epsilon >0$, we can choose an appropriate $\tau$ such that $x^{\prime }$ is large enough for all $x\in \mathbb{Z}$, and thereby conclude that for all $x\in \mathbb{Z}$. This implies that for every $\epsilon >0$, the difference series $f_{2+\epsilon }(\tau )=-{\sum }_{x\in \mathbb{Z}}{\widehat{s}}_{\tau ,\epsilon }(x)>0$ for some $\tau >0$, which completes the proof for Theorem 4.1.

Putting them together, we get Theorem 4.4, which says that for any $p>2$, we can find a radius $r$ such that for any $d$, the integer lattice contains exponentially many points within a distance $r$ around $1/2\cdot {\mathrm{𝟏}}_d$ than around any of its even multiple. Using these gadgets in our reduction, Theorem 1.2 follows.

We leave $p=2$ as an open problem. Note that the $\mathrm{𝖤𝖳𝖧}$ hardness of ${\mathrm{𝖲𝖵𝖯}}_{p,\gamma }$ for $p\in [1,2)$ follows from the $\mathrm{𝖤𝖳𝖧}$ hardness of $p=2$ by the norm embedding techniques of [66].

Prove that for any $p\in [1,2]$, there exists a constant $\gamma >1$ such that assuming $\mathrm{𝖤𝖳𝖧}$ there are no sub-exponential time algorithms for ${\mathrm{𝖲𝖵𝖯}}_{p,\gamma }$.

Bounded distance decoding is a lattice problem that has found applications in showing hardness results for important cryptographic primitives such as Learning With Errors $(\mathrm{𝖫𝖶𝖤})$. It can be thought of as $\mathrm{𝖢𝖵𝖯}$ under a promise that the closest lattice vector to a target $𝒕$ is not too far away from the lattice $ℒ(B)$, relative to the length of the shortest non-zero vector. Alternatively, it can be thought of as a decoding problem over lattices, analogous to decoding noisy code words over finite fields. Quantitatively, a ${\mathrm{𝖡𝖣𝖣}}_{p,\alpha }$ instance promises that there is a closest lattice vector at a distance at most $\alpha {\lambda }_1^{(p)}(ℒ(B))$ from the lattice. (See Definition 2.8 for the formal definition.) Regev [65], in a seminal work, gave a reduction from worst case $\mathrm{𝖡𝖣𝖣}$ to (an average case problem) $\mathrm{𝖫𝖶𝖤}$, with polynomial (in the dimension of the lattice) $\alpha$. It is easy to see that there would be a unique solution to the problem if . If ${\alpha }_1>{\alpha }_2>0$, it is easy to see that ${\mathrm{𝖡𝖣𝖣}}_{p,{\alpha }_2}$ reduces to ${\mathrm{𝖡𝖣𝖣}}_{p,{\alpha }_1}$. Therefore, when showing hardness results for $\mathrm{𝖡𝖣𝖣}$, a lower $\alpha$ corresponds to a stronger result. $\mathrm{𝖭𝖯}$-hardness of $\mathrm{𝖡𝖣𝖣}$ for a constant $\alpha$ was first shown by [54], with $\alpha =\min \{2^{-1/2},2^{-1/p}\}$ for $p\ge 1$. This reduction however incurs a polynomial blowup in the rank of the lattice. Recently [26] studied the quantitative hardness of $\mathrm{𝖡𝖣𝖣}$ for the first time and show that for all $p>1$, there is no $2^{\mathrm{\Omega }(n)}$ time algorithm for ${\mathrm{𝖡𝖣𝖣}}_{p,\alpha }$ for all $\alpha$ greater than a certain constant that approaches $1/2$ as $p\to \mathrm{\infty }$, unless randomized $\mathrm{𝖤𝖳𝖧}$ is false. In a followup work [27], they show a similar result for improved values of $\alpha$, under the $\mathrm{𝖦𝖺𝗉𝖤𝖳𝖧}$ assumption. Quantitatively, they define a constant ${\alpha }_p^{‡}$ Equation 4 that depends on $p$, and show that for all $p>1$, for all $\alpha >{\alpha }_p^{‡}$ there is no sub-exponential time algorithm for ${\mathrm{𝖡𝖣𝖣}}_{p,\alpha }$ unless $\mathrm{𝖦𝖺𝗉𝖤𝖳𝖧}$ is false. To get this result, they show a decision-to-search reduction from ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }^{\prime }$ to the decision version of ${\mathrm{𝖡𝖣𝖣}}_{p,\alpha }$, where the goal is to decide if there is a vector at a distance at most $\alpha \cdot {\lambda }_1^{(p)}(ℒ(B))$. Here, ${\mathrm{𝖢𝖵𝖯}}^{\prime }$ is a special case of $\mathrm{𝖢𝖵𝖯}$ where in the $\mathrm{𝖸𝖤𝖲}$ case, there is a binary vector $𝒙\in {\{0,1\}}^n$ such that ${\Vert B𝒙-𝒕\Vert }_p\le r$, as compared to an arbitrary integer vector $𝒙$. For this they make use a ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }^{\prime }$ instance constructed from $\mathrm{𝟥}𝖲𝖠𝖳$ in [25]. Precisely, given a rank $n^{\prime }$ instance of ${\mathrm{𝖢𝖵𝖯}}^{\prime }$ $(B^{\prime },{𝒕}^{\prime },r^{\prime })$, for some scalar parameters $s,l>0$, they define a (generating set of a) lattice and target pair

where $(B^{†},{𝒕}^{†})$ is again a locally dense lattice gadget. Similar to what we saw in case of $\mathrm{𝖲𝖵𝖯}$ above, they are able to bound the number of lattice vectors close to the target $𝒕$ in the $\mathrm{𝖸𝖤𝖲}$ case by, say $G$, which is exponentially larger than the number of lattice vectors close to $𝒕$ in the $\mathrm{𝖭𝖮}$ case. However, there is a technical difficulty here. We also need the fact that if the output $\mathrm{𝖡𝖣𝖣}$ instance $(B,𝒕,r)$ is a $\mathrm{𝖸𝖤𝖲}$ instance, it satisfies the promise that the nearest lattice vector is at a distance at most $\alpha \cdot {\lambda }_1^{(p)}(ℒ(B))$. This corresponds to also bounding the number of very short vectors in the gadget in the $\mathrm{𝖸𝖤𝖲}$ case by some $A$. As before, they can then sparsify the lattice (Section 2.5), to get a sparse random sub-lattice such that if the input ${\mathrm{𝖢𝖵𝖯}}^{\prime }$ instance was a yes instance then there is a lattice vector at a distance at most $\alpha \cdot {\lambda }_1^{(p)}(ℒ(B))$ from the target, with high probability.

In this work we are able to achieve the same lower bound of ${\alpha }_p^{‡}$ from [27], but under $\mathrm{𝖤𝖳𝖧}$, by starting from a ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ instance constructed from gap $\mathrm{𝖬𝖠𝖷𝖫𝖨𝖭}$. To achieve this, we show a reduction from arbitrary ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ instances over lattices over integers, $ℒ\subseteq {\mathbb{Z}}^n$. In fact, we are able to get a simpler reduction, in that we don’t need to embed an integer lattice into our $\mathrm{𝖡𝖣𝖣}$ instance anymore. Given a ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ instance $(B^{\prime },{𝒕}^{\prime },r)$ we can define the following lattice

where $(B^{†},{𝒕}^{†})$ is again a locally dense lattice gadget. Using an analysis similar to that in case of ${\mathrm{𝖲𝖵𝖯}}_{p,\gamma }$ in Section 4, and a locally dense integer gadget from [27], we get a desired reduction from ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ to ${\mathrm{𝖡𝖣𝖣}}_{p,\alpha }$, for all $p\ge 1$ and for all $\alpha >{\alpha }_p^{‡}$. When we instantiate this reduction with the ${\mathrm{𝖢𝖵𝖯}}_{p,\gamma }$ instance from Section 3, we find that there is no sub-exponential time algorithm for ${\mathrm{𝖡𝖣𝖣}}_{p,\alpha }$, for all $p\ge 1$ and for all $\alpha >{\alpha }_p^{‡}$, unless the (randomized) $\mathrm{𝖤𝖳𝖧}$ is false.