betaFeedback

WorksComputer Science

ℓ∞\ell_{\infty} norm SVP in O~(3n)\widetilde{O}(3^n)

Abstract

We give a classical randomized algorithm for the Shortest Vector Problem in the infinity norm in O~(3n)\widetilde O(3^n) time and space, improving the previous bound of 22.443n+o(n)2^{2.443n+o(n)}. We adapt Gaussian difference dynamics to the infinity norm by repeatedly taking differences of vectors from two lists, producing lists in successively smaller cubes. The key is to restrict the midpoint of each pair to a fixed inner cube, so that every allowed difference has the same region of possible midpoints. Using random lattice translates, this rule preserves equal expected counts at each point of the smaller cube. We analyze the dependencies created by repeated differencing through the counting moments of Gaussian difference dynamics, together with a weighted packing bound for cubes. Finally, two searches based on coordinate comparisons generate the intermediate lists and recover a shortest lattice vector within the claimed time bound.

Introduction

Let L=BZn⊂RnL = B\mathbb{Z}^n \subset\mathbb{R}^n be a full-rank lattice. The Shortest Vector Problem in the infinity norm asks for a nonzero vector v∈Lv \in L satisfying

∥v∥∞=λ1(∞)(L):=min⁡x∈L∖{0}max⁡1≤i≤n∣xi∣.\lVert v\rVert_\infty= \lambda_1^{(\infty)}(L) := \min_{x\in L\setminus\{0\}} \max_{1\le i\le n} |x_i|.

Equivalently, it asks for the smallest axis-aligned cube centered at the origin that contains a nonzero lattice point. The infinity norm naturally describes coordinatewise error bounds in cryptanalytic lattice problems, including the Hidden Number Problem [7] and attacks on DSA and ECDSA with partially known nonces [HGS01, NS03].

Provable sieving algorithms for this norm exploit the product geometry of the cube. Aggarwal and Mukhopadhyay [2] specialized the AKS framework to this geometry and obtained a randomized algorithm with 22.8200n+o(n)2^{2.8200n+o(n)} time and space. Mukhopadhyay [Muk21] subsequently improved both bounds to 22.4430n+o(n)2^{2.4430n+o(n)} through a finer subdivision of the cube.

We give a classical randomized algorithm for exact ℓ∞\ell_\infty-SVP in O~(3n)\widetilde{O}(3^n) time and space, reducing the exponent from 2.44302.4430 to log⁡23≈1.5850\log_2 3 \approx1.5850. Our algorithm constructs lists in successively smaller cubes by repeatedly taking differences, following the counting moment framework of Gaussian difference dynamics [GHH26]. The geometry of the cube guides both the rule for generating these differences and the searches used to find them efficiently. Here and throughout the paper, O~(cn)\widetilde{O}(c^n) means cnpoly⁡(n,size⁡(B))c^n\operatorname{poly}(n,\operatorname{size}(B)).

Our results

Theorem 1.1 (Main theorem). There is a classical randomized algorithm that, given a nonsingular rational basis of a full-rank lattice L⊂RnL \subset\mathbb{R}^{n}, returns a nonzero vector of LL and, with probability at least 2/32/3, returns a vector of norm λ1(∞)(L)\lambda_{1}^{(\infty)}(L). Every execution uses

T=O~(3n)andS=O~(3n).T = \widetilde{O}(3^{n}) \qquad\text{and} \qquad S = \widetilde{O}(3^{n}).

The success probability can be increased to 1−2−Ω(nlog⁡n)1 - 2^{-\Omega(n \log n)} by independent repetition without changing either bound.

Application to Subset Balancing. Combining Theorem 1.1 with the reduction of Gao, Feng, Hu, and Pan [GFHP26, Theorem 3.3] to one (n+1)(n+1)-dimensional ℓ∞\ell_{\infty}-SVP instance gives the following consequence.

Corollary 1.2. Given x∈Znx \in\mathbb{Z}^{n} and an integer d≥1d \ge1, there is a randomized algorithm that, with probability at least 2/32/3, finds a vector c∈{−d,…,d}n∖{0}c \in\{-d,\ldots,d\}^{n} \setminus\{0\} satisfying c⋅x=0c \cdot x = 0, or correctly reports that no such vector exists. It uses O~(3n)\widetilde{O}(3^{n}) time and space, suppressing polynomial factors in the binary input length.

For every d≥5d \ge5, this is exponentially faster than the standard meet-in-the-middle bound O~((2d+1)n/2)\widetilde{O}((2d+1)^{n/2}), improving the threshold d≥15d \ge15 obtained in [GFHP26].

Related work

Ajtai, Kumar, and Sivakumar introduced randomized sieving for lattice problems [4]. Algorithms in general norms were subsequently developed through sieving and through enumeration. Dadush, Peikert, and Vempala obtained single-exponential algorithms for SVP in arbitrary norms by using M-ellipsoid coverings [8].

The infinity norm bounds discussed above use linear sieves adapted to the cube. Mukhopadhyay’s sieve [Muk21] also applies to every ℓp\ell_p norm, with a general SVP bound of 22.7510n+o(n)2^{2.7510n+o(n)} time and space, and gives approximation algorithms for SVP and CVP in these norms.

Random superlattices and quotient labels appear in the Euclidean algorithms of Gao, Feng, and Hu [9 GFH26b]. A superlattice contains every target vector of the input lattice, and equal labels certify that a difference lies in the input lattice.

Gaussian difference dynamics [GHH26] controls the lists produced by repeated differences through a recursion for their first two counting moments. We specialize its analysis to lists with the same expected count at every lattice point in the current cube, retaining each eligible pair independently even when pairs share an input entry. The midpoint geometry, weighted cube estimates, and coordinate searches developed here make this construction possible within the O~(3n)\widetilde{O}(3^{n}) bound.

Organization. § 2 explains the construction and derives the main cost balance. § 3 fixes notation and the standard lattice tools. § 4 and § 5 control cube counts on a random superlattice. § 6 builds the lists and proves their counting bounds. § 7 and § 8 give the two pair searches. § 9 assembles the algorithm and proves Theorem 1.1. Appendix § 10 proves the basis preprocessing lemma, and Appendix § 11 gives the finite arithmetic details.

The author used generative AI to assist with algorithm design, mathematical analysis, and manuscript drafting, as described in the AI methodology statement at the end of the paper.

Technique overview

Fix a shortest vector v∈L∖{0}v \in L \setminus\{0\} for the analysis, and write λ=∥v∥∞\lambda= \lVert v\rVert_{\infty}. There are two tasks: make vv appear as a difference between two lists, and find that difference within the claimed time. We first explain the construction as though λ\lambda were known. A polynomial-size scale grid removes this assumption in the algorithm.

Preserving uniform counts by midpoint restriction

We seek a difference rule that preserves equal expected counts across each successive cube. Write

QR=[−R,R)n,BR=[−R/2,R/2)n.Q_R = [-R,R)^n,\qquad B_R = [-R/2,R/2)^n.

The two boxes have different roles. QRQ_R contains an input list, while BRB_R is the allowed midpoint region. Choose a fixed γ<1\gamma< 1. From two lists in QRQ_R, keep pairs satisfying

z=x−y∈QγR,M=(x+y)/2∈BR.(1)z = x-y \in Q_{\gamma R},\qquad M = (x+y)/2 \in B_R. \tag*{(1)}

For every allowed zz, the complete set of possible midpoints is exactly BRB_R. Conversely, M∈BRM \in B_R and z∈QγRz \in Q_{\gamma R} imply M±z/2∈QRM \pm z/2 \in Q_R. The volume of the midpoint set is therefore RnR^n, independently of zz. This is the reason for the second condition in (1). Restricting only x−yx-y would give a midpoint region that shrinks as a coordinate of zz approaches the boundary. The additional midpoint condition removes that variation. In the continuous model, the output has constant density on QγRQ_{\gamma R}.

For lattice points, the number of admissible midpoints also depends on the lattice translate. We build the lists along a binary tree, choosing a new random translate at each node and generating the two child lists with independent randomness conditional on their translates. Averaging the translate makes the expected output count equal at every lattice point of the smaller cube. To control both the variation in midpoint counts and the dependence caused by pairs that share an input entry, we track the first two counting moments as in [GHH26]. This requires a bound on the midpoint count’s variance, which we obtain by passing to a random superlattice.

Controlling midpoint variance with a random superlattice

A cube near the shortest vector scale can contain very different numbers of points in different translates of the input lattice. For a lattice Λ\Lambda and a uniform translate t+Λt+\Lambda, let

JRΛ(t)=#((t+Λ)∩BR).J_R^\Lambda(t) = \#((t+\Lambda)\cap B_R).

We measure this variation by

ΘR(Λ∗)=Var⁡(JRΛ)E[JRΛ]2,E[JRΛ]=Rndet⁡Λ.(2)\Theta_R(\Lambda^*) = \frac{\operatorname{Var}(J_R^\Lambda)}{\mathbb{E}[J_R^\Lambda]^2},\qquad\mathbb{E}[J_R^\Lambda] = \frac{R^n}{\det\Lambda}. \tag*{(2)}

We work in a random superlattice Γ⊃L\Gamma\supset L, of determinant DD, chosen so that these relative variances are small at all widths used by the construction.

The main geometric estimate is

1+ΘR(L∗)≤Cndet⁡Lλn,C=98,R≥89λ.(3)1+\Theta_R(L^*) \le C^n\frac{\det L}{\lambda^n},\qquad C=\frac{9}{8},\qquad R\ge\frac{8}{9}\lambda. \tag*{(3)}

Its proof is a weighted packing argument for cubes. The constant can already be seen in one dimension. An interval of length 4/34/3, translated uniformly modulo Z\mathbb{Z}, contains one point with probability 2/32/3 and two points with probability 1/31/3. Its second moment divided by the square of its mean is 9/89/8. Products of these intervals give (9/8)n(9/8)^n.

Passing to a random superlattice of prime index pp reduces the expected relative variance to at most ΘR(L∗)/p\Theta_R(L^*)/p, plus an error term controlled in § 5. We choose

p≳Cndet⁡Lλnpoly⁡(n),D≳λnC−npoly⁡(n).p \gtrsim C^n \frac{\det L}{\lambda^n}\operatorname{poly}(n), \qquad D \gtrsim\frac{\lambda^n C^{-n}}{\operatorname{poly}(n)}.

This makes the relative variance small at all required widths with high probability. The density also determines the list size: for lists of a fixed average size, decreasing DD decreases the expected number of representations of the target vector, as the following calculation shows.

Choosing the list size from target representations

Suppose a final list has expected count AA at each point of a common translate z+Γz+\Gamma inside QλQ_\lambda. If its average size is NN, then

A=ND(2λ)n.A=\frac{ND}{(2\lambda)^n}.

Every midpoint in BλB_\lambda represents vv through the endpoints M+v/2M+v/2 and M−v/2M-v/2. The number of available midpoints is about λn/D\lambda^n/D. Thus the expected number of representations in the two lists is

A2λnD=N2D4nλn≳N24nCnpoly⁡(n).(4)A^2\frac{\lambda^n}{D}=\frac{N^2D}{4^n\lambda^n}\gtrsim\frac{N^2}{4^nC^n\operatorname{poly}(n)}. \tag*{(4)}

