## 3 A Faster Provable Sieving Algorithm in \(\ell_{p}\) Norm
### Linear Sieve
\begin{cases}\mathbf{e}+\mathbf{u}&\text{if }\mathbf{e}\in D _{1}\\ \mathbf{e}-\mathbf{u}&\text{if }\mathbf{e}\in D_{2}\\ \mathbf{e}&\text{else}\end{cases} \]  
For the analysis of the algorithm, we assume that for each perturbation vector \(\mathbf{e}\) chosen by our algorithm, we replace \(\mathbf{e}\) by \(\sigma(\mathbf{e})\) with probability \(1/2\) and that it remains unchanged with probability \(1/2\). We call this procedure _tossing_ the vector \(\mathbf{e}\). This does not change the distribution of the perturbation vectors \(\{\mathbf{e}\}\). Further, we assume that this replacement of the perturbation vectors happens at the step where this has any effect on the algorithm for the first time. In particular, at step 17 in Algorithm 2, after we have identified a center pair \((\mathbf{e}_{c},\mathbf{c})\), we apply \(\sigma\) on \(\mathbf{e}_{c}\) with probability \(1/2\). Then, at the beginning of step 12 in Algorithm 1, we apply \(\sigma\) to \(\mathbf{e}\) for all pairs \((\mathbf{e},\mathbf{y})\in S\). The distribution of \(\mathbf{y}\) remains unchanged by this procedure because \(\mathbf{y}\equiv\mathbf{e}\equiv\sigma(\mathbf{e})\mod\mathcal{P}(\mathbf{B})\) and \(\mathbf{y}-\mathbf{e}\in\mathcal{L}\). A somewhat more detailed explanation of this can be found in the following result of [47]. Lemma 8 (Theorem 4.5 in [47] (re-stated)): _The modification outlined above does not change the output distribution of the actual procedure._  
Note that since this is just a conceptual modification intended for ease in analysis, we should not be concerned with the actual running time of this modified procedure. Even the fact that we need a shortest vector to begin the mapping \(\sigma\) does not matter. The following lemma will help us to estimate the number of vector pairs to sample at the beginning of the algorithm. Lemma 9 (Lemma 4.7 in [47]): _Let \(N\in\mathbb{N}\) and \(q\) denote the probability that a random point in \(B_{n}^{(p)}(\xi\lambda)\) is contained in \(D_{1}\cup D_{2}\). If \(N\) points \(\mathbf{x}_{1},\ldots\mathbf{x}_{N}\) are chosen uniformly at random in \(B_{n}^{(p)}(\xi\lambda)\), then with a probability larger than \(1-\frac{4}{qN}\), there are at least \(\frac{qN}{2}\) points \(\mathbf{x}_{i}\in\{\mathbf{x}_{1},\ldots\mathbf{x}_{N}\}\) with the property \(\mathbf{x}_{i}\in D_{1}\cup D_{2}\)._  
From Lemma 3, we have  
\[q \geq 2^{-c_{s}n}\qquad\text{where }c_{s}=-\log\left(0.5-\frac{1}{4_{ \mathbf{c}}^{s}}\right)\]  
Thus, with a probability of at least \(1-\frac{4}{qN}\), we have at least \(2^{-c_{s}n}N\) pairs \((\mathbf{e}_{i},\mathbf{y}_{i})\) before the sieving iterations such that \(\mathbf{e}_{i}\in D_{1}\cup D_{2}\). Lemma 10: _If \(N\geq\frac{2}{q}(k|\mathcal{C}|+2^{c_{0}n}+1)\), then with a probability of at least \(1/2\), Algorithm 1 outputs a shortest non-zero vector in \(\mathcal{L}\) with respect to \(\ell_{p}\) norm for \(1\leq p\leq\infty\)._  
Proof: Of the \(N\) vector pairs \((\mathbf{e},\mathbf{y})\) sampled in steps 2-6 of Algorithm 1, we consider those such that \(\mathbf{e}\in(D_{1}\cup D_{2})\). We have already seen there are at least \(\frac{qN}{2}\) such pairs with a probability of at least \(1-\frac{4}{qN}\). We remove \(|\mathcal{C}|\) vector pairs in each of the \(k\) sieve iterations. Thus, at step 12 of Algorithm 1, we have \(N^{\prime}\geq 2^{c_{s}n}+1\) pairs \((\mathbf{e},\mathbf{y})\) to process. By Lemma 7, each of them is contained within a ball of radius \(R^{\prime}\) which can have at most \(2^{c_{s}n}\) lattice vectors. Thus, there exists at least one lattice vector \(\mathbf{w}\) for which the perturbation is in \(D_{1}\cup D_{2}\), and it appears twice in \(S\) at the beginning of step 12. With a probability of \(1/2\), it remains \(\mathbf{w}\), or with the same probability, it becomes either \(\mathbf{w}+\mathbf{u}\) or \(\mathbf{w}-\mathbf{u}\). Thus, after taking pair-wise difference at step 12 with a probability of at least \(1/2\), we find the shortest vector. **Theorem 2**: _Let \(\gamma\in(0,1)\), and let \(\xi>1/2\).