## 2 Preliminaries
### Lattice  
**Definition 3**.: _A **lattice**\(\mathcal{L}\) is a discrete additive subgroup of \(\mathbb{R}^{d}\). Each lattice has a basis \(\mathbf{B}=[\mathbf{b}_{1},\mathbf{b}_{2},\ldots\mathbf{b}_{n}]\), where \(\mathbf{b}_{i}\in\mathbb{R}^{d}\) and_  
\[\mathcal{L}=\mathcal{L}(\mathbf{B})=\Big{\{}\sum_{i=1}^{n}x_{i}\mathbf{b}_{i}: x_{i}\in\mathbb{Z}\quad\text{for}\quad 1\leq i\leq n\Big{\}}\]  
For algorithmic purposes, we can assume that \(\mathcal{L}\subseteq\mathbb{Q}^{d}\). We call \(n\) the _rank_ of \(\mathcal{L}\) and \(d\) the _dimension_. If \(d=n\), the lattice is said to be full-rank. Though our results can be generalized to arbitrary lattices, in the rest of the paper, we only consider full-rank lattices.  
**Definition 4**.: _For any lattice basis \(\mathbf{B}\), we define the **fundamental parallelepiped** as_  
\[\mathcal{P}(\mathbf{B})=\{\mathbf{B}\mathbf{x}:\mathbf{x}\in[0,1)^{n}\}\]  
If \(\mathbf{y}\in\mathcal{P}(\mathbf{B})\), then \(\|\mathbf{y}\|_{p}\leq n\|\mathbf{B}\|_{p}\), as can be easily seen by triangle inequality. For any \(\mathbf{z}\in\mathbb{R}^{n}\), there exists a unique \(\mathbf{y}\in\mathcal{P}(\mathbf{B})\) such that \(\mathbf{z}-\mathbf{y}\in\mathcal{L}(\mathbf{B})\). This vector is denoted by \(\mathbf{y}\equiv\mathbf{z}\mod\mathbf{B}\) and it can be computed in polynomial time given \(\mathbf{B}\) and \(\mathbf{z}\).  
**Definition 5**.: _For \(i\in[n]\), the **successive minimum** is defined as the smallest real number \(r\) such that \(\mathcal{L}\) contains \(i\) linearly independent vectors with a length of at most \(r\):_  
\[\lambda_{i}^{(p)}(\mathcal{L})=\inf\{r:\dim(span(\mathcal{L}\cap B_{n}^{(p)}(r )))\geq i\}\]  
Thus, the _first successive minimum_ of a lattice is the length of the shortest non-zero vector in the lattice:  
\[\lambda_{1}^{(p)}(\mathcal{L})=\min\{\|\mathbf{v}\|_{p}:\mathbf{v}\in\mathcal{ L}\setminus\{\mathbf{0}\}\}\]We consider the following lattice problems. In all the problems defined below, \(c\geq 1\) is some arbitrary approximation factor (usually specified as subscript), which can be a constant or a function of any parameter of the lattice (usually rank). For exact versions of the problems (i.e., \(c=1\)), we drop the subscript.  
**Definition 6** (**Shortest Vector Problem (\(\mathsf{SVP}_{c}^{(p)}\))**).: _Given a lattice \(\mathcal{L}\), find a vector \(\mathbf{v}\in\mathcal{L}\setminus\{\mathbf{0}\}\) such that \(\|\mathbf{v}\|_{p}\leq c\|\mathbf{u}\|_{p}\) for any other \(\mathbf{u}\in\mathcal{L}\setminus\{\mathbf{0}\}\)._  
**Definition 7** (**Closest Vector Problem (\(\mathsf{CVP}_{c}^{(p)}\))**).: _Given a lattice \(\mathcal{L}\) with rank \(n\) and a target vector \(\mathbf{t}\in\mathbb{R}^{n}\), find \(\mathbf{v}\in\mathcal{L}\) such that \(\|\mathbf{v}-\mathbf{t}\|_{p}\leq c\|\mathbf{w}-\mathbf{t}\|_{p}\) for all other \(\mathbf{w}\in\mathcal{L}\)._  
**Lemma 1** ([49]).: _The LLL algorithm [1] can be used to solve \(\mathsf{SVP}_{2^{n}}^{(p)}\) in polynomial time._  
The following result shows that in order to solve \(\mathsf{SVP}_{1+\epsilon}^{(p)}\), it is sufficient to consider the case when \(2\leq\lambda_{1}^{(p)}(\mathcal{L})<3\). This is done by appropriately scaling the lattice.  
**Lemma 2** (**Lemma 4.1 in [47]**).: _For all \(\ell_{p}\) norms, if there is an algorithm \(A\) that for all lattices \(\mathcal{L}\) with \(2\leq\lambda_{1}^{(p)}(\mathcal{L})<3\) solves \(\mathsf{SVP}_{1+\epsilon}^{(p)}\) in time \(T=T(n,b,\epsilon)\), then there is an algorithm \(A^{\prime}\) that solves \(\mathsf{SVP}_{1+\epsilon}^{(p)}\) for all lattices in time \(O(nT+n^{4}b)\)._  
Thus, henceforth, we assume \(2\leq\lambda_{1}^{(p)}(\mathcal{L})<3\).