This suggests

N=(2C)npoly⁡(n)=(3/2)npoly⁡(n).N=(2\sqrt{C})^n\operatorname{poly}(n)=(3/\sqrt{2})^n\operatorname{poly}(n).

A suitable polynomial factor makes the target count large. To turn this expectation into a success probability, we also control pairs of distinct entries within each list. Repeated vector values are kept as separate entries, so that every retained pair contributes one new entry to the counting recursion. At every round, the reference count per point is AR=ND/(2R)nA_R=ND/(2R)^n. We thin each eligible pair with probability

q=(2/γ)nN.q=\frac{(2/\gamma)^n}{N}.

Then qAR2(Rn/D)=AγRqA_R^2(R^n/D)=A_{\gamma R}, so the same reference list size NN is maintained throughout the tree. We choose a fixed 8/9<γ<1\sqrt{8/9}<\gamma<1, which ensures q≤1q\le1 while shortening the radius by a constant factor.

The construction starts in a cube whose radius is polynomially larger than λ\lambda, where we can sample the initial lists directly with the required counting moments. The tree therefore has depth O(log⁡n)O(\log n) and polynomially many nodes, so its leading exponential cost is determined by the list size and the pair searches at each node.

Finding pairs with coordinatewise tests

Gaussian difference dynamics [GHH26] uses BDGL product codes [6] to find pairs with short Euclidean differences. In the infinity norm, the difference and midpoint conditions can be tested coordinate by coordinate. We exploit this structure directly: three classes per coordinate generate candidates for each recursive merge, while a binary condition and quotient labels recover a shortest vector from the two root lists.

For an internal pair, (1) implies

∣xi∣+∣yi∣=max⁡{∣xi−yi∣,∣xi+yi∣}≤R.(5)|x_i|+|y_i|=\max\{|x_i-y_i|,|x_i+y_i|\}\le R. \tag*{(5)}

Divide each absolute coordinate into three classes, according to the intervals [0,R/3)[0,R/3), (R/3,2R/3](R/3,2R/3], and (2R/3,R](2R/3,R]. If the class numbers are bi(x),bi(y)∈{0,1,2}b_i(x),b_i(y)\in\{0,1,2\}, every eligible pair satisfies

bi(x)+bi(y)≤2.b_i(x)+b_i(y)\le2.

There are six compatible class pairs out of nine in each coordinate. A table indexed by {0,1,2}n\{0,1,2\}^n reports the corresponding pairs without visiting empty combinations. The candidate count has scale

N2(2/3)n=3npoly⁡(n).N^2(2/3)^n=3^n\operatorname{poly}(n).

These tables also account for the O~(3n)\widetilde{O}(3^n) space bound, which exceeds the space needed to store the lists.

The final search uses a different rule. It asks that in every coordinate at least one endpoint lie in [−λ/2,λ/2)[-\lambda/2,\lambda/2). This keeps every representation of a shortest vector whose midpoint lies in BλB_\lambda: since ∣vi∣≤λ|v_i|\le\lambda, at least one of Mi+vi/2M_i+v_i/2 and Mi−vi/2M_i-v_i/2 lies in that inner interval. Each point has a binary class vector and a label modulo LL, so equal labels recognize differences in LL.

To bound the number of reports, we express binary compatibility by inclusion and exclusion as a weighted count involving the inner cube BλB_\lambda. Every translate of this half-open cube contains at most one point of LL, so the lattice sum is bounded by the total weight, (3λ)n(3\lambda)^n. Thus, if PP counts pairs satisfying both the binary condition and the equal-label condition, then

E[P]≤A2(3λ)nD=3npoly⁡(n).\mathbb{E}[P]\le\frac{A^2(3\lambda)^n}{D}=3^n\operatorname{poly}(n).

To find these pairs, we check small label groups directly and use a binary prefix table for large groups. Splitting at group size 2n/22^{n/2} gives the deterministic bound

poly⁡(n)(M2n/2+P),\operatorname{poly}(n)(M2^{n/2}+P),

where MM is the total input size. Since MM is at most (3/2)npoly⁡(n)(3/\sqrt{2})^n\operatorname{poly}(n), this cost is also 3npoly⁡(n)3^n\operatorname{poly}(n).

Part of the algorithmQuantity before substitutionExponential factor
List generationNN(3/2)n(3/\sqrt{2})^n
Internal candidate pairsN2(2/3)nN^2(2/3)^n3n3^n
Final label-group searchesN2n/2N2^{n/2}3n3^n
Final pair reportsA2(3λ)n/DA^2(3\lambda)^n/D3n3^n

Table 1. The cost balance. Polynomial factors are omitted in this overview.

Preliminaries

We use log⁡\log for the natural logarithm and log⁡2\log_2 for the binary logarithm. For a real number tt, write (t)+=max⁡{t,0}(t)_+=\max\{t,0\}. All lists are finite sequences of entries with distinct identifiers. Different entries may store the same vector.

Lattices and basic tools

For a nonsingular rational matrix BB, let

L=BZn,det⁡L=∣det⁡B∣,L∗=B−TZn.L=B\mathbb{Z}^n,\qquad\det L=|\det B|,\qquad L^*=B^{-T}\mathbb{Z}^n.

We write λi(p)(L)\lambda_i^{(p)}(L) for the iith successive minimum in the ℓp\ell_p norm. Unless a different lattice is specified, λ\lambda denotes λ1(∞)(L)\lambda_1^{(\infty)}(L). The inequalities

∥x∥∞≤∥x∥2≤n∥x∥∞\lVert x\rVert_\infty\le\lVert x\rVert_2 \le\sqrt{n}\lVert x\rVert_\infty

will be used for preprocessing only.

Minkowski’s second theorem, applied to the cube, gives [Henk02]

∏i=1nλi(∞)(L)≤det⁡L,λn(∞)(L)≤det⁡Lλn−1.(6)\prod_{i=1}^{n}\lambda_i^{(\infty)}(L) \le\det L,\qquad\lambda_n^{(\infty)}(L) \le\frac{\det L}{\lambda^{n-1}}. \tag*{(6)}

In particular, det⁡L≥λn\det L \ge\lambda^n. We also use the Euclidean transference bound [5]

λn(2)(Λ)λ1(2)(Λ∗)≤n.(7)\lambda_n^{(2)}(\Lambda)\lambda_1^{(2)}(\Lambda^*) \le n. \tag*{(7)}

The following basis lemma places the starting cube within a polynomial factor of the final scale. We use the general Euclidean preprocessing result of [GHH26, Proposition 3.2 and Corollary 3.3].

Lemma 3.1. Put Ared(n)=2(n+1)A_{\mathrm{red}}(n)=2(n+1). From a rational basis of a rank-nn lattice Λ\Lambda, one can compute a size-reduced basis (b1,…,bn)(b_1,\ldots,b_n) such that

max⁡i∥bi∗∥2≤Ared(n)λn(2)(Λ).\max_i \lVert b_i^*\rVert_2 \le A_{\mathrm{red}}(n)\lambda_n^{(2)}(\Lambda).

The time and workspace are 2n+o(n)poly⁡(size⁡(B))2^{n+o(n)}\operatorname{poly}(\operatorname{size}(B)). All projected bases, lifted vectors, and integer coordinates have polynomial encoding length.

Proof. This is [GHH26, Corollary 3.3]. The proof from [1 MV13] is reproduced in Appendix § 10.

Here bi∗b_i^* are the Gram–Schmidt vectors. For the computed basis matrix Bred=(b1,…,bn)B_{\mathrm{red}}=(b_1,\ldots,b_n), size reduction gives

sup⁡x∈Bred[0,1)n∥x∥∞≤∑i∥bi∥2≤n2Ared(n)λn(2)(Λ).(8)\sup_{x\in B_{\mathrm{red}}[0,1)^n}\lVert x\rVert_\infty\le\sum_i\lVert b_i\rVert_2 \le n^2 A_{\mathrm{red}}(n)\lambda_n^{(2)}(\Lambda). \tag*{(8)}

The coarse factor n2n^2 is convenient and sufficient.

Boxes and finite shifts

We use the half-open boxes

QR=[−R,R)n,BR=[−R/2,R/2)n.Q_R=[-R,R)^n,\qquad B_R=[-R/2,R/2)^n.

Thus QRQ_R has radius RR and BRB_R has side length RR. Half-open endpoints assign every grid point to exactly one interval when we partition a coordinate.

All random shifts are chosen from a finite quotient. For a fixed rational superlattice Γ\Gamma, choose a rational δ>0\delta>0 such that

Γ⊆G:=δZn.(9)\Gamma\subseteq G:=\delta\mathbb{Z}^n. \tag*{(9)}

Then G/ΓG/\Gamma has D/δnD/\delta^n elements, where D=det⁡ΓD=\det\Gamma. A uniform shift a∈G/Γa\in G/\Gamma satisfies

P[x∈a+Γ]=δnD(x∈G).(10)\mathbb{P}[x\in a+\Gamma]=\frac{\delta^n}{D}\qquad(x\in G). \tag*{(10)}

A basis in Hermite normal form permits uniform quotient sampling in polynomial time. We describe the exact arithmetic in Appendix § 11.

Counts in random lists

For a list X\mathcal{X}, let NxN_x be the number of entries equal to xx. Define

