WorksComputer Science
norm SVP in
Abstract
We give a classical randomized algorithm for the Shortest Vector Problem in the infinity norm in time and space, improving the previous bound of . 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 be a full-rank lattice. The Shortest Vector Problem in the infinity norm asks for a nonzero vector satisfying
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 time and space. Mukhopadhyay [Muk21] subsequently improved both bounds to through a finer subdivision of the cube.
We give a classical randomized algorithm for exact -SVP in time and space, reducing the exponent from to . 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, means .
Our results
Theorem 1.1 (Main theorem). There is a classical randomized algorithm that, given a nonsingular rational basis of a full-rank lattice , returns a nonzero vector of and, with probability at least , returns a vector of norm . Every execution uses
The success probability can be increased to 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 -dimensional -SVP instance gives the following consequence.
Corollary 1.2. Given and an integer , there is a randomized algorithm that, with probability at least , finds a vector satisfying , or correctly reports that no such vector exists. It uses time and space, suppressing polynomial factors in the binary input length.
For every , this is exponentially faster than the standard meet-in-the-middle bound , improving the threshold 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 norm, with a general SVP bound of 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 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 for the analysis, and write . There are two tasks: make appear as a difference between two lists, and find that difference within the claimed time. We first explain the construction as though 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
The two boxes have different roles. contains an input list, while is the allowed midpoint region. Choose a fixed . From two lists in , keep pairs satisfying
For every allowed , the complete set of possible midpoints is exactly . Conversely, and imply . The volume of the midpoint set is therefore , independently of . This is the reason for the second condition in (1). Restricting only would give a midpoint region that shrinks as a coordinate of approaches the boundary. The additional midpoint condition removes that variation. In the continuous model, the output has constant density on .
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 and a uniform translate , let
We measure this variation by
We work in a random superlattice , of determinant , chosen so that these relative variances are small at all widths used by the construction.
The main geometric estimate is
Its proof is a weighted packing argument for cubes. The constant can already be seen in one dimension. An interval of length , translated uniformly modulo , contains one point with probability and two points with probability . Its second moment divided by the square of its mean is . Products of these intervals give .
Passing to a random superlattice of prime index reduces the expected relative variance to at most , plus an error term controlled in § 5. We choose
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 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 at each point of a common translate inside . If its average size is , then
Every midpoint in represents through the endpoints and . The number of available midpoints is about . Thus the expected number of representations in the two lists is
This suggests
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 . We thin each eligible pair with probability
Then , so the same reference list size is maintained throughout the tree. We choose a fixed , which ensures while shortening the radius by a constant factor.
The construction starts in a cube whose radius is polynomially larger than , where we can sample the initial lists directly with the required counting moments. The tree therefore has depth 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
Divide each absolute coordinate into three classes, according to the intervals , , and . If the class numbers are , every eligible pair satisfies
There are six compatible class pairs out of nine in each coordinate. A table indexed by reports the corresponding pairs without visiting empty combinations. The candidate count has scale
These tables also account for the 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 . This keeps every representation of a shortest vector whose midpoint lies in : since , at least one of and lies in that inner interval. Each point has a binary class vector and a label modulo , so equal labels recognize differences in .
To bound the number of reports, we express binary compatibility by inclusion and exclusion as a weighted count involving the inner cube . Every translate of this half-open cube contains at most one point of , so the lattice sum is bounded by the total weight, . Thus, if counts pairs satisfying both the binary condition and the equal-label condition, then
To find these pairs, we check small label groups directly and use a binary prefix table for large groups. Splitting at group size gives the deterministic bound
where is the total input size. Since is at most , this cost is also .
| Part of the algorithm | Quantity before substitution | Exponential factor |
| List generation | ||
| Internal candidate pairs | ||
| Final label-group searches | ||
| Final pair reports |
Table 1. The cost balance. Polynomial factors are omitted in this overview.
Preliminaries
We use for the natural logarithm and for the binary logarithm. For a real number , write . 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 , let
We write for the th successive minimum in the norm. Unless a different lattice is specified, denotes . The inequalities
will be used for preprocessing only.
Minkowski’s second theorem, applied to the cube, gives [Henk02]
In particular, . We also use the Euclidean transference bound [5]
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 . From a rational basis of a rank- lattice , one can compute a size-reduced basis such that
The time and workspace are . 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 are the Gram–Schmidt vectors. For the computed basis matrix , size reduction gives
The coarse factor is convenient and sufficient.
Boxes and finite shifts
We use the half-open boxes
Thus has radius and has side length . 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 , choose a rational such that
Then has elements, where . A uniform shift satisfies
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 , let be the number of entries equal to . Define
The second quantity counts ordered pairs of distinct entries. In particular, .
At a node with radius and prescribed coset , the reference is
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, independent draws and 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 and , define
Here , with . By the following lemma, is the relative variance of the translated box count used in § 2.
Lemma 4.1. Let be uniform modulo , and put
Then
and
Proof. The periodization of is bounded on a fundamental domain. It is therefore square integrable. Its mean is , and its Fourier coefficient at has absolute value
Parseval’s identity proves (14), including convergence of the nonnegative series. Alternatively, expand before integrating over a fundamental domain. The two lattice points differ by some , and the intersection of the corresponding boxes has volume . Thus
Combining the two expressions for the second moment gives (15).
From a one-dimensional weight to a cube bound
The coordinate projections of an -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 be real numbers with nonnegative weights . There are nonnegative weights on the intervals that cover each point to total weight at least . Their total weight equals the maximum weight of a subset whose points are pairwise at distance at least one.
Proof. Let be the last index with , or zero if no such index exists. Define
The first option omits . The second selects and uses an optimal subset among the first points. Hence is the maximum weight of a separated subset.
Give weight . The intervals containing are precisely those with , so their total weight is
The total interval weight is .
For , put
Lemma 4.3. For every finite set whose distinct points are at distance at least one,
Writing with and , one has
Proof. Discard points with zero weight. If points remain, order them increasingly. Pair the smallest with the largest, the second smallest with the second largest, and so on. Their separation gives
Consequently their total weight is at most . For even , this expression is the average of its values at the two neighboring odd integers. For , it equals . Maximizing over gives . Summing the terms at gives the displayed formula.
Lemma 4.4 (Weighted packing for cubes). If is -separated by at least one, then
In particular, with ,
for every .
Proof. Only finitely many points contribute to the sum. Apply Lemma 4.2 to the distinct values in each coordinate projection, with weight . The cover’s total weight equals that of the heaviest separated subset of the projection, which is at most by Lemma 4.3.
Multiply the coordinate covers. For each point, the product of its covering weights dominates . Sum first over points and then over product boxes. Every half-open box has side length one and contains at most one point of , so it is counted at most once. The total product weight is at most , proving (17).
To prove (18), set and apply (17) to . Equation (15) gives
For , the ratio is . For , it is at most
since is equivalent to .
For and , equality holds in (18). This example explains why the factor 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 and . Fix . For uniform , let
Then
Proof. Every interval of length on the translate contains exactly points. Averaging the coset therefore gives
In the square of the count, the difference between two midpoints belongs to . For , each coordinate intersection contains exactly points. Its endpoints differ by integer multiples of , even when is a half-grid point. Thus
Use (15) for the second identity. The two second moments are the same for all , 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 satisfying
The algorithm tries a polynomial number of scales. This section analyzes a scale satisfying (22). Let be an integer to be specified later, and put
Choose a prime with . If , choose a uniform nonzero and define
Then
The index is always , so is fixed before is drawn.
Reducing box variance through the dual lattice
The dual of (24) is
A vector outside survives with probability
while every vector in survives. Consequently,
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 by Lemma 4.4. The second term is the variance associated with the fine lattice . We bound it by counting fundamental cells near the boundary of a box.
Lemma 5.1. For all sufficiently large , the parameters above satisfy
The threshold is uniform over the input lattice, the correct scale, and .
Proof. By (6),
Apply Lemma 3.1 and (8) to , then divide the resulting basis by . A fundamental cell for is contained in , where, with ,
We use this cell only for analysis.
Let . For every translate of a box of side , the union of the cells anchored at its lattice points is contained in the box expanded by in each direction. Conversely, it covers the box contracted by in each direction. Therefore
For , the relative deviation from the mean is at most . The variance identity in Lemma 4.1 gives
The last expression is at most for all sufficiently large .
Theorem 5.2 (Small box variance on a random superlattice). Fix prescribed widths . For all sufficiently large , the construction (24) satisfies
except with probability at most .
Proof. Equations (26) and (27), together with Lemma 5.1, give
Apply Markov’s inequality at each prescribed width and take a union bound.
Choosing the initial scale
Call the event in Theorem 5.2 . We include among the prescribed widths. On , there is no nonzero with . Indeed, the elementary inequality gives
contradicting . By (7),
After Lemma 3.1, the fundamental cell has coordinate radius at most
This bound can be checked from the computed basis by summing the infinity norms of its columns.
Let be the least nonnegative integer such that
Since is a fixed polynomial, . Both and the ratios depend only on . The widths supplied to Theorem 5.2 are , so they are fixed before the random superlattice is drawn.
Building the lists
Fix and its preprocessed basis. We construct a list at radius in any prescribed coset . The construction is a binary tree with leaves at radius . Each subtree uses private samples, private shifts, and private retention coins.
Choose one rational grid satisfying
A common denominator followed by integer subdivision gives such a grid with polynomial encoding length. The large size of the quotient 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 be the fundamental cell and use the bound . Set
Draw uniformly from . For the prescribed coset , compute
Then . Keep the proposal only when .
Lemma 6.1. For any positive integer , let
Make independent proposals as in (32). Independently keep each successful proposal with probability . For every fixed coset , the resulting list satisfies
It uses proposals, each of polynomial cost.
Proof. For every allowed output , its complete cell lies in . That cell contains exactly grid points, one for each coset of in . Hence a proposal equals with probability , independently of and .
The first moment is . Distinct retained entries come from distinct proposals, so
Finally, (30) gives
Thus .
One shortening step
Suppose a node is to produce a list in at radius . Choose a uniform . The two child cosets are
Generate the two child lists at radius with independent private randomness. For each ordered pair of child entries, keep the difference with probability
Each distinct pair of child identifiers uses an independent coin and creates at most one output entry. Fix . An admissible pair with difference is uniquely determined by its midpoint. Its midpoint set is
Every such midpoint gives two endpoints in the child boxes. Thus the number of representations is exactly the variable 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 and error , uniformly over their prescribed cosets. Assume they are independent after the cosets in (33) are fixed, and that . The output satisfies
and
The bounds hold for every fixed output coset and all .
Proof. Fix . The first moment at is . Averaging gives
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
For a shared left entry at , the right values are fixed as and . The number of possible triples is at most . This contribution is therefore at most
The same bound holds for a shared right entry. This also covers , 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 . Since
the result is (35).
The complete tree
Set . A call produces a list in . At , it invokes the leaf sampler. Otherwise, it uses (33), calls and independently, and applies (34) at input radius . Starting with , Lemma 6.2 gives
The factor counts the effect of the entire tree. It remains polynomial because .
The first moment stays exact throughout the construction. If a node’s coset is uniform in , then (10) gives
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()
Input: Level , coset representative , fixed , grid and radii. Output: A list in , or fail.
if then
return the list of Lemma 6.1
Choose uniformly in
and , using independent randomness
if either call failed then
return fail
Initialize an empty output list
Use the ternary search of § 7 on
foreach reported pair of entries do
if and then
With probability , append a new entry with value
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 , define
For an eligible pair,
so . Thus, for each left entry , we need to report all right entries whose class vectors satisfy 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 , where is either two or three. Given upper bounds , a query reports all records whose class vector satisfies in every coordinate.
Let be the histogram of class vectors, with a list of record identifiers at each occupied vector. For every , store a table
Each table has entries. It is obtained from by prefix sums in the last coordinates. All tables therefore take arithmetic operations and storage, in addition to the records.
To answer a query, start with the empty prefix. At depth , try the at most allowed values for the next coordinate and consult . Descend only when the count is positive. At depth , 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 charges per record, each with at most child tests, so a query costs
For the internal search, build the ternary tables on the right list and query with for each left entry . 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 and an internal call whose prescribed output coset is uniform in . If the two child lists have the exact first moments in (12), then their expected number of ternary candidate pairs is
Including construction of the tables, the expected search work is at most
Proof. Write the parent coset as . For independent uniform , the map
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 has expected count
Let , which is divisible by six. The three one-dimensional class sizes are , , and . Summing the six combinations with class sum at most two gives the fraction
The free grid has endpoint pairs, which proves (40) after multiplication by the expected count above. The table construction and query bounds, together with , 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 and are independent conditional on and . The last search uses the original lattice both to recognize valid differences and to bound its work.
Quotient labels and a binary condition
For with , give the entry label
Then
A label is represented by one field element, as detailed in Appendix § 11.
Let
For each endpoint, store the binary class vector
The final search reports exactly the pairs of entries satisfying
Thus every coordinate has at least one endpoint in the inner interval . Each reported nonzero difference is tested for membership in and compared with the current best vector.
A shortest vector has many compatible representations
Fix a shortest vector . The full midpoint box gives endpoints
in . Let count its midpoints in , and let count those also satisfying the binary condition in (42).
Lemma 8.1. For every , a uniform satisfies
except with probability at most .
Proof. Put . By Lemma 4.5,
Chebyshev’s inequality gives except with probability .
Consider one coordinate. If , every midpoint in puts at least one endpoint in . If , the excluded midpoints form a central interval of length . The endpoints of this interval align with the midpoint grid because and .
A union bound over coordinates therefore shows that the expected number of deleted midpoints is at most . Markov’s inequality bounds the probability of deleting more than by . On the complementary events, (43) holds.
To turn these midpoint locations into actual pairs, fix a root coset with and let count pairs of entries with difference and a compatible midpoint. The two root lists are independent with the moments in (12), so . Each endpoint determines the other uniquely. Thus two different midpoint locations have different endpoint values on both sides, and contribute at most to the second moment. At a repeated location, the ordinary second moment on each side is at most . Consequently,
and the second-moment inequality gives
where the last inequality uses .
On (43), the expected number of these pairs satisfies
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
For , let be times the number of compatible one-dimensional endpoint pairs at displacement :
The key is to express this count using the inner interval and a nonnegative weight, so that the separation of can bound the lattice sum directly. Inclusion and exclusion gives
The two cross terms, obtained by putting the first or the second endpoint in , agree by reflection about , the common center of and .
Lemma 8.2 (Final report bound). If , then
For the two root lists generated in a uniform common coset of a fixed , the number of pairs satisfying (42) obeys
Proof. Apply (47) in every coordinate, then set . All summands are nonnegative, so
The inner sum is at most one. Two points in the half-open cube differ by less than in every coordinate, while a nonzero vector of has infinity norm at least . Therefore
For the work estimate, first fix the common coset . The two root lists use independent private randomness, and their first moments are exactly . If , then membership of in already implies membership of . Averaging therefore contributes one factor . For a fixed , the number of compatible free grid pairs is . Thus
which proves (49). The term is included throughout.
To see the balance already at this point, put . Our parameters give , so the report bound is
The last inequality is . 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 entries in total, and let be the number of their pairs satisfying (42). There is a deterministic algorithm that reports every such pair of entries once, in time
and space .
Proof. Sort the entries by label. Put , and let be the total size of the two sides in label group .
If , check all cross pairs in that group. The total cost of these groups is at most .
There are at most groups with . In each such group, build the binary prefix tables of § 7.2 on the right side and query with bounds for each left entry . The total table and query cost is
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 , 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
Here exceeds the total number of nodes in the two trees. Since ,
Since , the retention probability in (34) satisfies
On every good superlattice, (36) gives
Set
Then . We try every scale . This gives
scales of polynomial encoding length, at least one of which satisfies (22).
At each scale, set and test independent uniform candidates in by deterministic primality testing [3]. Standard prime density bounds make the failure probability at most , and every prime returned on a correct scale satisfies .
A trial with resource limits
Choose the list limit
Let bound the polynomial overhead of the arithmetic and search operations, and set the work limit for each pair search to
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 .
Algorithm 2: Infinity-norm shortest vector search
Input: A nonsingular rational matrix , with .
Output: A nonzero lattice vector .
Initialize with a shortest column of in the infinity norm
foreach scale in the multiplicative grid do
Compute , , and
Run the bounded prime search. Skip this scale if it fails
Choose uniform nonzero and form
Apply Lemma 3.1 to
if the sum of the infinity norms of the basis columns exceeds then
Skip this scale
Choose satisfying (31), and choose uniform
Run two independent calls and with limits (53) and (54)
if either call fails then
Skip this scale
Assign quotient labels and run the search of Proposition 8.3, with work limit
foreach reported pair do
Set
if , , and then
Set
return
Success of the unrestricted construction
Fix a shortest vector and a correct scale. Conditional on a successful prime search, Theorem 5.2 gives
On , the basis check passes. By Lemma 8.1, the root shift has except with probability .
For every such root shift, combine (25), (45), and (51):
Since , 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 satisfying the binary condition with probability at least
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 and average the root shift and the private tree randomness. They refer to the construction without resource limits.
Every node has expected list size by (37). A union bound and Markov’s inequality give
After absorbing constants into , Proposition 7.1 and bound the expected work of each internal search by
For the final search, (49) and the parameter choices give
Also,
so Proposition 8.3 gives the same expected work bound for the final search. The work limit (54) leaves a factor of , and Markov’s inequality followed by a union bound over the searches gives
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 .
Total time, space, and amplification
There are polynomially many scales and at most tree nodes per scale. Since , leaf sampling and pair searches take time under the stated resource limits. The 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 completed lists are waiting while another subtree is evaluated. The live lists use records. An internal search uses table entries. The final search needs only 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 .
Proof of Theorem 1.1. On a correct scale, the preceding bounds give total failure probability , including the finite randomness loss. Thus a basic execution succeeds with probability at least for all sufficiently large .
When the correct scale succeeds, its final search reports a shortest vector. Every update of is an exactly checked nonzero vector of , 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 -SVP algorithm of [8], with their costs included in the absolute constant.
Independent repetition times, returning the shortest output, reduces the failure probability to and preserves the time and space bounds.
The factor 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 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 and put . Fix a prefix of a basis of . Its orthogonal projection and remaining lattice are
with when . Clear one common positive denominator in to obtain the integer input required by [1]. This preserves length ratios and coefficients, so an output with coefficient vector lifts to .
If , apply [1 Theorem 2.3] with block dimension , exact oracle factor , and slack . It returns a nonzero projected vector with
using polynomially many exact SVP calls of rank . Here is the Euclidean Hermite bound, and the determinant is taken within the span of . If , use exact SVP on .
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 , with . The projections of independent vectors of length at most span the remaining space. Selecting independent projections and applying Hadamard’s inequality gives
Later operations keep the prefix fixed, so its Gram–Schmidt vectors are preserved. Writing , , and using for , we obtain
For , exact SVP at every suffix gives the stronger factor one. Thus 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 . Consequently every current basis column has length at most . Its denominator divides the original common denominator, and 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 rounds and polynomially many exact SVP calls of rank at most . The algorithm of [MV13] uses time and space per call, with polynomial input overhead. The overall time and workspace are therefore bounded by , including the fixed small dimensions.
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 to an integer vector. A Hermite basis of
is obtained from and gives a rational basis of after multiplication by .
For a terminal entry , let
Modulo , this vector lies in the span of . Choose an index with and represent the label by
This scalar represents the class , so equal labels are equivalent to 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 , , and , then subdivide until . Its encoding length is polynomial because there are radii of polynomial encoding length. The inclusion makes this grid valid for every possible at the given scale and prime.
Let be an upper triangular integer Hermite basis of . If its positive diagonal entries are , the integer box
is the standard set of representatives of . Independent uniform coordinates in these intervals, multiplied by , therefore sample 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 per attempt. The resource limits give a deterministic bound on the number of calls, with polynomial in the input length. Truncate each call after
attempts and fail the trial if none succeeds. Coupling to the exact choices gives a total disagreement probability at most
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 and have absolute value at most . The grid, radii, quotient labels, identifiers, and table counts all have polynomial encoding length under the parameter and resource bounds. Exact membership tests use , and all arithmetic and comparisons have polynomial bit cost, as included in .
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]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]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]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]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]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]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]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]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]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.