mX(x)=E[Nx],SX(x,x′)=E[NxNx′−1x=x′Nx].(11)m_{\mathcal{X}}(x)=\mathbb{E}[N_x],\qquad S_{\mathcal{X}}(x,x')=\mathbb{E}[N_xN_{x'}-\mathbf{1}_{x=x'}N_x]. \tag*{(11)}

The second quantity counts ordered pairs of distinct entries. In particular, SX(x,x)=E[Nx(Nx−1)]S_{\mathcal{X}}(x,x)=\mathbb{E}[N_x(N_x-1)].

At a node with radius RR and prescribed coset c+Γc+\Gamma, the reference is

AR=ND(2R)n,mX(x)=AR,SX(x,x′)≤eεAR2(x,x′∈(c+Γ)∩QR).(12)A_R=\frac{N D}{(2R)^n},\qquad m_{\mathcal{X}}(x)=A_R,\qquad S_{\mathcal{X}}(x,x')\leq e^\varepsilon A_R^2\quad(x,x'\in(c+\Gamma)\cap Q_R). \tag*{(12)}

The moments in (12) average the node’s private randomness and keep its coset fixed. The first equality gives the expected supply at each point. The second inequality limits clustering. For example, NN independent draws and NN copies of one draw have the same first moment, but very different second moments.

When a node chooses the two child cosets, we first fix those cosets and multiply the moments of the independent child subtrees. We then average the common choice of child cosets. This order will be used in both the list analysis and the work estimates.

Weighted cube counts

The number of points in a translated cube is the geometric quantity needed by the list construction. We first express its variance as a nonnegative Fourier sum. We then bound that sum by a packing argument in the original lattice.

The variance of a translated box

For a full-rank lattice Λ\Lambda and R>0R>0, define

ΘR(Λ∗)=∑ξ∈Λ∗∖{0}∏i=1nsinc⁡2(Rξi).(13)\Theta_R(\Lambda^*)=\sum_{\xi\in\Lambda^*\setminus\{0\}}\prod_{i=1}^{n}\operatorname{sinc}^2(R\xi_i). \tag*{(13)}

Here sinc⁡(t)=sin⁡(πt)/(πt)\operatorname{sinc}(t)=\sin(\pi t)/(\pi t), with sinc⁡(0)=1\operatorname{sinc}(0)=1. By the following lemma, ΘR(Λ∗)\Theta_R(\Lambda^*) is the relative variance of the translated box count used in § 2.

Lemma 4.1. Let tt be uniform modulo Λ\Lambda, and put

JR(t)=#((t+Λ)∩BR),μR=Rn/det⁡Λ.J_R(t)=\#((t+\Lambda)\cap B_R),\qquad\mu_R=R^n/\det\Lambda.

Then

E[JR]=μR,Var⁡JRμR2=ΘR(Λ∗),(14)\mathbb{E}[J_R]=\mu_R,\qquad\frac{\operatorname{Var}J_R}{\mu_R^2}=\Theta_R(\Lambda^*), \tag*{(14)}

and

1+ΘR(Λ∗)=det⁡ΛR2n∑w∈Λ∏i=1n(R−∣wi∣)+.(15)1+\Theta_R(\Lambda^*)=\frac{\det\Lambda}{R^{2n}}\sum_{w\in\Lambda}\prod_{i=1}^{n}(R-|w_i|)_+. \tag*{(15)}

Proof. The periodization of 1BR\mathbf{1}_{B_R} is bounded on a fundamental domain. It is therefore square integrable. Its mean is Rn/det⁡ΛR^n/\det\Lambda, and its Fourier coefficient at ξ∈Λ∗\xi\in\Lambda^* has absolute value

Rndet⁡Λ∏i∣sinc⁡(Rξi)∣.\frac{R^n}{\det\Lambda}\prod_i\left|\operatorname{sinc}(R\xi_i)\right|.

Parseval’s identity proves (14), including convergence of the nonnegative series. Alternatively, expand JR2J_R^2 before integrating over a fundamental domain. The two lattice points differ by some w∈Λw \in\Lambda, and the intersection of the corresponding boxes has volume ∏i(R−∣wi∣)+\prod_i(R-|w_i|)_+. Thus

E[JR2]=1det⁡Λ∑w∈Λ∏i(R−∣wi∣)+.\mathbb{E}[J_R^2]=\frac{1}{\det\Lambda}\sum_{w\in\Lambda}\prod_i(R-|w_i|)_+.

Combining the two expressions for the second moment gives (15).

From a one-dimensional weight to a cube bound

The coordinate projections of an ℓ∞\ell_\infty-separated set need not themselves be separated. To apply a one-dimensional weighted bound, we first construct covers by weighted unit intervals and then multiply these covers across coordinates. Every resulting unit cube contains at most one point of the separated set, which allows the one-dimensional estimate to give the required cube bound.

Lemma 4.2. Let x1<⋯<xmx_1<\cdots<x_m be real numbers with nonnegative weights w1,…,wmw_1,\ldots,w_m. There are nonnegative weights on the intervals [xj,xj+1)[x_j,x_j+1) that cover each point xix_i to total weight at least wiw_i. Their total weight equals the maximum weight of a subset whose points are pairwise at distance at least one.

Proof. Let p(i)p(i) be the last index with xp(i)≤xi−1x_{p(i)}\le x_i-1, or zero if no such index exists. Define

F0=0,Fi=max⁡{Fi−1,wi+Fp(i)}.F_0=0,\qquad F_i=\max\{F_{i-1},w_i+F_{p(i)}\}.

The first option omits xix_i. The second selects xix_i and uses an optimal subset among the first p(i)p(i) points. Hence FmF_m is the maximum weight of a separated subset.

Give [xj,xj+1)[x_j,x_j+1) weight dj=Fj−Fj−1≥0d_j=F_j-F_{j-1}\ge0. The intervals containing xix_i are precisely those with p(i)<j≤ip(i)<j\le i, so their total weight is

∑j=p(i)+1idj=Fi−Fp(i)≥wi.\sum_{j=p(i)+1}^{i}d_j=F_i-F_{p(i)}\ge w_i.

The total interval weight is ∑jdj=Fm\sum_jd_j=F_m.

For r>0r>0, put

fr(x)=(r−∣x∣)+,A(r)=∑k∈Zfr(k).(16)f_r(x)=(r-|x|)_+,\qquad A(r)=\sum_{k\in\mathbb{Z}}f_r(k). \tag*{(16)}

Lemma 4.3. For every finite set P⊂RP\subset\mathbb{R} whose distinct points are at distance at least one,

∑x∈Pfr(x)≤A(r).\sum_{x\in P}f_r(x)\le A(r).

Writing r=m+ur=m+u with m=⌊r⌋m=\lfloor r\rfloor and 0≤u<10\le u<1, one has

A(r)=r2+u(1−u).A(r)=r^2+u(1-u).

Proof. Discard points with zero weight. If kk points remain, order them increasingly. Pair the smallest with the largest, the second smallest with the second largest, and so on. Their separation gives

∑x∈P∣x∣≥⌊k24⌋.\sum_{x\in P}|x|\ge\left\lfloor\frac{k^2}{4}\right\rfloor.

Consequently their total weight is at most kr−⌊k2/4⌋kr-\lfloor k^2/4\rfloor. For even kk, this expression is the average of its values at the two neighboring odd integers. For k=2j+1k=2j+1, it equals (2j+1)r−j(j+1)(2j+1)r-j(j+1). Maximizing over j≥0j\ge0 gives A(r)A(r). Summing the terms at 0,±1,…,±m0,\pm1,\ldots,\pm m gives the displayed formula.

Lemma 4.4 (Weighted packing for cubes). If P⊂RnP \subset\mathbb{R}^{n} is ℓ∞\ell_{\infty}-separated by at least one, then

∑x∈P∏i=1nfr(xi)≤A(r)n.(17)\sum_{x \in P}\prod_{i=1}^{n} f_r(x_i) \le A(r)^n. \tag*{(17)}

In particular, with λ=λ1(∞)(L)\lambda= \lambda_1^{(\infty)}(L),

1+ΘR(L∗)≤(9/8)ndet⁡Lλn(18)1+\Theta_R(L^*) \le(9/8)^n\frac{\det L}{\lambda^n} \tag*{(18)}

for every R≥8λ/9R \ge8\lambda/9.

Proof. Only finitely many points contribute to the sum. Apply Lemma 4.2 to the distinct values in each coordinate projection, with weight frf_r. The cover’s total weight equals that of the heaviest separated subset of the projection, which is at most A(r)A(r) by Lemma 4.3.

Multiply the coordinate covers. For each point, the product of its covering weights dominates ∏ifr(xi)\prod_i f_r(x_i). Sum first over points and then over product boxes. Every half-open box has side length one and contains at most one point of PP, so it is counted at most once. The total product weight is at most A(r)nA(r)^n, proving (17).

To prove (18), set r=R/λr=R/\lambda and apply (17) to L/λL/\lambda. Equation (15) gives

1+ΘR(L∗)≤det⁡Lλn(A(r)r2)n.1+\Theta_R(L^*) \le\frac{\det L}{\lambda^n}\left(\frac{A(r)}{r^2}\right)^n.

For 8/9≤r≤18/9 \le r \le1, the ratio is 1/r≤9/81/r \le9/8. For r=m+u≥1r=m+u \ge1, it is at most

1+u(1−u)(1+u)2≤98,1+\frac{u(1-u)}{(1+u)^2}\le\frac{9}{8},

since 8u(1−u)≤(1+u)28u(1-u)\le(1+u)^2 is equivalent to (3u−1)2≥0(3u-1)^2\ge0.

For L=ZnL=\mathbb{Z}^n and R=4/3R=4/3, equality holds in (18). This example explains why the factor 9/89/8 enters the list size.

Exact moments for finite shifts

The algorithm uses a finite quotient, not a continuous random translate. The same moments hold exactly on a sufficiently aligned rational grid.

Lemma 4.5. Suppose Γ⊂G=δZn\Gamma\subset G=\delta\mathbb{Z}^n and R/δ∈ZR/\delta\in\mathbb{Z}. Fix z∈Gz\in G. For uniform a∈G/Γa\in G/\Gamma, let

Ja(z)=#((a−z/2+Γ)∩BR),μR=Rn/D.J_a(z)=\#\bigl((a-z/2+\Gamma)\cap B_R\bigr),\qquad\mu_R=R^n/D.

Then

Ea[Ja(z)]=μR,(19)\mathbb{E}_a[J_a(z)]=\mu_R, \tag*{(19)}
Ea[Ja(z)2]=(1+ΘR(Γ∗))μR2,(20)\mathbb{E}_a[J_a(z)^2]=(1+\Theta_R(\Gamma^*))\mu_R^2, \tag*{(20)}
Ea[Ja(z)Ja(z′)]≤(1+ΘR(Γ∗))μR2(z,z′∈G).(21)\mathbb{E}_a[J_a(z)J_a(z')]\le(1+\Theta_R(\Gamma^*))\mu_R^2\qquad(z,z'\in G). \tag*{(21)}

Proof. Every interval of length RR on the translate δZ−zi/2\delta\mathbb{Z}-z_i/2 contains exactly R/δR/\delta points. Averaging the coset therefore gives

Ea[Ja(z)]=δnD(R/δ)n=μR.\mathbb{E}_a[J_a(z)]=\frac{\delta^n}{D}(R/\delta)^n=\mu_R.

In the square of the count, the difference between two midpoints belongs to Γ\Gamma. For w∈Γw \in\Gamma, each coordinate intersection contains exactly (R−∣wi∣)+/δ(R-\lvert w_i\rvert)_+/\delta points. Its endpoints differ by integer multiples of δ\delta, even when zi/2z_i/2 is a half-grid point. Thus

Ea[Ja(z)2]=1D∑w∈Γ∏i(R−∣wi∣)+.\mathbb{E}_a[J_a(z)^2] = \frac{1}{D}\sum_{w\in\Gamma}\prod_i(R-\lvert w_i\rvert)_+.

Use (15) for the second identity. The two second moments are the same for all zz, so Cauchy–Schwarz proves the mixed bound.

A random superlattice with small box variance

We now make the bounds in Lemma 4.5 useful at the shortest vector scale. Fix a candidate scale ℓ\ell satisfying

ℓ≤λ≤(1+η)ℓ,η=n−3.(22)\ell\le\lambda\le(1+\eta)\ell,\qquad\eta=n^{-3}. \tag*{(22)}

The algorithm tries a polynomial number of scales. This section analyzes a scale satisfying (22). Let h≥2h\ge2 be an integer to be specified later, and put

C=98,P0=Cndet⁡Lℓn24h.(23)C=\frac{9}{8},\qquad P_0=C^n\frac{\det L}{\ell^n}2^{4h}. \tag*{(23)}

Choose a prime pp with P0≤p≤4P0P_0\le p\le4P_0. If L=BZnL=B\mathbb{Z}^n, choose a uniform nonzero u∈Fpnu\in\mathbb{F}_p^n and define

Γ=L+ZBup,D=det⁡Γ=det⁡Lp.(24)\Gamma=L+\mathbb{Z}\frac{Bu}{p},\qquad D=\det\Gamma=\frac{\det L}{p}. \tag*{(24)}

Then

14ℓnCn−22−4h≤D≤ℓnCn−22−4h.(25)\frac{1}{4}\ell^n C^{n-2}2^{-4h}\le D\le\ell^n C^{n-2}2^{-4h}. \tag*{(25)}

The index is always pp, so DD is fixed before uu is drawn.

Reducing box variance through the dual lattice

The dual of (24) is

Γ∗={B−Tz:z∈Zn, ⟨z,u⟩=0(modp)}.\Gamma^*=\{B^{-T}z:z\in\mathbb{Z}^n,\ \langle z,u\rangle=0\pmod p\}.

A vector outside pL∗pL^* survives with probability

αp=pn−1−1pn−1<1p,\alpha_p=\frac{p^{n-1}-1}{p^n-1}<\frac{1}{p},

while every vector in pL∗pL^* survives. Consequently,

EΓ[ΘR(Γ∗)]=αpΘR(L∗)+(1−αp)ΘR(pL∗)≤ΘR(L∗)p+ΘR(pL∗).(26)\mathbb{E}_{\Gamma}[\Theta_R(\Gamma^*)]=\alpha_p\Theta_R(L^*)+(1-\alpha_p)\Theta_R(pL^*)\le\frac{\Theta_R(L^*)}{p}+\Theta_R(pL^*). \tag*{(26)}

This is the same elementary random-kernel calculation used for Gaussian weights in [9]. Here the weights are products of squared sinc functions.

The first term of (26) is at most 2−4h2^{-4h} by Lemma 4.4. The second term is the variance associated with the fine lattice L/pL/p. We bound it by counting fundamental cells near the boundary of a box.

Lemma 5.1. For all sufficiently large nn, the parameters above satisfy

ΘR(pL∗)≤2−4h(R≥ℓ).\Theta_R(pL^*) \le2^{-4h} \qquad(R \ge\ell).

The threshold is uniform over the input lattice, the correct scale, and h≥2h \ge2.

Proof. By (6),

λn(2)(L)≤ndet⁡Lλnn−1.\lambda_n^{(2)}(L) \le\sqrt{n}\frac{\det L}{\lambda_n^{n-1}}.

Apply Lemma 3.1 and (8) to LL, then divide the resulting basis by pp. A fundamental cell for L/pL/p is contained in [−F,F]n[-F,F]^n, where, with K(n)=n3Ared(n)K(n)=n^3A_{\mathrm{red}}(n),

F≤K(n)ℓC−n2−4h.(27)F \le K(n)\ell C^{-n}2^{-4h}. \tag*{(27)}

We use this cell only for analysis.

Let d=det⁡(L/p)d=\det(L/p). For every translate of a box of side RR, the union of the cells anchored at its lattice points is contained in the box expanded by FF in each direction. Conversely, it covers the box contracted by FF in each direction. Therefore

(R−2F)+n≤dJR(a)≤(R+2F)n.(R-2F)^n_+ \le dJ_R(a) \le(R+2F)^n.

For 2nF/R≤12nF/R\le1, the relative deviation from the mean Rn/dR^n/d is at most 4nF/R4nF/R. The variance identity in Lemma 4.1 gives

ΘR(pL∗)≤16n2(F/R)2≤16n2K(n)2C−2n2−8h.\Theta_R(pL^*) \le16n^2(F/R)^2 \le16n^2K(n)^2C^{-2n}2^{-8h}.

The last expression is at most 2−4h2^{-4h} for all sufficiently large nn.

Theorem 5.2 (Small box variance on a random superlattice). Fix mm prescribed widths R≥ℓR\ge\ell. For all sufficiently large nn, the construction (24) satisfies

ΘR(Γ∗)≤θ:=2−hat every prescribed width\Theta_R(\Gamma^*) \le\theta:= 2^{-h} \quad\text{at every prescribed width}

except with probability at most m21−3hm2^{1-3h}.

Proof. Equations (26) and (27), together with Lemma 5.1, give

EΓ[ΘR(Γ∗)]≤21−4h.\mathbb{E}_{\Gamma}[\Theta_R(\Gamma^*)] \le2^{1-4h}.

Apply Markov’s inequality at each prescribed width and take a union bound.

Choosing the initial scale

Call the event in Theorem 5.2 G\mathcal{G}. We include ℓ\ell among the prescribed widths. On G\mathcal{G}, there is no nonzero ξ∈Γ∗\xi\in\Gamma^* with ℓ∥ξ∥2≤1/4\ell\lVert\xi\rVert_2\le1/4. Indeed, the elementary inequality sin⁡t≥t−t3/6\sin t\ge t-t^3/6 gives

∏isinc⁡2(ℓξi)≥1−π23ℓ2∥ξ∥22≥1−π248>12,\prod_i \operatorname{sinc}^2(\ell\xi_i)\ge1-\frac{\pi^2}{3}\ell^2\lVert\xi\rVert_2^2\ge1-\frac{\pi^2}{48}>\frac{1}{2},

contradicting Θℓ(Γ∗)≤2−h\Theta_\ell(\Gamma^*)\le2^{-h}. By (7),

λn(2)(Γ)<4nℓ.\lambda_n^{(2)}(\Gamma)<4n\ell.

After Lemma 3.1, the fundamental cell has coordinate radius at most

Fmax⁡=4n3Ared(n)ℓ.(28)F_{\max}=4n^3A_{\mathrm{red}}(n)\ell. \tag*{(28)}

This bound can be checked from the computed basis by summing the infinity norms of its columns.

γ=1920,R0=(1+η)ℓ,Rj=R0γ−j.(29)\gamma= \frac{19}{20}, \qquad R_0 = (1+\eta)\ell, \qquad R_j = R_0\gamma^{-j}. \tag*{(29)}

Let tt be the least nonnegative integer such that

Rt≥8n5Ared(n)ℓ=2n2Fmax⁡.(30)R_t \ge8n^5 A_{\mathrm{red}}(n)\ell= 2n^2F_{\max}. \tag*{(30)}

Since AredA_{\mathrm{red}} is a fixed polynomial, t=O(log⁡n)t = O(\log n). Both tt and the ratios Rj/ℓR_j/\ell depend only on nn. The widths supplied to Theorem 5.2 are ℓ,R0,…,Rt\ell, R_0, \ldots, R_t, so they are fixed before the random superlattice is drawn.

Building the lists

Fix Γ∈G\Gamma\in\mathcal{G} and its preprocessed basis. We construct a list at radius RjR_j in any prescribed coset c+Γc+\Gamma. The construction is a binary tree with leaves at radius RtR_t. Each subtree uses private samples, private shifts, and private retention coins.

Choose one rational grid G=δZnG = \delta\mathbb{Z}^n satisfying

p−1L⊆G,ℓ2δ∈Z,Rj6δ∈Z(0≤j≤t),δℓ≤n−10.(31)p^{-1}L \subseteq G,\qquad\frac{\ell}{2\delta}\in\mathbb{Z},\qquad\frac{R_j}{6\delta}\in\mathbb{Z}\quad(0\le j\le t),\qquad\frac{\delta}{\ell}\le n^{-10}. \tag*{(31)}

A common denominator followed by integer subdivision gives such a grid with polynomial encoding length. The large size of the quotient G/ΓG/\Gamma does not affect the cost of sampling one of its elements.

The leaf sampler

At a leaf, the box is wide relative to a fundamental cell. This permits a direct sampler with exactly constant expected counts.

Let P=BΓ[0,1)nP=B_\Gamma[0,1)^n be the fundamental cell and use the bound P⊆[−Fmax⁡,Fmax⁡]nP\subseteq[-F_{\max},F_{\max}]^n. Set

U=QRt+Fmax⁡,VU=vol⁡(U).U=Q_{R_t+F_{\max}},\qquad V_U=\operatorname{vol}(U).

Draw XX uniformly from U∩GU\cap G. For the prescribed coset c+Γc+\Gamma, compute

Y=c+BΓ[BΓ−1(X−c)].(32)Y=c+B_\Gamma\left[B_\Gamma^{-1}(X-c)\right]. \tag*{(32)}

Then X∈Y+PX\in Y+P. Keep the proposal only when Y∈QRtY\in Q_{R_t}.

Lemma 6.1. For any positive integer NN, let

M=⌈NVU(2Rt)n⌉,q0=NVUM(2Rt)n.M=\left\lceil\frac{NV_U}{(2R_t)^n}\right\rceil,\qquad q_0=\frac{NV_U}{M(2R_t)^n}.

Make MM independent proposals as in (32). Independently keep each successful proposal with probability q0q_0. For every fixed coset c+Γc+\Gamma, the resulting list satisfies

m(x)=At:=ND(2Rt)n,S(x,x′)≤At2(x,x′∈(c+Γ)∩QRt).m(x)=A_t:=\frac{ND}{(2R_t)^n},\qquad S(x,x')\le A_t^2\quad(x,x'\in(c+\Gamma)\cap Q_{R_t}).

It uses O(N)O(N) proposals, each of polynomial cost.

Proof. For every allowed output yy, its complete cell y+Py+P lies in UU. That cell contains exactly D/δnD/\delta^n grid points, one for each coset of Γ\Gamma in GG. Hence a proposal equals yy with probability D/VUD/V_U, independently of yy and cc.

The first moment is Mq0D/VU=AtMq_0D/V_U=A_t. Distinct retained entries come from distinct proposals, so

S(x,x′)=M(M−1)(q0D/VU)2=(1−1/M)At2.S(x,x')=M(M-1)(q_0D/V_U)^2=(1-1/M)A_t^2.

Finally, (30) gives

VU(2Rt)n=(1+Fmax⁡Rt)n≤e1/(2n).\frac{V_U}{(2R_t)^n}=\left(1+\frac{F_{\max}}{R_t}\right)^n\le e^{1/(2n)}.

Thus M=O(N)M=O(N).

One shortening step

Suppose a node is to produce a list in c+Γc+\Gamma at radius γR\gamma R. Choose a uniform a∈G/Γa\in G/\Gamma. The two child cosets are

c+=a+Γ,c−=a−c+Γ.(33)c_+=a+\Gamma,\qquad c_-=a-c+\Gamma. \tag*{(33)}

Generate the two child lists at radius RR with independent private randomness. For each ordered pair of child entries, keep the difference with probability

q1{x−y∈QγR}1{(x+y)/2∈BR},q=(2/γ)nN.(34)q\mathbf{1}_{\{x-y\in Q_{\gamma R}\}}\mathbf{1}_{\{(x+y)/2\in B_R\}},\qquad q=\frac{(2/\gamma)^n}{N}. \tag*{(34)}

Each distinct pair of child identifiers uses an independent coin and creates at most one output entry. Fix z∈(c+Γ)∩QγRz\in(c+\Gamma)\cap Q_{\gamma R}. An admissible pair with difference zz is uniquely determined by its midpoint. Its midpoint set is

(a−z/2+Γ)∩BR.(a-z/2+\Gamma)\cap B_R.

Every such midpoint gives two endpoints in the child boxes. Thus the number of representations is exactly the variable Ja(z)J_a(z) of Lemma 4.5.

The full differencing recursion of [GHH26, Section 4, Exact factorial recursion] applies here with a constant expected count per point. Its error has two sources: variation in the number of admissible midpoints and reuse of an input entry. The first is controlled by the box variance, while the second contributes a term that decreases with the list size.

Lemma 6.2 (Counting moments after a difference step). Suppose both child lists satisfy (12) with common expected count A=ARA=A_R and error ε\varepsilon, uniformly over their prescribed cosets. Assume they are independent after the cosets in (33) are fixed, and that q≤1q\le1. The output satisfies

mout(z)=AγRm_{\mathrm{out}}(z)=A_{\gamma R}

and

Sout(z,z′)≤eε′AγR2,ε′=2ε+log⁡(1+ΘR(Γ∗)+2n+1N).(35)S_{\mathrm{out}}(z,z')\le e^{\varepsilon'}A_{\gamma R}^2,\qquad\varepsilon'=2\varepsilon+\log\left(1+\Theta_R(\Gamma^*)+\frac{2^{n+1}}{N}\right). \tag*{(35)}

The bounds hold for every fixed output coset and all z,z′∈(c+Γ)∩QγRz,z'\in(c+\Gamma)\cap Q_{\gamma R}.

Proof. Fix aa. The first moment at zz is qA2Ja(z)qA^2J_a(z). Averaging aa gives

qA2μR=(2/γ)nN(ND(2R)n)2RnD=ND(2γR)n=AγR.qA^2\mu_R=\frac{(2/\gamma)^n}{N}\left(\frac{ND}{(2R)^n}\right)^2\frac{R^n}{D} =\frac{ND}{(2\gamma R)^n}=A_{\gamma R}.

For the second factorial moment, classify two distinct output entries by their child identifiers. There are three cases: four distinct child entries, one shared left entry, or one shared right entry. Four distinct child entries contribute at most

e2εq2A4Ea[Ja(z)Ja(z′)]≤e2εq2A4(1+ΘR)μR2.e^{2\varepsilon}q^2A^4\mathbb{E}_a[J_a(z)J_a(z')] \le e^{2\varepsilon}q^2A^4(1+\Theta_R)\mu_R^2.

For a shared left entry at xx, the right values are fixed as x−zx-z and x−z′x-z'. The number of possible triples is at most Ja(z)J_a(z). This contribution is therefore at most

e2εq2A3Ea[Ja(z)]=e2εq2A3μR.e^{2\varepsilon}q^2A^3\mathbb{E}_a[J_a(z)] = e^{2\varepsilon}q^2A^3\mu_R.

The same bound holds for a shared right entry. This also covers z=z′z=z', since different entries may have equal values. Sharing both child identifiers would give the same output entry and is excluded from the factorial moment. Divide the sum by AγR2=(qA2μR)2A_{\gamma R}^2=(qA^2\mu_R)^2. Since

AμR=N/2n,A\mu_R=N/2^n,

the result is (35).

The complete tree

Set Aj=ND/(2Rj)nA_j=ND/(2R_j)^n. A call Build⁡(j,c)\operatorname{Build}(j,c) produces a list in (c+Γ)∩QRj(c+\Gamma)\cap Q_{R_j}. At j=tj=t, it invokes the leaf sampler. Otherwise, it uses (33), calls Build⁡(j+1,a)\operatorname{Build}(j+1,a) and Build⁡(j+1,a−c)\operatorname{Build}(j+1,a-c) independently, and applies (34) at input radius Rj+1R_{j+1}. Starting with εt=0\varepsilon_t=0, Lemma 6.2 gives

ε0≤(2t−1)(θ+2n+1N).(36)\varepsilon_0 \le(2^t-1)\left(\theta+\frac{2^{n+1}}{N}\right). \tag*{(36)}

The factor 2t2^t counts the effect of the entire tree. It remains polynomial because t=O(log⁡n)t=O(\log n).

The first moment stays exact throughout the construction. If a node’s coset is uniform in G/ΓG/\Gamma, then (10) gives

E[∣Xj∣]=AjδnD#(QRj∩G)=N.(37)\mathbb{E}[|\mathcal{X}_j|]=A_j\frac{\delta^n}{D}\#(Q_{R_j}\cap G)=N. \tag*{(37)}

A uniform root coset makes every node coset uniform. The lists below two distinct children need only be independent after their prescribed cosets are fixed. Algorithm 1 describes the generation rule. The implementation places fixed limits on list sizes and search work. These limits are chosen in § 9. Until then, the counting analysis refers to the same finite construction without those limits.

Algorithm 1: Build(j,cj,c)

Input: Level jj, coset representative c∈Gc \in G, fixed Γ\Gamma, grid and radii. Output: A list in (c+Γ)∩QRj(c+\Gamma)\cap QR_j, or fail.

  1. if j=tj=t then

  2. return the list of Lemma 6.1

  3. Choose aa uniformly in G/ΓG/\Gamma

  4. X+←Build⁡(j+1,a)\mathcal{X}_{+} \leftarrow\operatorname{Build}(j+1,a) and X−←Build⁡(j+1,a−c)\mathcal{X}_{-} \leftarrow\operatorname{Build}(j+1,a-c), using independent randomness

  5. if either call failed then

  6. return fail

  7. Initialize an empty output list

  8. Use the ternary search of § 7 on X+,X−\mathcal{X}_{+},\mathcal{X}_{-}

  9. foreach reported pair of entries (x,y)(x,y) do

  10. if x−y∈QRjx-y\in QR_j and (x+y)/2∈BRj+1(x+y)/2\in BR_{j+1} then

  11. With probability qq, append a new entry with value x−yx-y

  12. return the output list

Finding pairs for recursive differencing

To implement the difference rule, we first select candidate pairs by their coordinate classes and then test the exact conditions in (34). A prefix table reports these candidates, and the counting identities from § 6 bound their expected number.

Three classes per coordinate

At input radius RR, define

bi(x)={0,∣xi∣≤R/3,1,R/3<∣xi∣≤2R/3,2,2R/3<∣xi∣≤R.(38)b_i(x)= \begin{cases} 0, & |x_i|\le R/3,\\ 1, & R/3<|x_i|\le2R/3,\\ 2, & 2R/3<|x_i|\le R. \end{cases} \tag*{(38)}

For an eligible pair,

∣xi∣+∣yi∣=max⁡{∣xi−yi∣,∣xi+yi∣}≤R,|x_i|+|y_i|=\max\{|x_i-y_i|,|x_i+y_i|\}\le R,

so bi(x)+bi(y)≤2b_i(x)+b_i(y)\le2. Thus, for each left entry xx, we need to report all right entries whose class vectors satisfy bi(y)≤2−bi(x)b_i(y)\le2-b_i(x) in every coordinate. We next give a table that answers these queries and will also be used for the binary classes in the final search.

Prefix tables and search cost

Consider records with class vectors in {0,…,s−1}n\{0,\ldots,s-1\}^{n}, where ss is either two or three. Given upper bounds u∈{0,…,s−1}nu\in\{0,\ldots,s-1\}^{n}, a query reports all records whose class vector bb satisfies bi≤uib_i\le u_i in every coordinate.

Let H(b)H(b) be the histogram of class vectors, with a list of record identifiers at each occupied vector. For every 0≤k≤n0\le k\le n, store a table

Tk(a1,…,ak,uk+1,…,un)=∑bk+1≤uk+1,…,bn≤unH(a1,…,ak,bk+1,…,bn).(39)T_k(a_1,\ldots,a_k,u_{k+1},\ldots,u_n) = \sum_{b_{k+1}\le u_{k+1},\ldots,b_n\le u_n} H(a_1,\ldots,a_k,b_{k+1},\ldots,b_n). \tag*{(39)}

Each table has sns^n entries. It is obtained from HH by prefix sums in the last n−kn-k coordinates. All tables therefore take O(n2sn)O(n^2s^n) arithmetic operations and O(nsn)O(ns^n) storage, in addition to the records.

To answer a query, start with the empty prefix. At depth kk, try the at most ss allowed values for the next coordinate and consult Tk+1T_{k+1}. Descend only when the count is positive. At depth nn, report the identifiers stored at that class vector.

Every visited nonempty prefix has a reported record below it. Charging the prefix to the first such record gives at most nn charges per record, each with at most ss child tests, so a query costs

O(ns(1+number of reported records)).O(ns(1+\text{number of reported records})).

For the internal search, build the ternary tables on the right list and query with ui=2−bi(x)u_i=2-b_i(x) for each left entry xx. Test the exact difference and midpoint conditions on every report. Each pair of entry identifiers is reported at most once, so independent retention coins implement the generation rule of § 6.

Proposition 7.1. Fix Γ∈G\Gamma\in G and an internal call whose prescribed output coset is uniform in G/ΓG/\Gamma. If the two child lists have the exact first moments in (12), then their expected number of ternary candidate pairs is

E[P3]=N2(23+2δ3R−δ24R2)n.(40)\mathbb{E}[P_3]=N^2\left(\frac{2}{3}+\frac{2\delta}{3R}-\frac{\delta^2}{4R^2}\right)^n. \tag*{(40)}

Including construction of the tables, the expected search work is at most

poly⁡(n,size⁡(B))(3n+N+N2(2/3)neO(nδ/R)).\operatorname{poly}(n,\operatorname{size}(B))\left(3^n+N+N^2(2/3)^n e^{O(n\delta/R)}\right).

Proof. Write the parent coset as c+Γc+\Gamma. For independent uniform c,a∈G/Γc,a\in G/\Gamma, the map

(c,a)⟼(a,a−c)(c,a)\longmapsto(a,a-c)

is a bijection of the quotient squared. Hence the two child cosets are jointly uniform. First fix these cosets and multiply the child first moments, using their private independence. Averaging the cosets then shows that every pair in (QR∩G)2(Q_R\cap G)^2 has expected count

AR2(δn/D)2.A_R^2(\delta^n/D)^2.

Let m=R/δm=R/\delta, which is divisible by six. The three one-dimensional class sizes are 2m/3+12m/3+1, 2m/32m/3, and 2m/3−12m/3-1. Summing the six combinations with class sum at most two gives the fraction

23+23m−14m2.\frac{2}{3}+\frac{2}{3m}-\frac{1}{4m^2}.

The free grid has (2R/δ)2n(2R/\delta)^{2n} endpoint pairs, which proves (40) after multiplication by the expected count above. The table construction and query bounds, together with E[∣X±∣]=N\mathbb{E}[|\mathcal{X}_{\pm}|]=N, give the work estimate. □

A uniform common root coset makes the output coset of every internal call marginally uniform, so Proposition 7.1 applies at every level.

Recovering a shortest vector

The two final lists lie in the same coset z+Γz+\Gamma and are independent conditional on zz and Γ\Gamma. The last search uses the original lattice LL both to recognize valid differences and to bound its work.

Quotient labels and a binary condition

For x=z+gxx=z+g_x with gx∈Γg_x\in\Gamma, give the entry label

lab⁡(x)=gx+L∈Γ/L.(41)\operatorname{lab}(x)=g_x+L\in\Gamma/L. \tag*{(41)}

Then

lab⁡(x)=lab⁡(y)⟺x−y∈L.\operatorname{lab}(x)=\operatorname{lab}(y)\Longleftrightarrow x-y\in L.

A label is represented by one field element, as detailed in Appendix § 11.

Let

I=[−R0,R0),B0=[−ℓ/2,ℓ/2).I=[-R_0,R_0),\qquad B_0=[-\ell/2,\ell/2).

For each endpoint, store the binary class vector

hi(x)=1{xi∉B0}.h_i(x)=\mathbf{1}_{\{x_i\notin B_0\}}.

The final search reports exactly the pairs of entries satisfying

lab⁡(x)=lab⁡(y),hi(x)+hi(y)≤1(1≤i≤n).(42)\operatorname{lab}(x)=\operatorname{lab}(y),\qquad h_i(x)+h_i(y)\le1\quad(1\le i\le n). \tag*{(42)}

Thus every coordinate has at least one endpoint in the inner interval B0B_0. Each reported nonzero difference is tested for membership in LL and compared with the current best vector.

A shortest vector has many compatible representations

Fix a shortest vector vv. The full midpoint box BℓB_\ell gives endpoints

x=M+v/2,y=M−v/2x=M+v/2,\qquad y=M-v/2

in QR0Q_{R_0}. Let Jfull(z)J_{\mathrm{full}}(z) count its midpoints in z−v/2+Γz-v/2+\Gamma, and let J(z)J(z) count those also satisfying the binary condition in (42).

Lemma 8.1. For every Γ∈G\Gamma\in\mathcal{G}, a uniform z∈G/Γz\in G/\Gamma satisfies

J(z)≥14ℓnD(43)J(z)\ge\frac{1}{4}\frac{\ell^n}{D} \tag*{(43)}

except with probability at most 4θ+4nη4\theta+4n\eta.

Proof. Put μ=ℓn/D\mu=\ell^n/D. By Lemma 4.5,

Ez[Jfull]=μ,Var⁡zJfull≤θμ2.\mathbb{E}_z[J_{\mathrm{full}}]=\mu,\qquad\operatorname{Var}_z J_{\mathrm{full}}\le\theta\mu^2.

Chebyshev’s inequality gives Jfull≥μ/2J_{\mathrm{full}}\ge\mu/2 except with probability 4θ4\theta.

Consider one coordinate. If ∣vi∣≤ℓ|v_i|\le\ell, every midpoint in [−ℓ/2,ℓ/2)[-\ell/2,\ell/2) puts at least one endpoint in B0B_0. If ∣vi∣>ℓ|v_i|>\ell, the excluded midpoints form a central interval of length ∣vi∣−ℓ≤ηℓ|v_i|-\ell\le\eta\ell. The endpoints of this interval align with the midpoint grid because vi∈δZv_i\in\delta\mathbb{Z} and ℓ/(2δ)∈Z\ell/(2\delta)\in\mathbb{Z}.

A union bound over coordinates therefore shows that the expected number of deleted midpoints is at most nημn\eta\mu. Markov’s inequality bounds the probability of deleting more than μ/4\mu/4 by 4nη4n\eta. On the complementary events, (43) holds.

To turn these midpoint locations into actual pairs, fix a root coset with J≥1J \ge1 and let ZZ count pairs of entries with difference vv and a compatible midpoint. The two root lists are independent with the moments in (12), so E[Z]=A02J=:M\mathbb{E}[Z] = A_0^2J =: M. Each endpoint determines the other uniquely. Thus two different midpoint locations have different endpoint values on both sides, and contribute at most e2ε0A04e^{2\varepsilon_0}A_0^4 to the second moment. At a repeated location, the ordinary second moment on each side is at most eε0(A02+A0)e^{\varepsilon_0}(A_0^2 + A_0). Consequently,

E[Z2]≤e2ε0(A04J2+2A03J+A02J),\mathbb{E}[Z^2] \le e^{2\varepsilon_0}(A_0^4J^2 + 2A_0^3J + A_0^2J),

and the second-moment inequality gives

P[Z>0]≥e−2ε01+2/(A0J)+1/M≥e−2ε0(1+M−1/2)2.(44)\mathbb{P}[Z > 0] \ge\frac{e^{-2\varepsilon_0}}{1 + 2/(A_0J) + 1/M} \ge\frac{e^{-2\varepsilon_0}}{(1 + M^{-1/2})^2}. \tag*{(44)}

where the last inequality uses A0J=MJ≥MA_0J = \sqrt{MJ} \ge\sqrt{M}.

On (43), the expected number of these pairs satisfies

A02J≥N2Dℓn4(2R0)2n.(45)A_0^2J \ge\frac{N^2D\ell^n}{4(2R_0)^{2n}}. \tag*{(45)}

The polynomial factors selected in § 9 make this quantity tend to infinity.

Bounding the number of reported pairs

We next bound all pairs satisfying (42), including zero differences. This is where the final binary rule is more useful than the internal ternary rule.

Use the discrete sets

Iδ=I∩δZ,Bδ=B0∩δZ,g=21Iδ−1Bδ≥0.I_\delta= I \cap\delta\mathbb{Z}, \qquad B_\delta= B_0 \cap\delta\mathbb{Z}, \qquad g = 2\mathbf{1}_{I_\delta} - \mathbf{1}_{B_\delta} \ge0.

For w∈δZw \in\delta\mathbb{Z}, let cδ(w)c_\delta(w) be δ\delta times the number of compatible one-dimensional endpoint pairs at displacement ww:

cδ(w)=δ∑x∈δZ1Iδ(x)1Iδ(x−w)1{x∈Bδ or x−w∈Bδ}.(46)c_\delta(w) = \delta\sum_{x \in\delta\mathbb{Z}} \mathbf{1}_{I_\delta}(x)\mathbf{1}_{I_\delta}(x-w)\mathbf{1}_{\{x\in B_\delta\ \mathrm{or}\ x-w\in B_\delta\}}. \tag*{(46)}

The key is to express this count using the inner interval and a nonnegative weight, so that the separation of LL can bound the lattice sum directly. Inclusion and exclusion gives

cδ(w)=δ∑x∈δZ1Bδ(x)g(x−w).(47)c_\delta(w) = \delta\sum_{x \in\delta\mathbb{Z}} \mathbf{1}_{B_\delta}(x)g(x-w). \tag*{(47)}

The two cross terms, obtained by putting the first or the second endpoint in BδB_\delta, agree by reflection about −δ/2-\delta/2, the common center of IδI_\delta and BδB_\delta.

Lemma 8.2 (Final report bound). If ℓ≤λ1(∞)(L)\ell\le\lambda_1^{(\infty)}(L), then

∑w∈L∏i=1ncδ(wi)≤(4R0−ℓ)n.(48)\sum_{w \in\mathcal{L}} \prod_{i=1}^{n} c_\delta(w_i) \le(4R_0-\ell)^n. \tag*{(48)}

For the two root lists generated in a uniform common coset of a fixed Γ∈G\Gamma\in\mathcal{G}, the number PP of pairs satisfying (42) obeys

E[P]≤A02D(4R0−ℓ)n.(49)\mathbb{E}[P] \le\frac{A_0^2}{D}(4R_0-\ell)^n. \tag*{(49)}

Proof. Apply (47) in every coordinate, then set t=x−wt=x-w. All summands are nonnegative, so

∑w∈L∏icδ(wi)=δn∑t∈G∏ig(ti)∑w∈L1Bδn(t+w).\sum_{w\in L}\prod_i c_\delta(w_i)=\delta^n\sum_{t\in G}\prod_i g(t_i)\sum_{w\in L}\mathbf{1}_{B_\delta^n}(t+w).

The inner sum is at most one. Two points in the half-open cube BδnB_\delta^n differ by less than ℓ\ell in every coordinate, while a nonzero vector of LL has infinity norm at least ℓ\ell. Therefore

∑w∈L∏icδ(wi)≤δn∑t∈G∏ig(ti)=(δ∑x∈δZg(x))n=(4R0−ℓ)n.\sum_{w\in L}\prod_i c_\delta(w_i)\le\delta^n\sum_{t\in G}\prod_i g(t_i)=\left(\delta\sum_{x\in\delta\mathbb{Z}}g(x)\right)^n=(4R_0-\ell)^n.

For the work estimate, first fix the common coset z+Γz+\Gamma. The two root lists use independent private randomness, and their first moments are exactly A0A_0. If x−y=w∈Lx-y=w\in L, then membership of xx in z+Γz+\Gamma already implies membership of yy. Averaging zz therefore contributes one factor δn/D\delta^n/D. For a fixed ww, the number of compatible free grid pairs is δ−n∏icδ(wi)\delta^{-n}\prod_i c_\delta(w_i). Thus

E[P]=A02D∑w∈L∏icδ(wi),\mathbb{E}[P]=\frac{A_0^2}{D}\sum_{w\in L}\prod_i c_\delta(w_i),

which proves (49). The term w=0w=0 is included throughout.

To see the 3n3^n balance already at this point, put r=R0/ℓr=R_0/\ell. Our parameters give N2D/ℓn=4npoly⁡(n)N^2D/\ell^n=4^n\operatorname{poly}(n), so the report bound is

E[P]≤poly⁡(n)(4r−1r2)n≤3npoly⁡(n),r≥1.\mathbb{E}[P]\le\operatorname{poly}(n)\left(\frac{4r-1}{r^2}\right)^n\le3^n\operatorname{poly}(n),\qquad r\ge1.

The last inequality is 4r−1≤3r24r-1\le3r^2. The remaining task is to find these pairs without scanning all pairs in a large label group.

Searching within label groups

To turn the report bound into a running time bound, we must also control the cost of searching within each label group. A split by group size balances direct comparisons against the cost of building a binary table.

Proposition 8.3. Let two fixed labeled lists contain MM entries in total, and let PP be the number of their pairs satisfying (42). There is a deterministic algorithm that reports every such pair of entries once, in time

poly⁡(n,log⁡(M+2),label length)(M2n/2+P)(50)\operatorname{poly}(n,\log(M+2),\text{label length})\left(M2^{n/2}+P\right) \tag*{(50)}

and space poly⁡(n)(M+2n)\operatorname{poly}(n)(M+2^n).

Proof. Sort the entries by label. Put H=⌈2n/2⌉H=\lceil2^{n/2}\rceil, and let mξm_\xi be the total size of the two sides in label group ξ\xi.

If mξ≤Hm_\xi\le H, check all cross pairs in that group. The total cost of these groups is at most ∑ξHmξ≤HM\sum_\xi Hm_\xi\le HM.

There are at most M/HM/H groups with mξ>Hm_\xi>H. In each such group, build the binary prefix tables of § 7.2 on the right side and query with bounds ui=1−hi(x)u_i=1-h_i(x) for each left entry xx. The total table and query cost is

poly⁡(n)(MH2n+M+P).\operatorname{poly}(n)\left(\frac{M}{H}2^n+M+P\right).

Together with the small groups and sorting, this gives (50). Process the large groups one at a time to obtain the space bound.

The algorithm and its analysis

We now choose the polynomial factors, remove knowledge of λ\lambda, and place finite limits on every trial. The list construction and the two search bounds then give the claimed complexity.

Parameters and the scale grid

The constants and radii are those of (29) and (30). Let

Q=2t+2,h=⌈log⁡2(Q(n+2)10)⌉,N=23h⌊(9/2)n⌋.(51)Q = 2^{t+2}, \qquad h = \left\lceil\log_2\left(Q(n+2)^{10}\right) \right\rceil, \qquad N = 2^{3h}\left\lfloor\sqrt{(9/2)^n} \right\rfloor. \tag*{(51)}

Here QQ exceeds the total number of nodes in the two trees. Since t=O(log⁡n)t = O(\log n),

Q=poly⁡(n),h=O(log⁡n),(3/2)n23h≤N≤2(3/2)n23h.Q = \operatorname{poly}(n), \qquad h = O(\log n), \qquad(3/\sqrt{2})^n 2^{3h} \le N \le2(3/\sqrt{2})^n 2^{3h}.

Since γC>1\gamma\sqrt{C} > 1, the retention probability in (34) satisfies

q≤2−3h(γC)−n<1.q \le2^{-3h}(\gamma\sqrt{C})^{-n} < 1.

On every good superlattice, (36) gives

ε0≤Q(2−h+2n+1N)≤(n+2)−10+2Q−2(n+2)−30.(52)\varepsilon_0 \le Q\left(2^{-h}+\frac{2^{n+1}}{N}\right) \le(n+2)^{-10}+2Q^{-2}(n+2)^{-30}. \tag*{(52)}

Set

ℓlo=∥B−1∥∞→∞−1,ℓhi=min⁡i∥bi∥∞.\ell_{\mathrm{lo}}=\lVert B^{-1}\rVert_{\infty\to\infty}^{-1}, \qquad\ell_{\mathrm{hi}}=\min_i\lVert b_i\rVert_\infty.

Then ℓlo≤λ≤ℓhi\ell_{\mathrm{lo}}\le\lambda\le\ell_{\mathrm{hi}}. We try every scale ℓj=ℓlo(1+η)j≤ℓhi\ell_j=\ell_{\mathrm{lo}}(1+\eta)^j\le\ell_{\mathrm{hi}}. This gives

O(1+n3log⁡(ℓhi/ℓlo))=poly⁡(n,size⁡(B))O\left(1+n^3\log(\ell_{\mathrm{hi}}/\ell_{\mathrm{lo}})\right)=\operatorname{poly}(n,\operatorname{size}(B))

scales of polynomial encoding length, at least one of which satisfies (22).

At each scale, set Y=max⁡{2,⌈P0⌉}Y=\max\{2,\lceil P_0\rceil\} and test O((n+h+1)log⁡(2Y))O((n+h+1)\log(2Y)) independent uniform candidates in [Y,2Y][Y,2Y] by deterministic primality testing [3]. Standard prime density bounds make the failure probability at most 2−n−102^{-n-10}, and every prime returned on a correct scale satisfies P0≤p≤4P0P_0\le p\le4P_0.

A trial with resource limits

Choose the list limit

Lmax⁡=N22h.(53)L_{\max}=N2^{2h}. \tag*{(53)}

Let pop(n,size⁡(B))p_{\mathrm{op}}(n,\operatorname{size}(B)) bound the polynomial overhead of the arithmetic and search operations, and set the work limit for each pair search to

Wmax⁡=3n28hpop(n,size⁡(B)).(54)W_{\max}=3^{n2}8^h p_{\mathrm{op}}(n,\operatorname{size}(B)). \tag*{(54)}

Stop the current trial before exceeding either limit, including the cost of table construction and pair reporting. Retain every lattice vector already found as a candidate.

We analyze Algorithm 2 with exact random choices. Appendix § 11 implements these choices within fixed resource bounds, with total additional failure probability at most 2−n−102^{-n-10}.

Algorithm 2: Infinity-norm shortest vector search

Input: A nonsingular rational matrix BB, with L=BZnL = B\mathbb{Z}^n.

Output: A nonzero lattice vector vbestv_{\mathrm{best}}.

  1. Initialize vbestv_{\mathrm{best}} with a shortest column of BB in the infinity norm

  2. Compute tt, QQ, hh, NN from (30) and (51)

  3. foreach scale ℓ\ell in the multiplicative grid do

  4. &nbsp;&nbsp;&nbsp;&nbsp;Compute R0,…,RtR_0,\ldots,R_t, Fmax⁡F_{\max}, and P0P_0

  5. &nbsp;&nbsp;&nbsp;&nbsp;Run the bounded prime search. Skip this scale if it fails

  6. &nbsp;&nbsp;&nbsp;&nbsp;Choose uniform nonzero u∈Fpnu \in\mathbb{F}_p^n and form Γ=L+ZBu/p\Gamma= L + \mathbb{Z}Bu/p

  7. &nbsp;&nbsp;&nbsp;&nbsp;Apply Lemma 3.1 to Γ\Gamma

  8. &nbsp;&nbsp;&nbsp;&nbsp;if the sum of the infinity norms of the basis columns exceeds Fmax⁡F_{\max} then

  9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Skip this scale

  10. &nbsp;&nbsp;&nbsp;&nbsp;Choose G=δZnG = \delta\mathbb{Z}^n satisfying (31), and choose uniform z∈G/Γz \in G/\Gamma

  11. &nbsp;&nbsp;&nbsp;&nbsp;Run two independent calls X+←Build⁡(0,z)X_+ \leftarrow\operatorname{Build}(0,z) and X−←Build⁡(0,z)X_- \leftarrow\operatorname{Build}(0,z) with limits (53) and (54)

  12. &nbsp;&nbsp;&nbsp;&nbsp;if either call fails then

  13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Skip this scale

  14. &nbsp;&nbsp;&nbsp;&nbsp;Assign quotient labels and run the search of Proposition 8.3, with work limit Wmax⁡W_{\max}

  15. &nbsp;&nbsp;&nbsp;&nbsp;foreach reported pair (x,y)(x,y) do

  16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Set w=x−yw = x-y

  17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if w≠0w \ne0, B−1w∈ZnB^{-1}w \in\mathbb{Z}^n, and ∥w∥∞<∥vbest∥∞\lVert w\rVert_\infty< \lVert v_{\mathrm{best}}\rVert_\infty then

  18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Set vbest←wv_{\mathrm{best}} \leftarrow w

  19. return vbestv_{\mathrm{best}}

Success of the unrestricted construction

Fix a shortest vector vv and a correct scale. Conditional on a successful prime search, Theorem 5.2 gives

P[Gc]≤(t+2)21−3h=o(1).\mathbb{P}[\mathcal{G}^{c}] \le(t+2)2^{1-3h} = o(1).

On G\mathcal{G}, the basis check passes. By Lemma 8.1, the root shift has J≥ℓn/(4D)J \ge\ell^n/(4D) except with probability 4θ+4nη=o(1)4\theta+ 4n\eta= o(1).

For every such root shift, combine (25), (45), and (51):

A02J≥22h16(1+η)2n=:M∗.(55)A_0^2 J \ge\frac{2^{2h}}{16(1+\eta)^{2n}} =: M_*. \tag*{(55)}

Since M∗→∞M_* \to\infty, the moment bounds in (12) and (52), together with independence conditional on the common root coset, allow us to apply (44). The two trees therefore contain a pair with difference vv satisfying the binary condition with probability at least

e−2ε0(1+M∗−1/2)2=1−o(1).\frac{e^{-2\varepsilon_0}}{(1+M_*^{-1/2})^2} = 1-o(1).

The deterministic final search reports every such pair unless its resource limit is reached.

Bounding the probability of interruption

All expectations in this subsection fix a good Γ\Gamma and average the root shift and the private tree randomness. They refer to the construction without resource limits.

Every node has expected list size NN by (37). A union bound and Markov’s inequality give

P[some list exceeds Lmax⁡]≤Q2−2h=o(1).(56)\mathbb{P}[\text{some list exceeds }L_{\max}] \le Q2^{-2h} = o(1). \tag*{(56)}

After absorbing constants into pop⁡\operatorname{pop}, Proposition 7.1 and δ/R≤n−10\delta/R \le n^{-10} bound the expected work of each internal search by

pop⁡(n,size⁡(B)) 3n26h.\operatorname{pop}(n,\operatorname{size}(B))\,3^{n}2^{6h}.

For the final search, (49) and the parameter choices give

E[P]≤4⋅22h(3+4η(1+η)2)n≤4⋅3n22h.\mathbb{E}[P] \le4\cdot2^{2h}\left(\frac{3+4\eta}{(1+\eta)^2}\right)^n \le4\cdot3^n2^{2h}.

Also,

E[M] 2n/2=2N2n/2≤4⋅3n23h,\mathbb{E}[M]\,2^{n/2}=2N2^{n/2}\le4\cdot3^n2^{3h},

so Proposition 8.3 gives the same expected work bound for the final search. The work limit (54) leaves a factor of 22h2^{2h}, and Markov’s inequality followed by a union bound over the searches gives

P[some search reaches its work limit before a list limit]≤O(Q2−2h)=o(1).(57)\mathbb{P}[\text{some search reaches its work limit before a list limit}] \le O(Q2^{-2h})=o(1). \tag*{(57)}

These bounds do not condition on the presence of the target pair.

To compare the implementation with the unrestricted construction, give both the same random choices until the first limit is reached. They produce identical records before that point. Equations (56) and (57) bound the probability of this first interruption. Combined with the preceding correctness argument, one correct scale trial succeeds with probability 1−o(1)1-o(1).

Total time, space, and amplification

There are polynomially many scales and at most Q=poly⁡(n)Q=\operatorname{poly}(n) tree nodes per scale. Since h=O(log⁡n)h=O(\log n), leaf sampling and pair searches take O~(3n)\widetilde{O}(3^n) time under the stated resource limits. The 2n+o(n)poly⁡(size⁡(B))2^{n+o(n)}\operatorname{poly}(\operatorname{size}(B)) basis preprocessing cost per scale and the polynomial overhead of the remaining operations are absorbed in this bound.

Evaluate the trees in depth-first order. At most O(t)O(t) completed lists are waiting while another subtree is evaluated. The live lists use O(tN22h)O(tN2^{2h}) records. An internal search uses O(n3n)O(n3^n) table entries. The final search needs only O(n2n)O(n2^n) additional table entries, since large label groups are processed one at a time. Each record and each table count has polynomial encoding length. The total space is therefore O~(3n)\widetilde{O}(3^n).

Proof of Theorem 1.1. On a correct scale, the preceding bounds give total failure probability o(1)o(1), including the finite randomness loss. Thus a basic execution succeeds with probability at least 2/32/3 for all sufficiently large nn.

When the correct scale succeeds, its final search reports a shortest vector. Every update of vbestv_{\mathrm{best}} is an exactly checked nonzero vector of LL, so a later scale cannot replace it by an invalid shorter vector. This proves the success probability of a basic execution. The finitely many smaller dimensions can use the ℓ∞\ell_\infty-SVP algorithm of [8], with their costs included in the absolute constant.

Independent repetition O(nlog⁡n)O(n\log n) times, returning the shortest output, reduces the failure probability to 2−Ω(nlog⁡n)2^{-\Omega(n\log n)} and preserves the O~(3n)\widetilde{O}(3^n) time and space bounds.

The factor 3n3^n has two distinct geometric sources. Internally it comes from six compatible pairs of three coordinate classes. At the root it comes from the total weight 4R0−ℓ4R_0-\ell in the binary compatibility identity. The common list size makes both searches fit the same bound, while the counting moments allow the lists to be generated recursively.

Basis preprocessing

For completeness, we reproduce the proof of Lemma 3.1 from [GHH26, Appendix A.4], using the DBKZ theorem of [1 Theorem 2.3] and the exact Euclidean SVP algorithm of [MV13].

Proof of Lemma 3.1. Suppose n≥4n \ge4 and put k=⌊n/2⌋k = \lfloor n/2 \rfloor. Fix a prefix F=(b1,…,bi)F = (b_1,\ldots,b_i) of a basis (F,D)(F,D) of Λ\Lambda. Its orthogonal projection and remaining lattice are

π=I−F(FTF)−1FT,Λi=(πD)Zd=πΛ,d=n−i.\pi= I - F(F^{\mathsf{T}}F)^{-1}F^{\mathsf{T}}, \qquad\Lambda_i = (\pi D)\mathbb{Z}^d = \pi\Lambda, \qquad d = n-i.

with π=I\pi= I when i=0i = 0. Clear one common positive denominator in πD\pi D to obtain the integer input required by [1]. This preserves length ratios and coefficients, so an output with coefficient vector zz lifts to DzDz.

If d>kd > k, apply [1 Theorem 2.3] with block dimension kk, exact oracle factor δ=1\delta= 1, and slack ε=1\varepsilon= 1. It returns a nonzero projected vector vv with

∥v∥2≤2γk(d−1)/(2(k−1))det⁡(Λi)1/d≤2k(d−1)/(2(k−1))det⁡(Λi)1/d.\lVert v\rVert_2 \le2\gamma_k^{(d-1)/(2(k-1))}\det(\Lambda_i)^{1/d} \le2k^{(d-1)/(2(k-1))}\det(\Lambda_i)^{1/d}.

using polynomially many exact SVP calls of rank kk. Here γk≤k\gamma_k \le k is the Euclidean Hermite bound, and the determinant is taken within the span of Λi\Lambda_i. If d≤kd \le k, use exact SVP on Λi\Lambda_i.

Divide the output coefficient vector by the gcd of its coordinates to make it primitive. Extended-gcd operations give a unimodular completion. Lift this completion and size reduce the selected column against the fixed prefix. It becomes bi+1b_{i+1}, with ∥bi+1∗∥2≤∥v∥2\lVert b_{i+1}^* \rVert_2 \le\lVert v\rVert_2. The projections of nn independent vectors of length at most λn(2)(Λ)\lambda_n^{(2)}(\Lambda) span the remaining space. Selecting dd independent projections and applying Hadamard’s inequality gives

det⁡(Λi)1/d≤λd(2)(Λi)≤λn(2)(Λ).\det(\Lambda_i)^{1/d} \le\lambda_d^{(2)}(\Lambda_i) \le\lambda_n^{(2)}(\Lambda).

Later operations keep the prefix fixed, so its Gram–Schmidt vectors are preserved. Writing n=2k+rn = 2k+r, r∈{0,1}r \in\{0,1\}, and using k1/(k−1)≤2k^{1/(k-1)} \le2 for k≥2k \ge2, we obtain

max⁡i∥bi∗∥2≤2k(n−1)/(2(k−1))λn(2)(Λ)=2k k(r+1)/(2(k−1))λn(2)(Λ)≤2nλn(2)(Λ).\max_i \lVert b_i^* \rVert_2 \le2k^{(n-1)/(2(k-1))}\lambda_n^{(2)}(\Lambda) = 2k\,k^{(r+1)/(2(k-1))}\lambda_n^{(2)}(\Lambda) \le2n\lambda_n^{(2)}(\Lambda).

For n≤3n \le3, exact SVP at every suffix gives the stronger factor one. Thus Ared(n)=2(n+1)A_{\mathrm{red}}(n) = 2(n+1) works in every dimension.

For the encoding bounds, begin with an LLL-reduced input basis. After each selection, LLL reduce the projected suffix, lift its integer column operations, and size reduce against earlier columns, as in [MV13, Section 2]. An LLL-reduced suffix has Gram–Schmidt lengths at most 2n/2λn(2)(Λ)2^{n/2}\lambda_n^{(2)}(\Lambda). Consequently every current basis column has length at most 1+n/4max⁡{2n,2n/2}λn(2)(Λ)\sqrt{1+n/4\max\{2n,2^{n/2}\}}\lambda_n^{(2)}(\Lambda). Its denominator divides the original common denominator, and λn(2)(Λ)\lambda_n^{(2)}(\Lambda) is at most the longest input column. These bounds give polynomial encoding length at the start of each round. Gram inverse and cofactor formulas give the same bound for projections and integer coordinates. Each reduction, primitive completion, and lift has polynomial intermediate size.

There are nn rounds and polynomially many exact SVP calls of rank at most kk. The algorithm of [MV13] uses 4k+o(k)4^{k+o(k)} time and 2k+o(k)2^{k+o(k)} space per call, with polynomial input overhead. The overall time and workspace are therefore bounded by 2n+o(n)poly⁡(size⁡(B))2^{n+o(n)}\operatorname{poly}(\operatorname{size}(B)), including the fixed small dimensions. □\square

Finite arithmetic and random choices

We record the finite representations used by the algorithm and the coupling that makes every execution obey a deterministic resource bound.

Constructing the superlattice and its quotient

Lift u∈Fpnu \in\mathbb{F}_p^n to an integer vector. A Hermite basis of

K=pZn+ZuK = p\mathbb{Z}^n + \mathbb{Z}u

is obtained from [pI∣u][pI \mid u] and gives a rational basis of Γ\Gamma after multiplication by B/pB/p.

For a terminal entry x=z+gx = z + g, let

ax=pB−1g∈Zna_x = pB^{-1}g \in\mathbb{Z}^n

Modulo pp, this vector lies in the span of uu. Choose an index jj with uj≠0u_j \ne0 and represent the label by

lab⁡(x)=(ax)juj−1(modp).(58)\operatorname{lab}(x) = (a_x)_j u_j^{-1} \pmod p . \tag*{(58)}

This scalar represents the class g+Lg + L, so equal labels are equivalent to x−y∈Lx-y \in L and can be computed by exact rational and finite field arithmetic.

Choosing the grid and sampling its quotient

Choose the mesh in (31) from a common denominator for B/pB/p, ℓ/2\ell/2, and Rj/6R_j/6, then subdivide until δ/ℓ≤n−10\delta/\ell\le n^{-10}. Its encoding length is polynomial because there are O(log⁡n)O(\log n) radii of polynomial encoding length. The inclusion p−1L⊆Gp^{-1}L \subseteq G makes this grid valid for every possible Γ\Gamma at the given scale and prime.

Let HH be an upper triangular integer Hermite basis of Γ/δ\Gamma/\delta. If its positive diagonal entries are h1,…,hnh_1,\ldots,h_n, the integer box

{0,…,h1−1}×⋯×{0,…,hn−1}\{0,\ldots,h_1-1\} \times\cdots\times\{0,\ldots,h_n-1\}

is the standard set of representatives of Zn/HZn\mathbb{Z}^n/H\mathbb{Z}^n. Independent uniform coordinates in these intervals, multiplied by δ\delta, therefore sample G/ΓG/\Gamma in polynomial time.

All node offsets can be reduced to these representatives after each subtraction. This changes neither their cosets nor the midpoint identities.

Bounded randomness and bit complexity

All random choices reduce to rejection sampling of uniform integers, with acceptance probability at least 1/21/2 per attempt. The resource limits give a deterministic bound RrandR_{\mathrm{rand}} on the number of calls, with log⁡Rrand\log R_{\mathrm{rand}} polynomial in the input length. Truncate each call after

s=⌈log⁡2Rrand⌉+n+20s = \left\lceil\log_2 R_{\mathrm{rand}}\right\rceil+ n + 20

attempts and fail the trial if none succeeds. Coupling to the exact choices gives a total disagreement probability at most

Rrand2−s≤2−n−20R_{\mathrm{rand}}2^{-s} \le2^{-n-20}

This includes quotient and field samples, prime candidates, and rational retention coins.

Each record stores a vector, a quotient label, and an identifier local to its node. Vector coordinates lie in δZ\delta\mathbb{Z} and have absolute value at most RtR_t. The grid, radii, quotient labels, identifiers, and table counts all have polynomial encoding length under the parameter and resource bounds. Exact membership tests use B−1w∈ZnB^{-1}w \in\mathbb{Z}^n, and all arithmetic and comparisons have polynomial bit cost, as included in popp_{\mathrm{op}}.

AI methodology

Building on Gaussian difference dynamics (GDD) [GHH26], the author used GPT-6-astra to assist with extending the framework to the infinity norm, including the algorithm design and mathematical analysis in § 4 to § 9. The author then used GPT-6.1-sol and GPT-6-astra to help draft the manuscript. The author thoroughly checked and revised the entire paper and remains responsible for all mathematical claims, proofs, and references.

References

  1. [1]Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, and Noah Stephens-Davidowitz. Slide reduction, revisited—filling the gaps in SVP approximation. In Advances in Cryptology—CRYPTO, pages 274–295, 2020. https://doi.org/10.1007/978-3-030-56880-1_10.
  2. [2]Divesh Aggarwal and Priyanka Mukhopadhyay. Improved algorithms for the shortest vector problem and the closest vector problem in the infinity norm. In Proceedings of ISAAC, volume 123 of LIPIcs, pages 35:1–35:13, 2018. https://doi.org/10.4230/LIPIcs.ISAAC.2018.35.
  3. [3]Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of Mathematics, 160(2):781–793, 2004. https://doi.org/10.4007/annals.2004.160.781.
  4. [4]Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proceedings of STOC, pages 601–610, 2001. https://doi.org/10.1145/380752.380857.
  5. [5]Wojciech Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296(1):625–635, 1993. https://doi.org/10.1007/BF01445125.
  6. [6]Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Proceedings of SODA, pages 10–24, 2016. https://doi.org/10.1137/1.9781611974331.ch2.
  7. [7]Dan Boneh and Ramarathnam Venkatesan. Hardness of computing the most significant bits of secret keys in Diffie–Hellman and related schemes. In Advances in Cryptology—CRYPTO, pages 129–142, 1996. https://doi.org/10.1007/3-540-68697-5_11.
  8. [8]Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative lattice algorithms in any norm via M-ellipsoid coverings. In Proceedings of FOCS, pages 580–589, 2011. https://doi.org/10.1109/FOCS.2011.31.
  9. [9]Yiming Gao, Yansong Feng, and Honggang Hu. Solving the shortest vector problem in 2^{0.7314n+o(n)} time via discrete Gaussian sampling on superlattices. Cryptology ePrint Archive, Paper 2026/1587, 2026. https://eprint.iacr.org/2026/1587.

Paper details

vlnc:W_4v7vmujw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents