arXiv CSopen access

Solving the Shortest Vector Problem in time $2^{0.6039n}$ Time via Mid-point Hessian

Solving the Shortest Vector Problem in time 20.6039n Time via Mid-point Hessian Minki Hhan KAIST, Daejeon, Korea [email protected]

arXiv:2608.02478v1 [cs.DS] 3 Aug 2026

Abstract We present randomized algorithms for the shortest vector problem (SVP). For the n-dimensional lattice L, our algorithms solve SVP in time 20.6039n+o(n) classically and 20.5411n+o(n) quantumly and space 20.5n+o(n) , improving the previous best algorithm running in 2n+o(n) time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC’15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector v ∈ L, the Hessian at v/2 has the eigenvector close to v, which can be used to recover v using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo L, the candidate midpoints are indexed by the parity classes in L/2L. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.

AI use disclosure. Most results of this paper are discovered with the assistance of ChatGPT 5.5 Pro and ChatGPT 5.6 Sol Ultra. While the author suggested several directions and optimizations, all the technical details are discovered by AI, and verified by the author. The manuscript is written by the author based on the initial draft generated by AI. The author takes full responsibility for the content. All errors in the manuscript are likely due to the author’s human errors. 1

Contents 1 Introduction 1.1 Technical overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3

2 Preliminaries 2.1 Lattices and decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Discrete Gaussians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Useful inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 6 7 8

3 Recovering Shortest Vector from Hessian 3.1 Scale and Gaussian mass bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 The periodic Gaussian and the shortest parity class . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Estimating the Hessians and recovering a shortest vector . . . . . . . . . . . . . . . . . . . . .

9 9 10 11

4 Batch Hessian Estimation

13

5 Random Sublattice Coset Hessian 14 5.1 Gaussian and Hessian sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.2 A random coset Hessian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.3 Estimating the coset Hessian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.4 Coset Hessians and shortest vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.5 The affine-coset algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6 Importance Sampling on an Affine Lattice Coset 20 6.1 Lattice points in a shortest parity class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6.2 Sampling (wider) discrete Gaussian from an affine lattice coset . . . . . . . . . . . . . . . . . 24 6.3 Estimating the Hessian by importance sampling . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6.4 Recovering a shortest vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.5 The importance-sampling algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.6 Reducing the space by sparsification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6.7 Space-efficient implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6.8 Quantum algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2

1

Introduction

An n-dimensional lattice L = L(b1 , . . . , bn ) is the set of all integer combinations of linearly independent vectors b1 , . . . , bk ∈ Rn . For the sake of simplicity, we only consider the full rank lattice satisfies k = n. The (search) shortest vector problem (SVP) asks to find a nonzero vector of minimum norm, given a basis of L. There are two faces of lattice problems including SVP. Approximate variants of SVP have long served as algorithmic tools in computational number theory, integer programming, and cryptanalysis [24, 20, 25, 36, 23]. On the other hand, the exact problem and its small approximation factor version are known to be hard [6, 10, 3, 21, 18]. Given the close relation between the lattice problems and many recent cryptographic primitives [34, 11, 26, 33, 7, 16], lattice problems have become one of the most promising foundations for post-quantum cryptography. SVP remains a fundamental benchmark for our understanding of the complexity of lattice problems. Researchers have discovered various worst-case algorithms [17, 27, 8, 20, 29, 32, 28, 12] and heuristic or average-case algorithms [29, 31, 9]. To date, however, the best provable worst-case running time was 2n+o(n) , with the same space complexity [2] using a new efficient discrete Gaussian sampling algorithm. Later, [1] gave several time-space tradeoffs and quantum speedup, including 21.669n+o(n) time and 2n/2+o(n) space and 20.950n+o(n) and 20.835n+o(n) quantum time without and with quantum random access memory (QRAM), respectively. We give a new class of worst-case algorithms for SVP, significantly improving the previous classical and quantum algorithms [2, 1]. Our main results are summarized as follows. Theorem 1.1. There are randomized classical and quantum algorithms that solve Search-SVP with probability at least 2/3 in expected time 20.603867n+o(n) classically and 20.541051n+o(n) quantumly and space 20.5n+o(n) , up to factors polynomial in the input length. The quantum algorithm requires a QRAM of size 20.36036n+o(n) . Remark 1.2 (Concurrent works). During the preparation of this manuscript, OpenAI announced an improvement of the sphere packing bound [30]. Plugging that parameter, the time complexity of our algorithm is reduced to 20.60221n+o(n) classically and 20.53925n+o(n) quantumly, according to ChatGPT 5.6 Sol’s calculation. We did not present these complexities because the result of OpenAI and the numerical calculation for those parameters are not verified (by the author, at least). We also noticed the concurrent works [15, 22] right β2

before publicizing the manuscript, which obtains 2(0.5+ 4e ln 2 )n+o(n) ≈ 20.7134n+o(n) time and 20.5n+o(n) space algorithm for β = 20.4014... , matching Theorem 5.8, with a completely different approach.

1.1

Technical overview

Let L be a n-dimensional full-rank lattice with basis B and s > 0 be a width parameter.  Its dual 2 lattice L∗ = {y : ⟨y, x⟩ ∈ Z for every x ∈ L} has the basis B −T . Define ρs (x) := exp −π ∥x∥ and let s2 P ρs (x) ρs (A) := x∈A ρs (x). We define the (centered) discrete Gaussian distribution DL,s (x) := ρs (L) . The periodic Gaussian function [4] Fs : Rn → R is defined by Fs (z) :=

h i ρs (L + z) = EX∼DL∗ ,1/s e2πi⟨X,z⟩ ρs (L)

where the last equality is due to the Poisson summation formula. It is clear that Fs is L-periodic, i.e., Fs (z) = Fs (z + v) for v ∈ L. At the midpoint, the Hessian points the way. which also has two representations ∇2 Fs (z) +

Our algorithm starts with studying its Hessian [35, 13],

2 2 2π 4π 2 X Fs (z)In = 4 (y − z)(y − z)T e−π∥y−z∥ /s 2 s s ρs (L)

y∈L

3

(1)

by differentiating the first representation, and by differentiating the second representation i h ∇2 Fs (z) = −4π 2 EX∼DL∗ ,1/s XX T e2πi⟨X,z⟩ .

(2)

From these two representations, we observe the following two properties. First, let v be a shortest vector with ∥v∥ = λ and evaluate ∇2 Fs (v/2) in Eq. (1), we can see that   T 2 X 2 2 2 2 4π  vv e−πλ /4s + ∇2 Fs (v/2) + aI = 4 (y − v/2)(y − v/2)T e−π∥y−v/2∥ /s  s ρs (L) 2 y∈L\{0,v}

where a := 2πFs (v/2)/s2 which is unimportant in the spectral analysis. Noting that ∥y − v/2∥ for y = ̸ 0, v is much larger than ∥v/2∥ = λ/2, we can expect that ∇2 Fs (v/2) + aI is close to a multiple of vv T . For appropriately chosen s, this intuition can be formalized by the following statement for the normalized eigenvector ṽ of ∇2 Fs (v/2) corresponding to the largest eigenvalue: ṽ is inverse polynomially close to v/∥v∥. Then, given ṽ, we guess λ (which only takes polynomial iterations) and solve the bounded distance decoding (BDD) problem for the target vector λṽ. This BDD step can be relatively quick, thanks to the preprocessing BDD algorithm in [1], which solves each BDD instance with inverse polynomial distances in time 2o(n) after 20.5n+o(n) time preprocessing. One Hessian is enough if we know where to look. This gives our very first result (Theorem 3.7) with time complexity 21.463n+o(n) and space complexity 20.5n+o(n) . Suppose that for a shortest vector v, we know a representative w of the parity class v + 2L. We compute the eigenvector w̃ of ∇2 Fs (w/2), and solve the BDD problem for it using (preprocessing) BDD. But, how to compute ∇2 Fs (w/2)? Here the second representation Eq. (2) comes in. We use the algorithm in [2] that samples N = 2n/2 elements, say X1 , ..., XN , from the discrete Gaussian distribution in time 2n/2+o(n) on L∗ . Then, given w/2, we use the estimator N −4π 2 X 2 F (w/2) = \ ∇ Xi XiT e2πi⟨Xi ,w/2⟩ . s N i=1 Concentration inequalities and results from lattice literature show that about 22t0 n+o(n) samples for t0 = 20.802 /4e ln 2 = 0.2314 suffice to accurately estimate the actual ∇2 Fs (w/2) as well as its eigenvectors. This leads to the time complexity |L/2L| · 22t0 n = 21.463n+o(n) by enumerating all the parity class in L/2L. The 2n/2+o(n) space is required in the discrete Gaussian sampling. Walsh-Hadamard looks everywhere at once. The time can be reduced further. Write w = Bu. Since B T X ∈ Zn , T T T T e2πi⟨X,Bu/2⟩ = eπiu B X = (−1)u (B X mod 2) . 2 F (Bu/2) simultaneously \ With some work, the fast Walsh-Hadamard transform can be applied to compute ∇ s n+o(n) for different u’s. Carefully choosing the coordinates leads to 2 time algorithm in Theorem 4.2 while preserving 20.5n+o(n) space.

A random coset narrows the view. The bottleneck 2n of the above strategy is the size of the search space L/2L. Let X ∈ L∗ . Choose a random invertible linear map P ∈ GLn (F2 ) and divide P (B T X mod 2) ∈ Fn2 into h fixed coordinates and ℓ = n − h remaining coordinates. We then choose a random value j ∈ Fh2 for the first h coordinates, and use the discrete Gaussian samples X that agree to this value. These samples belong 4

to an affine coset of an index-2h sublattice of L∗ . It turns out that the discrete Gaussian samples (for an appropriate width) are almost uniformly distributed over different cosets, thus this collective sampling adds 2h multiplicative factor in the time complexity in sampling. That is, the estimation can be anyway done. At first sight, it may seem that choosing one random coset could lose the spectral property of Hessian. This is not the case. Conditioning the first h coordinates of the samples on the dual lattice side corresponds to summing over the corresponding h coordinates of u as shown in Eq. (21). Thus, the shortest-vector contribution still appears in one of the 2ℓ coset Hessians! Given this intuition, we can indeed apply almost the same strategy to find a shortest vector. The overall time complexity becomes 22t0 n+h+o(n) + 2ℓ+o(n) where the first term is to sample 22t0 n discrete Gaussian samples in the target coset (as we get roughly one coset Gaussian sample out of 2h lattice Gaussian samples), and 2ℓ is the number of outputs to be checked. Balancing these costs gives 20.73147n+o(n) algorithm as shown in Theorem 5.8. May the fourth weigh what matters. The main loss in the above algorithm is due to the inefficient rejection step in the discrete Gaussian sampling over the sublattice coset. The last algorithm uses the following observation: For two probabilistic distributions D and E, where we know how to sample only from E and know their probabilistic density functions p and q, then we have   X X p(X) p(X) f (X) = EX∼E f (X) EX∼D [f (X)] = p(X)f (X) = q(X) · q(X) q(X) X

X

so that we can estimate the statistics regarding D only using samples from E. We use this idea. We first show that for a slightly wider width sR than original, we can sample discrete Gaussian directly on the target sublattice coset Λ. Of course, samples from the discrete Gaussian with a wider width sR do not have exactly the distribution required for Hessian estimation. We therefore use the above idea and assign each sample X the importance weight for the narrower target width sr < sR w(X) :=

PrDΛ,sr [X]ρsr (Λ) PrDΛ,sr [X] ρsr (X) = , ∝ ρsR (X) PrDΛ,sR [X]ρsR (Λ) PrDΛ,sR [X]

which is easily computable. Similarly to the above, we have EX∼DΛ,sr [f (X)] =

EX∼DΛ,sR [w(X)f (X)] EX∼DΛ,sR [w(X)]

for a function f . Thus the wider Gaussian with width R is used only to generate the samples, while the weights recover the Hessian corresponding to the narrower target  Gaussian  with width r. R2 The loss caused by importance sampling is ι = 12 log2 r(2R−r) in the exponent of the variance (Lemma 6.7), forcing us to sample 2ιn more samples. This turns 22t0 n+h time in the previous algorithm to 2(2r+ι)n , and balancing the parameters gives 20.60387n+o(n) time complexity in Theorem 6.11.1 Sparsity makes space for quantum. A careful reader may notice that the above algorithm requires 2(2r+ι)n Gaussian samples, thus its space complexity is also 20.60387n+o(n) . We observe that the value w(X) heavily depends on the norm of X, and in particular for most of X it is very close to 0. We can sparsify the Gaussian samples by employing a binary variable Z such that, conditioned on each sample X, choose Z ∈ {0, 1} such that Pr[Z = 1 | X] = π(X) and Pr[Z = 0 | X] = 1 − π(X) for some π(X) ∝ w(X). We use the following: For every function f ,      Zf (X) Zf (X) EX,Z = EX E X = EX [f (X)] π(X) π(X) 1 Note that since we do not even sample from the discrete Gaussian with width r, we can set r smaller than the limit of the original discrete Gaussian sampler [2]. We actually choose so, and extend several lemmas for r < t0 .

5

thus we can compute the statistics with a smaller number of X’s for which Z = 1, which is about E[π(X)] · 2(2r+ι)n . This gives a 20.5n+o(n) space version of the above algorithm, showing Theorem 6.14. Note that we anyway need to sample 2(2r+ι)n Gaussian samples, thus the time complexity remains unchanged. This reduced space actually allows us to use the quantum minimum finding algorithm [14]. The number of effective samples can be reduced to 22rn while ensuring the accuracy of the estimation at best. In this case, we choose b ≈ 2rn and write Fℓ2 = Fb2 × Fℓ−b 2 . For each fixed value of the last ℓ − b coordinates, the fast Walsh-Hadamard transform computes the corresponding 2b = 22rn+o(n) coset Hessians at once. Classically this is repeated 2ℓ−b times, while quantum minimum finding reduces the number of repetitions to 2(ℓ−b)/2 , which is 2ιn+o(n) for the optimized parameters. Balancing the parameter gives 20.5411n+o(n) quantum time and 20.5n+o(n) space in Theorem 6.15. The QRAM only stores the BDD preprocessing data and 22rn samples, which is 20.3604n+o(n) in the balanced parameters. Acknowledgment. The author is grateful to Yixin Shen for helpful discussions about an early version of this work, and to Jiseung Kim for kindly sharing a preliminary draft of his ongoing work [22].

2

Preliminaries

The sets of integers, positive integers, and real numbers are denoted by Z, N, and R. F2 denotes the field of two elements {0, 1}. We write [m] = {1, . . . , m} for m ∈ N. The Euclidean, operator, and Frobenius norms are denoted by ∥·∥, ∥·∥op , and ∥·∥F , respectively. The closed Euclidean ball of radius R is B2n (R) = {x ∈ Rn : ∥x∥ ≤ R}. For an event E, its indicator function is 1E . All logarithms are natural unless a base is specified. We write dist(t, S) := inf x∈S ∥t − x∥ for a set S and a vector t. The dimension n tends to infinity when discussing the asymptotic behavior. Unless specified otherwise, every o(1) term is uniform over the lattices and the fixed parameters in the stated ranges. A negligible function, denoted by negl(n), is smaller than n−c for every c > 0 for all sufficiently large n. We write ⟨B⟩ for the bit length of the input basis B and assume that it is polynomial in n.

2.1

Lattices and decoding

We only consider the full-rank lattice defined as follows.2 Let B = (b1 , ..., bn ) ∈ Rn×n be a matrix with independent columns. A full-rank lattice generated by B is a set L = L(B) := BZn , i.e., integer linear combinations of column vectors of B. We define its dual lattice by L∗ := {y ∈ span(L) : ⟨y, x⟩ ∈ Z for every x ∈ L} which also satisfies L∗ = B −T Zn when L is full-rank. A lattice L′ is called a sublattice of L if L′ ⊆ L. If L′ is a full-rank sublattice, L/L′ is the finite abelian group of cosets x + L′ . In particular, it holds that L/2L ∼ = Fn2 ,

L∗ /2L∗ ∼ = Fn2 .

For cosets a + 2L and x + 2L∗ , we can write a = Bu ∈ L and x = B −T z ∈ L∗ for u, z ∈ Fn2 . We call u is the parity class. The following is well-defined T

χa (x) := (−1)⟨x,a⟩ = (−1)z u and independent of the representatives. In the remainder of the paper, we use arbitrary representative of the coset which does not change any results. The first minimum λ = λ1 (L) is λ1 (L) := minx∈L\{0} ∥x∥. For R ≥ 0, define the counting function for the lattice points inside a ball NL (R) := |(L \ {0}) ∩ B2n (R)| . We use the following bound [32, Lemma 3], based on the spherical-code bound of [19]. 2 It is well-known that the full-rank case implies to the general case.

6

Lemma 2.1. Uniformly for full-rank n-dimensional lattices L and x ≥ 1, it holds for β = 20.4014... NL (xλ1 (L)) ≤ β n+o(n) xn . Definition 2.2 (Search-SVP). Given a basis of a full-rank lattice L, Search-SVP asks to find a nonzero v ∈ L with ∥v∥ = λ1 (L). Definition 2.3 (BDD). For 0 < α < 1/2, α-BDD takes a lattice L and a target vector t promised to satisfy dist(t, L) < αλ1 (L) as input, and returns the unique closest lattice vector to t. We use the following result for preprocessing BDD from [1]. Theorem 2.4. There is a randomized classical preprocessing algorithm for the n−1/3 -BDD problem such that: • its preprocessing runs in expected time and worst-case space 2n/2+o(n) and succeeds with a constant probability. After running, the size of advice is 2o(n) . • given the successful preprocessing output, any instance of the n−1/3 -BDD problem can be deterministically solved in time 2o(n) and polynomial additional space. √ Proof. Plug ε = exp(− n) in [1, Theorem 56] with α = 1/2,√which gives (ϕ(L)/λ1 (L))-BDD oracle in √ ln(1/ε)/π−o(1) m poly(n) time and space after the DGS preprocessing ϕ(L) = and m = O(n ln(1/ε)/ ε) = 2ηε (L∗ ) q pn 2o(n) . An asymptotic calculation gives ϕ(L)/λ1 (L) = Ω(n−1/4 ) using λ1 (L)ηε (L∗ ) ≤ ln((1+ε)/ε) + 2π . π This makes the query in m poly(n) = 2o(n) time and space. The preprocessing is only the discrete Gaussian samples, which can be sampled in time 2n/2+o(n) and space 2n/2+o(n) . We consider a time-truncated variant that returns ⊥ and aborts if the time is exceeded. For an input that does not meet the promise of n−1/3 -BDD, there is no correctness guarantee; we use an output only after exact lattice-membership verification. Whenever an algorithm is repeated, every trial uses independent preprocessing and fresh randomness, and we return the shortest exactly verified nonzero vector over all trials. Every DGS call is time-truncated at its stated budget. If the call exceeds the budget or returns too few samples, the current scale is aborted.

2.2

Discrete Gaussians

For s > 0, x ∈ Rn , and a countable set A, define ∥x∥ ρs (x) := exp −π 2 s

2

! ,

ρs (A) :=

X

ρs (x)

x∈A

For a full-rank lattice L ⊂ Rn and a vector t ∈ Rn , the discrete Gaussian on a lattice coset L + t is DL+t,s (x) :=

ρs (x) , ρs (L + t)

x ∈ L + t.

In particular, DL,s denotes the central case t = 0. Definition 2.5 (Smoothing parameter [26, 34]). For ε ∈ (0, 1), the smoothing parameter is the unique positive number ηε (L) satisfying ρ1/ηε (L) (L∗ \ {0}) = ε. Lemma 2.6 ([2, Lemma 6.1]). Let β be the constant in Lemma 2.1. For any full-rank lattice L ⊂ Rn , it holds that   √ β n ∗ η1/2 (L ) ≤ √ + o(1) . λ1 (L) 2πe

7

Theorem 2.7 ([2, Theorem 5.11]). Let L ⊂ Rn be a full-rank lattice, s > 0, and κ = Ω(n). There is a classical algorithm DGS that outputs at most M = 2n/2 lattice vectors in time 2n/2+polylog(κ)+o(n) and space 2n/2+o(n) . Its output distribution is exp(−Ω(κ))-close to the following distribution: choose M ′ ∈ {0, . . . ,√ M }, draw X1 , . . . , XM independently from DL,s and independently of M ′ , and output X1 , . . . , XM ′ . If s > 2η1/2 (L), then M ′ = M . Lemma 2.8. For every c > 0, there is a constant Cc > 0 such that, for every lattice L, every s > 0, and X ∼ DL,s , i h √ 2 P[∥X∥ > Cc s n] ≤ 2−2cn and E ∥X∥ 1{∥X∥>Cc s√n} ≤ s2 n 2−cn . Proof. The discrete-Gaussian tail inequality [2, Lemma 2.4] gives, for all sufficiently large constants t, √  √ 2 n P[∥X∥ > ts n] ≤ 2πe · te−πt . Choose t = Cc sufficiently large (which only depends on c) so that √ −πt2 2 2πe · te−πt ≤ e 2 ≤ 2−2c holds, which proves the first part. For the second part, the tail integration formula for Y = ∥X∥ gives Z ∞ E[Y 2 1{Y >u} ] = u2 P[Y > u] + 2zP[Y > z]dz. u

√ √ Taking u = Cc s n and z = ts n, we have

Z ∞

√ 2t · P[∥X∥ > ts n]dt Cc   Z ∞ −nπt2 2 2 −2cn 2 ≤ Cc s n2 +s n 2t · exp dt 2 Cc

E[Y 2 1{Y >Cc s√n} ] ≤ Cc2 s2 n2−2cn + s2 n

2e = Cc2 s2 n2−2cn + s2 n · 2

≤s n



Cc2 +

2 πn



2 −πnCc 2

πn

−2cn

2

where the last term is smaller than s2 n2−cn for sufficiently large n.

2.3

Useful inequalities

We use the following standard probability bounds. Lemma 2.9 (Markov’s inequality). For a random variable Y ≥ 0 and a > 0, P[Y ≥ a] ≤ E[Y ]/a. Lemma 2.10 (Chebyshev’s inequality). If Y has finite variance and a > 0, P[|Y − E[Y ]| ≥ a] ≤ Var(Y )/a2 . Lemma If Y1 , . . . , Y h P 2.11 (Hoeffding’si inequality). N are independent and ai ≤ Yi ≤ bi and δ > 0,  2 2 N 1 2N δ P N i=1 (Yi − E[Yi ]) ≥ δ ≤ 2 exp − PN (b −a )2 . i=1

i

i

Lemma 2.12 (Chernoff bound). If Y1 , . . . , YN are independent Bernoulli random variables and 0 < δ ≤ 1, then ! # " N N N N X X X δ2 X P Yi − E[Yi ] ≥ δ E[Yi ] ≤ 2 exp − E[Yi ] . 3 i=1 i=1 i=1 i=1 Lemma 2.13. If E1 , . . . , Em are independent events with P[Ei ] ≤ p < 1/4, then "m # X m P 1Ei ≥ ≤ 2m pm/2 . 2 i=1 8

3

Recovering Shortest Vector from Hessian

We assume that an approximate shortest-vector length d satisfying λ1 (L) ≤ d ≤ (1 + 1/n)λ1 (L)

(3)

is known. This can be assumed by applying LLL [24] and guessing d from {(1 + 1/n)−j ∥x∥}j=0,...,n2 , where x is the resulting nonzero vector. We formalize this in the final algorithm. It will be convenient to define the following parameters: r 4nt ln 2 β2 ξt = ξt (d) := , t0 := = 0.23147 . . . (4) 2 πd 4e ln 2 These choices give the Gaussian-mass estimates in Corollary 3.2. It will be convenient to note that for most of our interested case the following holds for most choices of t: ξt2 = Θ(n/d2 ) = Θ(n/λ2 ).

3.1

(5)

Scale and Gaussian mass bounds

√ Lemma 3.1. Let L be an n-dimensional full-rank lattice and let λ = λ1 (L). Let s = Θ(λ/ n) and let k ≥ 0 be a constant. Then k  2 2 n/2 X  β ns ∥x∥ 1+ ρs (x) ≤ 2o(n) . λ 2πeλ2 x∈L\{0}

Proof. The case k = 0 is essentially [2, Lemma 4.2]. The same shell argument gives X x∈L\{0}

 1+

∥x∥ λ

k

2 2

2

2 2

2

ρs (x) ≤ 2k β n+o(n) max y n+k e−πλ y /s ≤ β n+o(n) max y n+k e−πλ y /s . y>0

y≥0

Here we used ∥x∥ ≥ λ and hence  1+

∥x∥ λ

k

≤ 2k



2

The maximum is attained at y 2 = (n+k)s 2πλ2 , and its value is

∥x∥ λ 

k .

(n+k)s2 2πeλ2 o(n)

fixed, replacing n + k by n changes the expression by only 2 shell-summation factor are absorbed into the same term.

(n+k)/2

√ . Since s = Θ(λ/ n) and k is

. The fixed factor 2k and the subexponential

Corollary 3.2. Let λ = λ1 (L) and λ ≤ d ≤ (1 + 1/n)λ. For every fixed a > 0 and k ≥ 0, X x∈L\{0}

  k  a 2 t0 1 ∥x∥ 2 log2 2t +o(1) n ρa/ξt (x) ≤ 2 . 1+ λ1 (L)

Consequently, for every fixed a > 0 and k > 0, X

1

k

∥x∥ ρa/ξt (x) ≤ λk 2( 2 log2

a2 t0 2t +o(1))n

x∈L

In particular, the following hold: 1 t • For a (possibly negative) constant c, it holds that ρ√21+c /ξt (L) ≤ 1 + 2(c/2− 2 log2 t0 +o(1))n . • If t > t0 /2, then ρ1/ξt (L) = 1 + 2−Ω(n) . √ • If t > t0 , then ξt > 2 η1/2 (L∗ ), and Theorem 2.7 applies to L∗ at parameter ξt . 9

(6)

2

2

2

2

ns a t0 d Proof. For s = a/ξt , we have β2πeλ 2 = 2t λ2 . The first claim follows from Lemma 3.1, since d/λ ≤ 1 + 1/n. k k k The second claim follows from the first because √ its term at x = 0 vanishes and ∥x∥ ≤ λ (1 + ∥x∥/λ) for c+1 x= ̸ 0. The first bound follows by taking a = 2 for given c and k = 0. Plugging t > t0 /2 gives the second bound. If t > t0 , then the bound gives 1 ρ√2/ξt (L \ {0}) < 2 for all sufficiently large n. The definition and monotonicity of the smoothing parameter give the last claim.

3.2

The periodic Gaussian and the shortest parity class

For s > 0, define the periodic Gaussian function [5, 13] by ρs (L + z) , ρs (L)

z ∈ Rn .

(7)

i h Fs (z) = EX∼DL∗ ,1/s e2πi⟨X,z⟩ .

(8)

Fs (z) :=

The following is the Poisson representation of Fs .

For u ∈ Fn2 , define the Hessian

Gt,d (u) := ∇2 F1/ξt (Bu/2).

We also define At,d (u) := Gt,d (u) + 2πξt2 F1/ξt (Bu/2)In .

(9)

For fixed u, At,d (u) and Gt,d (u) differ by 2πξt2 F1/ξt (Bu/2)In , a constant multiple of In . Hence the two matrices have the same eigenvectors and eigengaps. We will use the following alternative formula. Lemma 3.3. For every u ∈ Fn2 , h i T T Gt,d (u) = −4π 2 EX∼DL∗ ,ξt XX T (−1)u (B X mod 2) .

(10)

Moreover, the following equality holds thus At,d (u) is positive semidefinite: At,d (u) =

π 2 ξt4 ρ1/ξt (L)

X

2

2

wwT e−πξt ∥w∥ /4 .

(11)

w∈Bu+2L

Proof. Differentiating the expression in Eq. (8) gives h i ∇2 Fs (z) = −4π 2 EX∼DL∗ ,1/s XX T e2πi⟨X,z⟩ . Set s = 1/ξt and z = Bu/2. Since B T X ∈ Zn , T

T

T

T

e2πi⟨X,Bu/2⟩ = eπiu B X = (−1)u (B X mod 2) . This proves the first identity. Differentiating the expression in Eq. (7) and using L = −L gives   2π 1 X 4π 2 T −π∥y−z∥2 /s2 ∇2 Fs (z) = (y − z)(y − z) − I . n ·e 4 2 ρs (L) s s y∈L

It follows that ∇2 Fs (z) +

2 2 2π 4π 2 X (y − z)(y − z)T e−π∥y−z∥ /s . Fs (z)In = 4 2 s s ρs (L)

y∈L

Again set s = 1/ξt , z = Bu/2, and reindex by w = 2y − Bu. The second identity follows from −Bu + 2L = Bu + 2L. 10

The following lemma shows that, if a shortest vector v is included in the coset Bu + 2L, the matrix At,d (u) is approximately proportional to the matrix vv T . Lemma 3.4. Let t > t0 and λ = λ1 (L) ≤ d ≤ (1 + 1/n)λ. Let v ∈ L satisfy ∥v∥ = λ and u ∈ Fn2 satisfy v ∈ Bu + 2L. For the normalized vector vb = v/λ, it holds that At,d (u) = µt,d vbvbT + Rt,d (u)

for

µt,d :=

2π 2 ξt4 λ2 −πξt2 λ2 /4 e = ξt4 λ2 2−tn+O(1) , ρ1/ξt (L)

where Rt,d (u) is positive semidefinite such that ∥Rt,d (u)∥op ≤ µt,d · 2

  − 21 log2 tt +o(1) n 0

(12)

.

Proof. Since Bu + 2L = v + 2L, the terms w = v and w = −v in Eq. (11) contribute 2 2 2π 2 ξt4 vv T e−πξt λ /4 = µt,d vbvbT . ρ1/ξt (L)

Let Rt,d (u) be the sum of the remaining terms. It is positive semidefinite. Write every element of v + 2L as w = −v + 2y for y ∈ L. The two removed terms correspond to y = 0 and y = v. Since Rt,d (u) is positive semidefinite, we have ∥Rt,d (u)∥op ≤ Tr (Rt,d (u)) . This gives ∥Rt,d (u)∥op µt,d

2

X

≤2

y∈L\{0,v}

∥y − v/2∥ −πξt2 (∥y−v/2∥2 −λ2 /4) e . λ2

For y ∈ / {0, v}, both y and y − v are nonzero lattice vectors. Hence 2

2

∥y − v/2∥ −

2

2

λ2 ∥y∥ + ∥y − v∥ − λ2 ∥y∥ = ≥ . 4 2 2

Moreover, ∥y − v/2∥ ∥y∥ ∥v∥ ∥y∥ ≤ + ≤ +1 λ λ 2λ λ √ Combining these two bounds and Corollary 3.2 with a = 2 and k = 2 gives 2   X  ∥Rt,d (u)∥op ∥y∥ − 1 log t +o(1) n ≤2 1+ ρ√2/ξt (y) ≤ 2 2 2 t0 . µt,d λ y∈L\{0}

Finally, the asymptotic of µt,d follows from the choice of ξt in Eq. (4) and λ ≤ d ≤ (1 + 1/n)λ, as well as ρ1/ξt (L) = 1 + 2−Ω(n) by Corollary 3.2.

3.3

Estimating the Hessians and recovering a shortest vector

By Lemma 3.4, the exact Hessian at the parity class of a shortest vector v contains some information about v. In this section, we show how to actually recover v using this property. As discussed in the overview, this can be done by the three steps; 1) compute an estimation of Hessian, 2) compute a unit vector close to the direction of v, and 3) recover the vector v using (preprocessing) BDD oracle from Theorem 2.4. Fix 0 < t < 1/4 and let Nt = ⌈n5 log n · 22tn ⌉.3 For independent X1 , . . . , XNt ∼ DL∗ ,ξt and u ∈ Fn2 , define Nt T T 4π 2 X Gbt,d (u) := − Xi XiT (−1)u (B Xi mod 2) 1{∥Xi ∥≤C1 ξt √n} , Nt i=1

(13)

where C1 is the constant in Lemma 2.8 for c = 1. The parameters will be chosen so that we can use the DGS algorithm in Theorem 2.7. The following lemma shows that Gb approximate G accurately. 3 Throughout this paper, we do not try to optimize the polynomial factors.

11

Lemma 3.5. For every fixed 0 < t < 1/4, with probability 1 − 2−Ω(n log n) , it holds for all u ∈ Fn2 that max Gbt,d (u) − Gt,d (u)

u∈Fn 2

op

≤ 2ξt2 2−tn .

√ b Proof. Let X ∼ DL∗ ,ξt . Noting that ∥X∥ > C1 ξt n is truncated in G, i h T T E[Gbt,d (u)] − Gt,d (u) = 4π 2 E XX T (−1)u (B X mod 2) 1{∥X∥>C1 ξt √n} . Using ∥E[M ]∥op ≤ E[∥M ∥op ] and XX T E[Gbt,d (u)] − Gt,d (u)

op

2

op

= ∥X∥ , Lemma 2.8 with c = 1 gives for sufficiently large n

h i 2 ≤ 4π 2 E ∥X∥ 1{∥X∥>C1 ξt √n} ≤ 4π 2 ξt2 n2−n ≤ ξt2 2−tn .

(14)

We next bound the probability that the estimation Gb is far from G. Fix u ∈ Fn2 and a, b ∈ {1, . . . , n}. The absolute value of the (a, b)-entry of each summand in Eq. (13) is at most 4π 2 |(Xi )a (Xi )b |1{∥Xi ∥≤C1 ξt √n} ≤ 4π 2 C12 ξt2 n. Therefore, Hoeffding’s inequality gives, using Nt = ⌈n5 log n · 22tn ⌉,       ξ2 Nt −2tn > t 2−tn ≤ 2 exp −Ω Gbt,d (u) − E[Gbt,d (u)] P 2 = 2e−Ω(n log n) . n n4 a,b By the union bound over all 2n n2 choices of u ∈ Fn2 and a, b ∈ {1, . . . , n}, with probability 1 − 2−Ω(n log n) , every entry of every difference Gbt,d (u) − E[Gbt,d (u)] has absolute value at most ξt2 2−tn /n. Since ∥M ∥op ≤ n maxa,b |Ma,b |, the operator norm of every difference is at most ξt2 2−tn . Together with Eq. (14), this concludes the proof. Given that Gbt,d (u) ≈ Gt,d (u) ≈ µt,d vbvbT due to Lemmas 3.4 and 3.5, the eigenvector of Gbt,d (u) must be close to the direction of v. The following lemma formalize this intuition. Lemma 3.6. Let t0 < t < 1/4 be fixed and let λ = λ1 (L) ≤ d ≤ (1 + 1/n)λ. Let v ∈ L satisfy ∥v∥ = λ, and let u ∈ Fn2 satisfy v ∈ Bu + 2L. Suppose that the conclusion of Lemma 3.5 holds. If q is a unit eigenvector corresponding to the largest eigenvalue of Gbt,d (u), then min

∥q − σv/λ∥ = O(n−1/2 ).

σ∈{−1,1}

Consequently, the n−1/3 -BDD query at dq returns one of ±v for all sufficiently large n. Proof. Let vb = v/λ. By Lemma 3.4 and the definition of At,d (u) in Eq. (9), Gbt,d (u) = −2πξt2 F1/ξt (Bu/2)In + µt,d vbvbT + E,

(15)

where E = Rt,d (u) + Gbt,d (u) − Gt,d (u) and ∥Rt,d (u)∥op /µt,d = 2−Ω(n) . Since λ ≤ d ≤ (1 + 1/n)λ, ξt2 λ2 = Θ(n). Also, µt,d = Θ(ξt4 λ2 2−tn ) by Lemma 3.4. Lemma 3.5 gives Gbt,d (u) − Gt,d (u) µt,d

op

 =O

1 ξt2 λ2



= O(n−1 ).

Together with ∥Rt,d (u)∥op /µt,d = 2−Ω(n) , this gives ∥E∥op = O(µt,d n−1 ). Since q is a eigenvector corresponding to the largest eigenvalue of Gbt,d (u), we have q T Gbt,d (u)q ≥ vbT Gbt,d (u)b v. Substituting the expression for Gbt,d (u) using Eq. (15), the multiple of In has the same value on both sides 12

2

because ∥q∥ = ∥b v ∥ = 1. The remaining inequality is µt,d ⟨q, vb⟩ + q T Eq ≥ µt,d + vbT Eb v . Since |q T Eq| ≤ ∥E∥op and |b v T Eb v | ≤ ∥E∥op , it follows that   2 µt,d 1 − ⟨q, vb⟩ ≤ q T Eq − vbT Eb v ≤ 2 ∥E∥op = O(µt,d n−1 ). 2

2

Choose σ ∈ {−1, 1} such that ⟨q, σb v ⟩ ≥ 0. It follows that ∥q − σb v ∥ ≤ 2(1 − ⟨q, vb⟩ ) = O(n−1 ). −1/2 −1/3 Finally, ∥dq − σv∥ ≤ d∥q − σb v ∥ + d − λ = O(λn ) < λn for all sufficiently large n. The last claim follows from Theorem 2.4. Combining the estimate and the recovery argument gives the direct algorithm. Algorithm 1: Direct Hessian SVP 1. Apply LLL reduction to obtain a nonzero x ∈ L and use the scales dj = (1 + 1/n)−j ∥x∥ for 0 ≤ j ≤ n2 . Construct the preprocessing n−1/3 -BDD data. 2. Fix t0 < t < 1/4. At every scale dj , call DGS from Theorem 2.7 with κ = n2 and keep Nt samples from DL∗ ,ξt (dj ) . Abort the scale if fewer than Nt samples are returned. 3. For every u ∈ Fn2 , evaluate Gbt,dj (u) directly and compute a unit eigenvector qu corresponding to its largest eigenvalue. Query BDD at dj qu and retain the output only after exact lattice-membership verification. 4. Return the shortest verified nonzero vector over all scales and all u. Theorem 3.7. Algorithm 1 solves Search-SVP with constant probability in time 21.46295n+o(n) and space 2n/2+o(n) . Proof. The correctness follows from the previous lemmas. Lemma 3.5 shows that Gb estimate G for all inputs with overwhelming probability, and in that case Lemma 3.6 and Theorem 2.4 show the correctness of the final outcome. We explain the time and space complexity below. There are polynomially many choices of dj because of the property of LLL-reduced vectors. For each dj , the algorithm considers all 2n values of u ∈ Fn2 , and evaluating Gbt,dj (u) takes Nt poly(n) time for Nt = poly(n)22tn . Hence the total time is 2(1+2t)n+o(n) . Because of Lemma 3.4, we have 1 + 2t > 1 + 2t0 = 1.4629 . . . , thus choosing t → t0 gives the desired time complexity. All remaining steps take less time and do not affect the overall time complexity. The space complexity is due to DGS in Theorem 2.7.

4

Batch Hessian Estimation

The factor 2n in the 21.4629n+o(n) running time of the previous section comes from evaluating Gbt,d (u) separately for every u ∈ Fn2 . The definition of Gbt,d (u) uses the same samples for all u, and Lemma 3.5 proves that all these estimators are simultaneously accurate. This section optimizes the algorithm by batching the Hessian estimations. The main idea is to use the Walsh-Hadamard transform in the following lemma. Lemma 4.1. Let A : Fℓ2 → Rn×n . Given A(x) for every x ∈ Fℓ2 , the matrices X (−1)θ·x A(x), θ ∈ Fℓ2 , x∈Fℓ2

can be computed in time 2ℓ poly(n) and space 2ℓ poly(n). Proof. Store the matrices A(x) in an array indexed by Fℓ2 . For every j ∈ {1, . . . , ℓ} and every x ∈ Fℓ2 with xj = 0, replace

A(x), A(x + ej ) by A(x) + A(x + ej ), A(x) − A(x + ej ) , 13

where ej is the jth standard basis vector. After processing all ℓ coordinates, the entry indexed by θ equals P θ·x (−1) A(x). There are ℓ2ℓ−1 replacements, and the array contains 2ℓ matrices. x Algorithm 2: Walsh-Hadamard Hessian SVP 1. Construct the preprocessing BDD data and the scale grid, choose t, and obtain the Discrete Gaussian samples at every scale dj as in Algorithm 1. Set ℓ = ⌊n/2⌋. 2. At each scale dj that was not aborted, define, for every sample Xi , ki := B T Xi mod 2,

Wi := −

4π 2 Xi XiT 1{∥Xi ∥≤C1 ξt (dj )√n} . Nt

Write ki = (ki′ , ki′′ ) ∈ Fℓ2 × Fn−ℓ . 2 3. For every θ′′ ∈ Fn−ℓ , construct the array Aθ′′ : Fℓ2 → Rn×n given by 2 X ′′ ′′ Aθ′′ (x) := (−1)θ ·ki Wi . 1≤i≤Nt ki′ =x

Apply Lemma 4.1 to Aθ′′ . The matrix indexed by θ′ ∈ Fℓ2 is Gbt,dj (θ′ , θ′′ ). For each such matrix, compute a unit eigenvector q corresponding to its largest eigenvalue, query BDD at dj q, and retain the output if it is a nonzero lattice vector. 4. Return the shortest retained vector over all scales. Theorem 4.2. Algorithm 2 solves Search-SVP in time 2n+o(n) and 2n/2+o(n) space with constant success probability. Proof. For u = (θ′ , θ′′ ), the matrix produced by the transform is X x∈Fℓ2

′

(−1)θ ·x Aθ′′ (x) =

Nt X ′ ′ ′′ ′′ (−1)θ ·ki +θ ·ki Wi = Gbt,dj (u). i=1

Thus the algorithm evaluates exactly the estimators defined in Eq. (13). The correctness then follows the same argument as in Theorem 3.7. Now we discuss the space and time complexity. In the algorithm, only one array Aθ′′ is stored at a time. The array contains 2ℓ matrices, while the number of Discrete Gaussian samples is Nt < 2n/2 . Together with the preprocessing BDD data, this gives space 2n/2+o(n) . For each fixed θ′′ , constructing the array Aθ′′ takes Nt poly(n) time and the following Hadamard-Walsh transform take 2ℓ+o(n) time by Lemma 4.1. Since there are 2n−ℓ choices of θ′′ , the total time for each dj is 2n−ℓ (Nt + 2ℓ )2o(n) . Here ℓ = ⌊n/2⌋ and Nt = 22tn+o(n) < 2n/2 because t < 1/4. Therefore, the total time over the polynomially many scales is 2n+o(n) .

5

Random Sublattice Coset Hessian

b The algorithm in Section 4 computes G(u) for all u ∈ Fn2 , resulting in the complexity 2n+o(n) . This section shows that the same strategy works by estimating the Hessians using vectors in a sublattice cosets. As always, we mainly focus on the case λ ≤ d ≤ (1 + 1/n)λ for λ = λ1 (L). We write g(t) := 12 log2 (t/t0 ) for t > 0. For our main interested parameter d, Corollary 3.2 gives, for every fixed c and positive integer k, X k ∥x∥ ρ√21+c /ξt (x) ≤ λk 2(c/2−g(t)+o(1))n , and ρ√21+c /ξt (L) ≤ 1 + 2(c/2−g(t)+o(1))n . (16) x∈L

14

The following term from Lemma 3.4 is convenient for us. µt,d = ξt4 λ2 2−tn+O(1) = ξt4 d2 2−tn+O(1)

5.1

λ ≤ d ≤ (1 + 1/n)λ.

for

(17)

Gaussian and Hessian sums

The following periodic Gaussian and Hessian mass bounds will be used in this section. Lemma 5.1. For every s > 0, X

ρ2s (L) . ρs (L)

Fs (Bu/2) =

u∈Fn 2

If λ ≤ d ≤ (1 + 1/n)λ, it holds that

(1/2−g(t)+o(1))n . u̸=0 F1/ξt (Bu/2) ≤ 2

P

Proof. The cosets Bu/2 + L for u ∈ Fn2 partition 12 L. Hence, X

Fs (Bu/2) =

u∈Fn 2

X ρs (Bu/2 + L)

=

ρs (L)

u∈Fn 2

ρs ( 12 L) ρ2s (L) = . ρs (L) ρs (L)

The final statement follows from Eq. (16) with c = 1. Lemma 5.2. Let λ ≤ d ≤ (1 + 1/n)λ and t > t0 /2. Then X 2 ∥At,d (u)∥F ≤ µ2t,d 2(2t−min{g(t),2g(t)}+o(1))n . u∈Fn 2 2

Proof. We use ∥X∥F = Tr(X T X) for the real matrix X. Applying this to Eq. (11), the left-hand side becomes 

π 2 ξt4 ρ1/ξt (L)

2 X

′

2

Tr(zz T z ′ z ′T )e−πξt (∥z∥ +∥z ∥ )/4 . 2

X

2

′ u∈Fn 2 z,z ∈Bu+2L ′

′

z−z 2 As u varies, the map from (z, z ′ ) ∈ (Bu + 2L)2 defined by (z, z ′ ) 7→ (p = z+z 2 ,q = 2 ) is a bijection to L , and it satisfies 2

2

2

2

Tr(zz T z ′ z ′T ) = (z T z ′ )2 = (∥p∥ − ∥q∥ )2 ,

2

2

∥z∥ + ∥z ′ ∥ = 2(∥p∥ + ∥q∥ ).

Therefore, X u∈Fn 2

Let w(x) = e

−πξt2 ∥x∥2 /2

2

∥At,d (u)∥F =

X 2 2 2 π 4 ξt8 2 2 (∥p∥ − ∥q∥ )2 e−πξt (∥p∥ +∥q∥ )/2 . 2 ρ1/ξt (L) p,q∈L

2

2

4

4

= ρ√2/ξt (x). Using (∥p∥ − ∥q∥ )2 ≤ 2(∥p∥ + ∥q∥ ), the sum over p, q ∈ L is at most  4

 X

4

∥p∥ w(p) 

p∈L

 X

w(q) .

q∈L 4

4

Indeed, the Gaussian weight factors as w(p)w(q), and the two terms obtained from ∥p∥ + ∥q∥ are equal. Applying the first inequality with k = 4 and c = 0 of Eq. (16) to the first term and the second inequality with c = 0 to the second term, we have an upper bound λ4 2(−g(t)+o(1))n · (1 + 2(−g(t)+o(1))n ) = λ4 2(− min{g(t),2g(t)}+o(1))n . The resulting exponent is −g(t) if g(t) ≥ 0 and −2g(t) otherwise. The fixed constants and ρ1/ξt (L)−2 ≤ 1 are absorbed into 2o(n) . The final result is obtained using Eq. (17). 15

5.2

A random coset Hessian

Fix 0 ≤ χ ≤ 1/2. We split each parity class u ∈ Fn2 into h = ⌊χn⌋ and ℓ = n − h bits in random basis. For P ∈ GLn (F2 ), u ∈ Fn2 , and X ∈ L∗ , define P u = (α, θ) ∈ Fh2 × Fℓ2 ,

P −T B T X mod 2 = (JP (X), VP (X)) ∈ Fh2 × Fℓ2 .

Define Λj := {X ∈ L∗ : JP (X) = j}. The set Λ0 is a sublattice of L∗ , and each Λj for j ∈ Fh2 is one of its cosets. Note that every Λj is nonempty because the map X 7→ P −T (B T X mod 2) from L∗ to Fn2 is surjective. Therefore, Λj can be written as Λ0 + vj for some vj ∈ Λj thus the discrete Gaussian DΛj ,s is well-defined. For θ ∈ Fℓ2 , we define the (sublattice) coset Hessian along Λj analogous to Lemma 3.3 by h i T Gt,d,j (θ) := −4π 2 EX∼DΛj ,ξt XX T (−1)θ VP (X) (18) based on the identity for X ∈ Λj uT (B T X mod 2) = (P u)T (P −T B T X mod 2) = αT JP (X) + θT VP (X) = αT j + θT VP (X)

(mod 2) (19)

T

For u = P −1 (α, θ), Eq. (18) omits the factor (−1)α j . This omission allows Gt,d,j is defined independent of α, yet we should be careful about that factor. Let ζt,j := 2h PX∼DL∗ ,ξt [JP (X) = j] be the probability, normalized by the uniform probability 2−h , that a discrete Gaussian sample of width ξt belongs to the affine lattice coset Λj . The following lemma shows that ζt,j is near 1, i.e., the distribution of JP (X) for the Discrete Gaussian sample X is pointwise exponentially close to uniform. The parameter condition of this lemma is intentionally general for the later application. Lemma 5.3. If λ = λ1 (L) ≤ d ≤ (1 + 1/n)λ, t > t0 /2, and 0 ≤ χ ≤ 1/2 and χ < 1/2 + g(t), then, with probability 1 − 2−Ω(n) over the uniform random P ∈ GLn (F2 ), ζt,j = 1 + O(2−Ω(n) ) for every j ∈ Fh2 . P Proof. Recall 2h 1{y=j} = α∈Fh (−1)α·(y+j) for y, j ∈ Fh2 . Applying the identity with y = JP (X) and taking 2 the expectation over X ∼ DL∗ ,ξt gives X ζt,j = (−1)α·j E[(−1)α·JP (X) ]. α∈Fh 2

Let KP := P −1 (Fh2 × {0}) and κ = P −1 (α, 0) ∈ KP for α ∈ Fh2 . The Poisson representation in Eq. (8) gives T

T

F1/ξt (Bκ/2) = EX∼DL∗ ,ξt [e2πi⟨X,Bκ/2⟩ ] = EX∼DL∗ ,ξt [(−1)κ (B X mod 2) ] = EX∼DL∗ ,ξt [(−1)α·JP (X) ]. Plugging this equation to the summand in ζt,j above, we have X X

ζt,j = (−1)α·j F1/ξt BP −1 (α, 0)/2 . (−1)α·j F1/ξt BP −1 (α, 0)/2 = 1 + α∈Fh 2

α̸=0

By substituting κ = P −1 (α, 0), we have |ζt,j − 1| ≤

P

κ∈KP F1/ξt (Bκ/2) for all j. We bound this term using κ̸=0 n Lemma 5.1. For each nonzero κ ∈ F2 , the space KP for random P is a uniform random h-dimensional subspace so that PP [κ ∈ KP ] = (2h − 1)/(2n − 1) = 2(χ−1+o(1))n . This gives

EP

X

F1/ξt (Bκ/2) ≤ 2(χ−1/2−g(t)+o(1))n .

κ∈KP ,κ̸=0

The exponent is a negative constant by the assumption χ < 1/2 + g(t). Markov’s inequality shows that, except with probability 2−Ω(n) over P , X F1/ξt (Bκ/2) ≤ 2−Ω(n) . κ∈KP ,κ̸=0

This proves the lemma, as the upper bound of |ζt,j − 1| holds simultaneously for all j. 16

The following lemma shows the sampling from DΛj ,ξt can be done by sampling from the entire DL∗ ,ξt and then collecting the samples with JP (X) = j thanks to the almost uniformity. Lemma 5.4. If λ ≤ d ≤ (1 + 1/n)λ, t0 < t < 1/4, and 0 ≤ χ ≤ 1/2, there is a classical algorithm that for independent uniform P ∈ GLn (F2 ) and j ∈ Fh2 , outputs Nt = ⌈n5 log n · 22tn ⌉ lattice vectors or aborts in time 2(max{1/2,χ+2t}+o(1))n and space 2n/2+o(n) . It does not abort with probability 1 − 2−Ω(n) over P and the sampler randomness, and in that case, the joint distribution of its outputs has statistical distance at most
Nt exp −Ω(n2 ) from DΛ . j ,ξt Proof. We use Theorem 2.7 ⌈4Nt 2h−n/2 ⌉ times sequentially, collect the samples satisfying JP (X) = j, and discard the others. By Lemma 5.3, except with probability 2−Ω(n) over P , PX∼DL∗ ,ξt [JP (X) = j] =
2−h 1 + O(2−Ω(n) ) simultaneously for every j ∈ Fh2 . For every such P and every j, the Chernoff bound in Lemma 2.12 shows that fewer than Nt samples are accepted among 4Nt 2h independent samples with probability 2−Ω(Nt
) . The statistical distance from independent DL∗ ,ξt samples changes this probability by at most exp −Ω(n2 ) . Therefore, the procedure aborts with probability 2−Ω(n) . The time and space complexity is clear.

5.3

Estimating the coset Hessian

Fix t0 = 0.23147 . . . < t < 1/4 and Nt = ⌈n5 log n · 22tn ⌉. For independent samples from the coset discrete Gaussian distribution X1 , . . . , XNt ∼ DΛj ,ξt , define an estimation of Eq. (18) analogous to Eq. (13) by Nt 4π 2 X Gbt,d,j (θ) := − Xi XiT (−1)θ·VP (Xi ) 1{∥Xi ∥≤C1 ξt √n} Nt i=1

(20)

which can be computed using Lemma 5.4. We show that Gbt,d,j approximates Gt,d,j similar to Lemma 3.5. Lemma 5.5. Let λ = λ1 (L) and λ ≤ d ≤ (1 + 1/n)λ. Choose independent uniform P ∈ GLn (F2 ) and j ∈ Fh2 . For independent X1 , . . . , XNt ∼ DΛj ,ξt , with probability 1 − 2−Ω(n) over P, j, X1 , . . . , XNt , µ  t,d max Gbt,d,j (θ) − Gt,d,j (θ) =O . n op θ∈Fℓ2 Proof. By Lemma 5.3, except with probability 2−Ω(n) over P , we have ζt,j ≥ 1/2 for every j ∈ Fh2 . Fix such a matrix P . Let Y ∼ DL∗ ,ξt and X ∼ DΛj ,ξt . By P[JP (Y ) = j] = 2−h ζt,j and Lemma 2.8 with c = 1, we have h i i 2h h 2 2 E ∥X∥ 1{∥X∥>C1 ξt √n} ≤ E ∥Y ∥ 1{∥Y ∥>C1 ξt √n} ≤ 2h+1 ξt2 n2−n . ζt,j With the same argument for Eq. (14), we have E[Gbt,d,j (θ)] − Gt,d,j (θ)

op

≤ 8π 2 ξt2 n2−ℓ ≤

ξt4 d2 −tn 2 n

for all sufficiently large n, where we used ℓ ≥ n/2, t < 1/4, and ξt2 d2 = 4nt ln 2/π. Each entry of the random matrix in Eq. (20) has absolute value at most 4π 2 C12 ξt2 n. Hence, for fixed θ ∈ Fℓ2 and a, b ∈ {1, . . . , n}, Hoeffding’s inequality gives       ξt4 d2 −tn Nt ξt4 d4 −2tn b b P Gt,d,j (θ) − E[Gt,d,j (θ)] > 2 2 ≤ 2 exp −Ω 2 = 2e−Ω(n log n) . n n6 a,b Here we used Nt = ⌈n5 log n · 22tn ⌉ and ξt2 d2 = 4nt ln 2/π. A union bound over the 2ℓ n2 choices of θ, a, b shows that, with probability 1 − 2−Ω(n log n) over the samples, max Gbt,d,j (θ) − E[Gbt,d,j (θ)] θ∈Fℓ2

≤ op

ξt4 d2 −tn 2 n

The triangle inequality applied to Gbt,d,j (θ) − E[Gbt,d,j (θ)] and E[Gbt,d,j (θ)] − Gt,d,j (θ) proves the lemma, after using µt,d = ξt4 d2 2−tn+O(1) . 17

5.4

Coset Hessians and shortest vectors

It remains to show how to relate the coset Hessians and the (direction) of shortest vectors as in Lemma 3.4. The following lemma extends Eq. (9) to the coset Hessian.
P 1 α·j Lemma 5.6. Gt,d,j (θ) − ζt,j At,d P −1 (α, θ) ∈ span{In }. α∈Fh (−1) 2

−h

Proof. Since P[JP (X) = j] = 2

ζt,j , the definition of Gt,d,j (θ) gives

Gt,d,j (θ) = −

h i 4π 2 2h EX∼DL∗ ,ξt XX T (−1)θ·VP (X) 1{JP (X)=j} . ζt,j

P Observe that 2h 1{y=j} = α∈Fh (−1)α·(y+j) for every y, j ∈ Fh2 . Indeed, if y = j, every summand is one; 2 otherwise, the summands can be paired with opposite signs. Applying this identity with y = JP (X) and interchanging the finite sum and expectation gives Gt,d,j (θ) =

1 X ζt,j

(−1)α·j Gt,d P −1 (α, θ)

(21)

α∈Fh 2

where we put u = P −1 (α, θ) and use Eq. (19) to derive T

T

(−1)θ·VP (X) · (−1)α·JP (X)+α·j = (−1)α·j · (−1)α·JP (X)+θ·VP (X) = (−1)α·j · (−1)u (B X mod 2) . T

T

The term (−1)u (B X mod 2) is exactly the term in Lemma 3.3, proving Eq. (21). The final inclusion is proven by using Lemma 3.3 on Gt,d (P −1 (α, θ)) − At,d (P −1 (α, θ)) ∈ span{In } for each α. This lemma gives some intuition why the approach in this section works. If one of P −1 (α, θ) = u is such that Bu + 2L contains a shortest vector v, the corresponding At,d (P −1 (α, θ)) must be approximately proportional to vv T . We will prove that the sum of the remaining terms is exponentially smaller with high probability over P and j. Therefore, some eigenvector of Gt,d,j (θ) must be approximately proportional to v, as the multiple of In does not affect the eigen vectors and the order of eigenvalues. The coefficient of the first term is (−1)α∗ ·j , so it may determine either the largest or the smallest eigenvalue. We therefore consider both extreme eigenvalues. Similarly to Lemma 3.6, we obtain the following lemma. Lemma 5.7. Let t0 < t < 1/4 be fixed, let 0 ≤ χ ≤ 1/2, and let λ = λ1 (L) ≤ d ≤ (1 + 1/n)λ. Let v ∈ L satisfy ∥v∥ = λ, and let u∗ ∈ Fn2 satisfy v ∈ Bu∗ + 2L. Choose independent uniform P ∈ GLn (F2 ) and j ∈ Fh2 , and write P u∗ = (α∗ , θ∗ ). With probability 1 − 2−Ω(n) over P and j, the following holds. Suppose that the conclusion of Lemma 5.5 holds. Let q+ and q− be unit eigenvectors corresponding to the largest and smallest eigenvalues of Gbt,d,j (θ∗ ), respectively. Then there are s ∈ {+, −} and τ ∈ {−1, 1} such that ∥qs − τ v/λ∥ = O(n−1/2 ). Consequently, the n−1/3 -BDD query at dqs returns τ v for all sufficiently large n. Proof. Let vb = v/λ and recall Lemma 3.4 stating that At,d (u∗ ) = µt,d vbvbT + Rt,d (u∗ ) for ∥Rt,d (u∗ )∥op /µt,d = 2−Ω(n) , where µt,d = ξt4 λ2 2−tn+O(1) . We first bound the contribution from α = ̸ α∗ . For fixed P , expanding the squared Frobenius norm using 2 ∥X∥F = Tr(X T X) for the real matrix X, 2

X α̸=α∗

(−1)j·(α−α∗ ) At,d P −1 (α, θ∗ )

= F

X


T
 ′ (−1)j·(α−α ) Tr At,d P −1 (α′ , θ∗ ) At,d P −1 (α, θ∗ )

α,α′ ̸=α∗

18

′

and taking the expectation over uniform j using Ej [(−1)j·(α−α ) ] = 0 for α ̸= α′ gives 2

Ej

X

j·(α−α∗ )

(−1)

At,d P

−1

(α, θ∗ )

α̸=α∗

= F

X

2 At,d P −1 (α, θ∗ ) F .

α̸=α∗

Now we are taking the expectation over P . For each fixed u = ̸ u∗ , the matrix At,d (u) occurs in the sum on exactly when P (u − u∗ ) ∈ Fh2 × {0}. Since P (u − u∗ ) is uniform over Fn2 \ {0}, the probability that P (u − u∗ ) is included in Fh2 × {0} is exactly (2h − 1)/(2n − 1). Consequently, Lemma 5.2 gives 2

EP,j

X

(−1)j·(α−α∗ ) At,d P −1 (α, θ∗ )

α̸=α∗

≤ 2h−n · (µ2t,d 22tn−g(t)n+o(n) ) = µ2t,d 2(χ−1−g(t)+2t+o(1))n

F

where we use h = ⌊χn⌋. Since χ ≤ 1/2, t < 1/4, and g(t) > 0, the exponent satisfies χ − 1 − g(t) + 2t < 0. Markov’s inequality shows that X

≤ µt,d 2−Ω(n)

(−1)j·(α−α∗ ) At,d P −1 (α, θ∗ )

α̸=α∗

(22)

F

holds except with probability 2−Ω(n) over P and j, and the same bound holds for the operator norm as well. µt,d vbvbT − aIn using Lemma 5.6 For the hidden sign σ = (−1)α∗ ·j , we can decompose E := σ Gbt,d,j (θ∗ ) − ζt,j for some a and bound its operator norm by   X

1  (−1)j·(α−α∗ ) At,d P −1 (α, θ∗ ) Gbt,d,j (θ∗ ) − Gt,d,j (θ∗ ) + + ∥Rt,d (u∗ )∥op  = O µt,d n−1 ζt,j op α̸=α∗

op

where we use Lemma 5.5 and Eq. (22) together with ζt,j = 1 + O(2−Ω(n) ) from Lemma 5.3. Let q be the unit eigenvector corresponding to the largest eigenvalue of σ Gbt,d,j (θ∗ ), which must be one of q+ µt,d (if σ = 1) or q− (if σ = −1). Hence q T σ Gbt,d,j (θ∗ )q ≥ vbT σ Gbt,d,j (θ∗ )b v . Plugging σ Gbt,d,j (θ∗ ) = ζt,j vbvbT + aIn + E, we obtain the following inequality 
µt,d  2 1 − ⟨q, vb⟩ ≤ 2 ∥E∥op = O µt,d n−1 . ζt,j 2

Thus 1 − ⟨q, vb⟩ = O(n−1 ). Choosing τ ∈ {−1, 1} such that ⟨q, τ vb⟩ ≥ 0 gives ∥q − τ vb∥ = O(n−1/2 ). Finally, ∥dq − τ v∥ ≤ d∥q − τ vb∥ + d − λ = O(λn−1/2 ) < λn−1/3 for all sufficiently large n. The final claim follows from Theorem 2.4.

5.5

The affine-coset algorithm

This section presents the algorithm using the affine cosets. The overall time complexity is 20.7314n ≈ 2(0.5+t)n+o(n) by balancing 2max(0.5,χ+2t)n+o(n) of the DGS sampling from Lemma 5.4 and 2ℓ+o(n) = 2(1−χ)n+o(n) of the number of θ ∈ Fℓ2 , where h = ⌊χn⌋, t0 = 0.2314 . . . < t < 1/4 and Nt = 2(2t+o(1))n . This can be obtained using the Walsh-Hadamard transform as before, and the other steps take much smaller time.

19

Algorithm 3: Affine-coset Hessian SVP 1. Construct the preprocessing n−1/3 -BDD data and the scale grid from Algorithm 1. Choose t0 < t < 1/4, and put χ = 1/2 − t. 2. At every scale d, choose independent uniform P ∈ GLn (F2 ) and j ∈ Fh2 . Apply the sampling algorithm from Lemma 5.4. Abort the scale d unless Nt samples from DΛj ,ξt are obtained. 3. Let b = ⌊n/2⌋. For every accepted sample Xi , define VP (Xi ) = (ki′ , ki′′ ) ∈ Fb2 × Fℓ−b 2 ,

Wi := −

4π 2 Xi XiT 1{∥Xi ∥≤C1 ξt √n} . Nt

For each θ′′ ∈ Fℓ−b 2 , do the following: P ′′ ′′ (a) Construct the array Aθ′′ (x) := 1≤i≤Nt (−1)θ ·ki Wi for all x ∈ Fb2 . ki′ =x

(b) Apply the matrix-valued Walsh-Hadamard transform to obtain for every θ′ ∈ Fb2 : X

′

(−1)θ ·x Aθ′′ (x) =

x∈Fb2

Nt X ′ ′ ′′ ′′ (−1)θ ·ki +θ ·ki Wi = Gbt,d,j (θ′ , θ′′ ).

(23)

i=1

(c) For each output in Eq. (23), compute unit eigenvectors q+ and q− corresponding to its largest and smallest eigenvalues and query BDD at dq± . Store a nonzero output in L. Keep only the shortest vector found, and discard the other vectors and temporal data. 4. Return the shortest vector over all scales. Theorem 5.8. Algorithm 3 solves Search-SVP with constant success probability in time 20.7314n+o(n) and space 2n/2+o(n) . Proof. Suppose λ1 (L) ≤ d ≤ (1 + 1/n)λ1 (L) and let v a shortest vector. Choose u∗ ∈ Fn2 such that v ∈ Bu∗ + 2L, write P u∗ = (α∗ , θ∗ ), and write θ∗ = (θ∗′ , θ∗′′ ) ∈ Fb2 × Fℓ−b 2 . By Lemma 5.4, the algorithm obtains the specified samples from DΛj ,ξt . By Eq. (23), the iteration indexed by θ∗′′ computes Gbt,d,j (θ∗′ , θ∗′′ ) = Gbt,d,j (θ∗ ). The conclusion of Lemma 5.5 holds simultaneously for every θ ∈ Fℓ2 , and Lemma 5.7 shows
the correctness. The statistical distance in Lemma 5.4 only changes the success probability by exp −Ω(n2 ) . We analyze the time and space complexity. Sampling takes 2(max{1/2,χ+2t}+o(1))n time by Lemma 5.4. There are 2ℓ−b sequential iterations. In each iteration, constructing the array takes Nt poly(n) time, and its Walsh-Hadamard transform, eigenvector computations, and 2b+1 BDD queries take 2b+o(n) time. Since Nt = 2(2t+o(1))n < 2b+o(n) = 20.5n+o(n) , their total time is 2ℓ+o(n) . Since ℓ = (1 − χ)n + O(1) and χ = 1/2 − t, the time exponent is max{χ + 2t, 1 − χ} = 1/2 + t → 0.7314 for t → t0 . The space complexity is dominated by the number of accepted samples and the preprocessing BDD data, which is 2n/2+o(n) .

6

Importance Sampling on an Affine Lattice Coset

This section improves the algorithm in Section 5 by sampling from DΛj ,ξR and estimating the Hessian defined using the smaller width ξr . Fix constants 0 < r < R with r < 1/4 and 0 < χ < 1/2. Let h = ⌊χn⌋ and ℓ = n − h as in Section 5.2. Recall g(t) = 12 log2 (t/t0 ). We use the parameters R and r for the source and target widths, respectively.

20

6.1

Lattice points in a shortest parity class

We first study the number of lattice points in the parity classes to improve some inequalities and conditions in some lemmas. For 0 < φ < π/2, define the Kabatiansky-Levenshtein constant BKL (φ) :=

1 + sin φ 1 + sin φ 1 − sin φ 1 − sin φ log2 − log2 . 2 sin φ 2 sin φ 2 sin φ 2 sin φ

Note that β in Lemma 2.1 is such that log2 β = BKL (π/3) as shown in [32]. We use the following bound [19]. Theorem 6.1. Let 0 < φ < π/2 be fixed. If S ⊆ {x ∈ Rn : ∥x∥ = 1} and the angle between every two distinct vectors in S is at least φ, then |S| ≤ 2(BKL (φ)+o(1))n . The o(1) term is uniform when φ ranges over a compact subinterval of (0, π/2). The counting argument in the following lemma is a variant of [32, Lemma 3]. The restriction to v + 2L gives the stronger separation used below. √ Lemma 6.2. Let v be a shortest √ vector and put√λ = ∥v∥. Every w ∈ v + 2L \ {±v} satisfies ∥w∥ ≥ 3λ. Moreover, for every fixed C ≥ 3, uniformly for 3 ≤ x ≤ C, 2

|{w ∈ v + 2L \ {±v} : ∥w∥ ≤ xλ}| ≤ 2(BKL (arccos(1−2/x ))+o(1))n . ̸ ±v, then y and y − v are nonzero lattice vectors. The parallelogram identity Proof. Write w = 2y − v. If w = 2 2 2 gives ∥w∥ + λ2 = 2∥y∥ + 2∥y − v∥ ≥ 4λ2 . For distinct w, w′ ∈ v +2L, the vector (w −w′ )/2q is a nonzero lattice vector, and hence ∥w − w′ ∥ ≥ 2λ. For 2

each vector with ∥w∥ ≤ xλ, append the coordinate x2 λ2 − ∥w∥ . The resulting vectors in Rn+1 have norm
xλ and pairwise distance at least 2λ. After normalization, their pairwise angles are at least arccos 1 − 2/x2 . The result follows from Theorem 6.1. We improve the bound on ρ2√2/ξt (L) ≤ 1 + 2(1−g(t)+o(1))n in Corollary 3.2 (i.e. Eq. (16)) using a more fine-grained counting argument with the vectors in each coset modulo 2L. For x ≥ 1, define ( √ 0, 1 ≤ x ≤ 2, √
K2 (x) := BKL (arccos 1 − 2/x2 ), x > 2, Combining Theorem 6.1 with Lemma 2.1, the number of nonzero vectors in L of norm at most xλ is NL (xλ1 (L)) ≤ 2(min{log2 β+log2 x,1+K2 (x)}+o(1))n . Recall g(t) = 21 log2 (t/t0 ) for t0 = 0.23147 . . . . Define4   R 2 g2 (R) := 1 − sup min {log2 β + log2 x, 1 + K2 (x)} − x ≥ g(R). 2 x≥1

(24)

Lemma 6.3. Let λ = λ1 (L) ≤ d ≤ (1 + 1/n)λ. For every fixed R > 0, ρ2√2/ξR (L \ {0}) ≤ 2(1−g2 (R)+o(1))n . Note that the proof of this lemma is rather complicated and somewhat independent to the other arguments. The readers may use a simpler bound with g. All arguments in this section works well by using g in place of g2 , which gives a only slightly bad complexity of 20.6040n+o(n) time and space. See Remark 6.10. 4 The inequality is not obvious. We sketch the proof for R < 1/ ln 2 which is only relevant to our analysis. In this case, dropping the second term from the minimum gives g2 (R) ≥ 1 − supx≥1 (log2 β + log2 x − Rx2 /2). The supremum is attained at √ x = 1/ R ln 2, and the resulting lower bound equals g(R).

21

Proof. We first bound the number of short vectors in one coset modulo 2L. Fix a coset C ∈ L/2L and put SC (x) := {w ∈ C \ {0} : ∥w∥ ≤ xλ} , m := |SC (x)|.  q  2 1 For every w ∈ SC (x), define uw := xλ w, x2 λ2 − ∥w∥ ∈ Rn+1 . Then ∥uw ∥ = 1. If w, w′ ∈ SC (x) are distinct, then (w − w′ )/2 is a nonzero vector in L, and hence ∥w − w′ ∥ ≥ 2λ. It follows that ∥w − w′ ∥ 2 1 2 2 ≥ =⇒ ⟨uw , uw′ ⟩ = 1 − ∥uw − uw′ ∥ ≤ 1 − 2 . xλ x 2 x √ Suppose first that 1 ≤ x ≤ 2. Then ⟨uw , uw′ ⟩ ≤ 0 for distinct w, w′ . Let G = (⟨uw , uw′ ⟩)w,w′ ∈SC (x) be the Gram matrix of these unit vectors. Since rank(G) ≤ n + 1 and tr(G) = m, the Cauchy-Schwarz inequality for the eigenvalues of G gives tr(G)2 m2 2 ∥G∥F ≥ ≥ . rank(G) n+1 ∥uw − uw′ ∥ ≥

2

On the other hand, −1 ≤ ⟨uw , uw′ ⟩ ≤ 0 for w ̸= w′ , and hence ⟨uw , uw′ ⟩ ≤ − ⟨uw , uw′ ⟩. Moreover, 2

X

0≤

uw

=m+

X

⟨uw , uw′ ⟩ .

′

w∈SC (x)

w,w ∈SC (x) w̸=w′

Consequently, X

2

∥G∥F = m +

2

⟨uw , uw′ ⟩ ≤ m −

w,w′ ∈SC (x) w̸=w′

X

⟨uw , uw′ ⟩ ≤ 2m.

w,w′ ∈SC (x) w̸=w′

2

o(n) Combining the two bounds . √ on ∥G∥F gives m ≤ 2(n + 1) = 2 Now consider x > 2. The preceding inner-product bound shows that the angle between every two
distinct vectors uw , uw′ is at least arccos 1 − 2/x2 . Applying Theorem 6.1 in dimension n + 1 gives

|SC (x)| ≤ 2(K2 (x)+o(1))n . Combining two cases, each coset modulo 2L contains 2(K2 (x)+o(1))n vectors of norm ≤ xλ for every fixed x ≥ 1. Summing over 2n cosets modulo 2L, giving 2(1+K2 (x)+o(1))n . Together with Lemma 2.1, we have NL (xλ) ≤ 2(min{log2 β+log2 x,1+K2 (x)}+o(1))n = 2A(x)n+o(n) for A(x) = min{log2 β + log2 x, 1 + K2 (x)}. We now estimate the Gaussian mass. Put xk = (1 + 1/n)k and 2 2 Sk := {w ∈ L : xk λ ≤ ∥w∥ < xk+1 λ} . Using ρ2√2/ξR (w) = 2−(R/2)n∥w∥ /d , we have ρ2√2/ξR (L \ {0}) ≤

X

2

2

2

NL (xk+1 λ)2−(R/2)n(λ /d )xk .

k≥0

Fix δ > 0 and a constant X0 > 1. Partition [1, X0 ] into finitely many intervals [a, b] such that R(b2 −a2 )/2 ≤ δ. For each interval, consider w ∈ L satisfying aλ ≤ ∥w∥ < bλ. Their number is at most 2(A(b)+o(1))n , while 2 2 2 each of their Gaussian weights is at most 2−(R/2)n(λ /d )a . Hence their total contribution is at most 2 2(A(b)−Ra /2+o(1))n ≤ 2(supx≥1 FR (x)+δ+o(1))n

where FR (x) := A(x) − R2 x2 . The last upper bound is independent of the interval, and the number of intervals in the decomposition of [1, X0 ] is independent of n, so their total contribution satisfies the same bound. 22

It remains to consider xk > X0 . Here we use only Lemma 2.1. Apart from its uniform 2o(n) factor, the upper bound for the k-th shell is 2

2

2

Uk := β n xnk+1 2−(R/2)n(λ /d )xk

2 2 2 Uk+1 ≤ e 2−R(λ /d )xk (1+1/(2n)) Uk

=⇒

since xk+1 = (1 + 1/n)xk . Choose X0 sufficiently so large that this ratio is at most 1/2 for all sufficiently large n and simultaneously the first such shell is bounded by 2(supx≥1 FR (x)+δ+o(1))n , which is possible because log2 β + log2 x − Rx2 /2 tends to −∞ as x → ∞. The bounds for the remaining shells form a geometric series and hence have the same total upper bound. Letting δ tend to zero gives ρ2√2/ξR (L \ {0}) ≤ 2(supx≥1 FR (x)+o(1))n = 2(1−g2 (R)+o(1))n , where the last equality follows from Eq. (24). The following lemma shows a spectral phenomena for the Hessian, or more precisely its translated version A in Eq. (11), similar to Lemma 3.4 even if r < t0 = 0.23147 . . .. We choose the lower bound 9/50 = 0.18 only to ensure 
1 BKL (arccos 1 − 2/x2 ) − r(x2 − 1) < − , 10 x≥ 3 sup √

(25)

√
which follows by standard calculus. Also note that BKL (arccos 1 − 2/x2 ) is Lipschitz in the interval [ 3, 7]. 2π 2 ξ 4 λ2

2

2

We define µr,d = ρ1/ξ r(L) e−πξr λ /4 for any r. r

Lemma 6.4. Let λ = λ1 (L) ≤ d ≤ (1 + 1/n)λ. Let v ∈ L satisfy ∥v∥ = λ, let u ∈ Fn2 satisfy v ∈ Bu + 2L, and put vb = v/λ. If r ≥ 9/50, then Ar,d (u) − µr,d vbvbT

F

≤ µr,d 2−Ω(n) .

Proof. The terms w = ±v in Eq. (11) give µr,d vbvbT . The sum of the other terms is positive semidefinite, so its Frobenius norm is at most its trace. Consequently, 2  Ar,d (u) − µr,d vbvbT F 2 2 2 1 X ∥w∥ 2−rn(λ /d )((∥w∥/λ) −1) . ≤ µr,d 2 λ w∈v+2L w̸=±v

Put xk :=

√

n o 3(1 + 1/n)k and let Sk := w ∈ v + 2L \ {±v} : xk ≤ ∥w∥ < x . Then k+1 λ 1 2

X w∈v+2L w̸=±v



∥w∥ λ

2

2

2

2

2−rn(λ /d )((∥w∥/λ) −1) ≤

2 2 2 1X |Sk |x2k+1 2−rn(λ /d )(xk −1) . 2

k≥0

We will show that the summations for xk < 7 and xk ≥ 7 both are bounded above by 2−Ω(n) . First, if xk < 7, Lemma 6.2 gives the bound  
2 2 2 1 rλ2 (x2k − 1) log2 |Sk |x2k+1 2−rn(λ /d )(xk −1) ≤ (BKL (arccos 1 − 2/x2k+1 ) + o(1)) − n d2
and using the fact that BKL (arccos 1 − 2/x2 ) is Lipschitz, xk+1 = xk + xk /n = xk + O(1/n) for xk < 7, and d/λ = 1 + O(1/n) gives an upper bound
1 BKL (arccos 1 − 2/x2k ) − r(x2k − 1) + o(1) ≤ − + o(1) 7 23

2

2

2

where we use Eq. (25), proving 12 |Sk |x2k+1 2−rn(λ /d )(xk −1) ≤ 2(−1/7+o(1))n . Since there are at most O(n) k’s such that xk < 7, it gives the desire bound for the first summand over xk < 7. Now consider xk ≥ 7. Since d ≤ (1 + 1/n)λ, rλ2 /d2 ≥ 1/6 for sufficiently large n. Lemma 2.1 on |Sk | gives   2 2 2 x2 − 1 1 log2 |Sk |2−rn(λ /d )(xk −1) ≤ log2 β + log2 xk+1 − k + o(1) n 6 Since xk+1 = (1 + 1/n)xk ≤ 2xk , the exponent is at most 1 x2 log2 β + log2 (2xk ) − (x2k − 1) + o(1) ≤ − k + o(1) 6 14 which holds for xk ≥ 7. Applying this inequality with x = xk proves x2 2 2 2 2 1 |Sk |x2k+1 2−rn(λ /d )(xk −1) ≤ k+1 2−nxk /14+o(n) . 2 2 This term (ignoring the uniform o(1) factor) decays (super-)exponentially fast,5 thus the asymptotic bound of the summation of the above term for k such that xk ≥ 7 becomes 2−Ω(n) .

6.2

Sampling (wider) discrete Gaussian from an affine lattice coset

This section shows that sampling from the discrete Gaussian DΛj ,ξR for a large ξR is more efficient than the χ one in Lemma 5.4 by removing the multiplicative p factor 2 in the time complexity. For the fixed d and R, recall that ξR = 4nR ln 2/(πd2 ). For P ∈ GLn (F2 ) and j ∈ Fh2 , recall from Section 5.2 that Λj := {X ∈ L∗ : JP (X) = j}. In particular, Λ0 is a sublattice of L∗ and Λj is a coset of Λ0 . The following lemma shows some Gaussian mass bound from Corollary 3.2 works for Λ0 in expectation. Lemma 6.5. Let λ = λ1 (L) and λ ≤ d ≤ (1+1/n)λ. If R > t0 and χ < g2 (R), then ρ√2/ξR (Λ∗0 \{0}) ≤ 2−Ω(n) √ with probability 1 − 2−Ω(n) over uniform P ∈ GLn (F2 ). Consequently, ξR > 2 η1/2 (Λ0 ). Proof. Let KP = P −1 (Fh2 × {0}). We first observe that Λ∗0 = L + BKP /2. For every nonzero κ ∈ Fn2 , it is easy to see that PP [κ ∈ KP ] = (2h − 1)/(2n − 1). Since the cosets L + Bκ/2 for κ ∈ Fn2 partition L/2, we have   EP ρ√2/ξR (Λ∗0 \ {0}) ≤ ρ√2/ξR (L \ {0}) + 2h−n+o(n) ρ2√2/ξR (L) − ρ√2/ξR (L) ≤ 2(−g(R)+o(1))n + 2(χ−g2 (R)+o(1))n . The last inequality follows from Eq. (16) with c = 0 and Lemma 6.3. Since χ < g2 (R) and R > t0 , Markov’s inequality in Lemma 2.9 gives ρ√2/ξR (Λ∗0 \ {0}) = 2−Ω(n) < 1/2 except with probability 2−Ω(n) . The last claim follows from the definition and monotonicity of the smoothing parameter. Given this lemma, we can apply Theorem 2.7 to sample the discrete Gaussian on Λj . More precisely, we define Γ := Λ0 + Zx = Λ0 ⊔ Λj for j ̸= 0 and x ∈ Λj , and run the algorithm from Theorem 2.7 on Γ. Collecting the samples in Λj works well. This gives the following lemma. Lemma 6.6. Let λ = λ1 (L), λ ≤ d ≤ (1 + 1/n)λ, χ < g2 (R), R > t0 , and M = 2O(n) . With probability 1 − 2−Ω(n) over uniform P ∈ GLn (F2 ), the following holds for every j ∈ Fh2 . There is an algorithm that outputs M vectors or aborts, and its abort probability is at most 2−Ω(n)
. If itMdoes not abort, the joint distribution of its outputs has statistical distance at most exp −Ω(n2 ) from DΛ . The algorithm takes j ,ξR n/2 o(n) n/2+o(n) time (M + 2 )2 and space 2 . 5 In particular, for x

2

2

2

2 −nxk+1 /14 2 )/(x2k+1 2−nxk /14 ) = (1 + 1/n)2 2−nxk+1 (2/n−1/n )/14 ≤ 1/2 holds. k ≥ 7, (xk+2 2

24

√ Proof. Note that ρ√2/ξR (Λ∗0 \ {0}) ≤ 2−Ω(n) and ξR > 2 η1/2 (Λ0 ) holds except with probability 2−Ω(n) over P because of Lemma 6.5. Fix any such P . For j = 0, we can directly use Theorem 2.7 ⌈M/2n/2 ⌉ times to Λ0 with parameter ξR and κ = n2 . Suppose that j ̸= 0. Solve the linear equations JP (x) = j over F2 and lift a solution to obtain x ∈ L∗ satisfying √ x ∈ Λj . Let Γ := Λ0 + Zx = Λ0 ⊔ Λj . Since Γ∗ ⊆ Λ∗0 , we have ρ√2/ξR (Γ∗ \ {0}) ≤ 2−Ω(n) , and hence ξR > 2 η1/2 (Γ) for large n. Choose arbitrary y ∈ Λ∗0 \ Γ∗ . Poisson summation formula gives EX∼DΓ,ξR e2πi⟨X,y⟩ =

ρ1/ξR (Γ∗ − y) ≤ ρ√2/ξR (Λ∗0 \ {0}) = 2−Ω(n) . ρ1/ξR (Γ∗ )

The character e2πi⟨X,y⟩ equals 1 for every X ∈ Λ0 . Moreover, 2x ∈ Λ0 , while y ∈ / Γ∗ , so ⟨x, y⟩ ∈ Z + 1/2. Hence the character equals −1 for every X ∈ x + Λ0 = Λj . The above inequality gives |1 − 2p| ≤ 2−Ω(n) , where p = PX∼DΓ,ξR [X ∈ Λj ]. It follows that p = 1/2 + O(2−Ω(n) ). We obtain the following sampling algorithm: Use Theorem 2.7 on Γ to generate 4(M + n) candidates, with parameter ξR and κ = n2 . Collect the first M candidates in Λj and abort if fewer than M are obtained. The Chernoff bound in Lemma 2.12 gives abort probability 2−Ω(n) . O(n) For exact samples from DΓ,ξR , conditioning on X ∈ Λj gives exactly
DΛj ,ξR . There are at most 2 2 calls to Theorem 2.7, so their total statistical distance is still exp −Ω(n ) . Applying the collection algorithm does not increase statistical distance, and conditioning on its non-abort event changes it by at most a factor 1 + 2−Ω(n) . Finally, the calls can be made sequentially, giving time (M + 2n/2 )2o(n) and space 2n/2+o(n) .

6.3

Estimating the Hessian by importance sampling

Importance sampling estimates an expectation under a target distribution using samples from another distribution. Here we sample from DΛj ,ξR for large ξR and estimate the Hessian defined using DΛj ,ξr for the smaller target ξr . For X ∈ Λj , let w(X) := ρξr (X)/ρξR (X) and wj := EX∼DΛj ,ξR [w(X)] = ρξr (Λj )/ρξR (Λj ). For every matrix-valued function H for which the expectations exist, EX∼DΛj ,ξR [w(X)H(X)] =

X ρξ (X) ρξ (X) r R H(X) = wj EX∼DΛj ,ξr [H(X)]. ρξR (Λj ) ρξR (X)

(26)

X∈Λj

Thus the weighted expectation is wj Gr,d,j (θ) when H(X) = −4π 2 XX T (−1)θ·VP (X) . Let M be the number of sample to be determined later. Consider n independent families {Xa,1 , . . . , Xa,M } of samples from DΛj ,ξR for a ∈ [n]. Define the importance-sampling Hessian estimator M 2 X

ba,j (θ) := − 4π N M

T w(Xa,i )Xa,i Xa,i (−1)θ·VP (Xa,i ) 1{∥Xa,i ∥≤C1 ξR √n} .

(27)

i=1

bj (θ) to be the median (i.e., (⌊n/2⌋ + 1)-st smallest) among the For p, q ∈ [n], define the (p, q)-entry of N b b bj (θ) approximates corresponding entries of N1,j (θ), . . . , Nn,j (θ). We will show the median estimator N wj Gr,d,j (θ) well for uniform random P and j. We need some notations. Define s > 0 by 1/s = 2/r − 1/R. Then 1 2 1 = 2− 2, ξs2 ξr ξR

ρξr (X)2 = ρξs (X), ρξR (X)

s=

rR < r < R. 2R − r

(28)

We also recall µ from Eq. (12), and choose the number of samples M using ι defined below: µr,d =

2π 2 ξr4 λ2 −πξr2 λ2 /4 e , ρ1/ξr (L)

M = ⌈n6 2(ι(r,R)+2r)n ⌉

where µr,d = Θ(ξr4 λ2 2−rn ) if λ ≤ d ≤ (1 + 1/n)λ and s > t0 /2. 25

for

ι(r, R) :=

1 R2 log2 2 r(2R − r)

(29)

Lemma 6.7. Let λ = λ1 (L) and λ ≤ d ≤ (1 + 1/n)λ. If s > t0 /2 and χ < 1/2 + g(r), then, the following hold with probability 1 − O(n−1 ) over uniform random P ∈ GLn (F2 ) and j ∈ Fh2 : ζr,j ≥

1 , 2

wj =

 r n/2  R

EX∼DΛj ,ξR [w(X)2 ]

 1 + O(2−Ω(n) ) ,

w2j

≤ 2n2ι(r,R)n .

Proof. Since s > t0 /2 and s < r < R, Corollary 3.2 gives ρ1/ξs (L), ρ1/ξr (L), ρ1/ξR (L) = 1 + 2−Ω(n) . Since g is increasing, Lemma 5.3 gives ζr,j , ζR,j = 1 + O(2−Ω(n) ) simultaneously for every j, except with probability 2−Ω(n) over P . In particular, ζr,j ≥ 1/2 for all sufficiently large n. By the definitions of wj and ζt,j , and by applying the Poisson summation formula to L∗ , we have wj =

  r n/2 ρ  r n/2  ζr,j ρξr (L∗ ) 1/ξr (L) ζr,j −Ω(n) 1 + O(2 ) = = ζR,j ρξR (L∗ ) R ρ1/ξR (L) ζR,j R

where we use the approximations of ρ and ζ above. This proves the estimate of wj in the statement. P 2 Fix a choice of P satisfying the preceding conclusions. Since 2−h j ζs,j = 1 and ζR,j /ζr,j = 1 + 2−Ω(n) 2 −Ω(n) uniformly in j, the expectation over uniform j of ζs,j ζR,j /ζr,j is 1 + 2 . Markov’s inequality gives ζs,j ζR,j ≤n 2 ζr,j except with probability O(n−1 ) over uniform j. The definitions of w(X) and DΛj ,ξR , together with Eq. (28), give EX∼DΛj ,ξR [w(X)2 ] =

X ρξ (X)2 ρξ (Λj ) 1 r = s . ρξR (Λj ) ρξR (X) ρξR (Λj ) X∈Λj

Also, wj = ρξr (Λj )/ρξR (Λj ). Consequently, we can compute EX∼DΛj ,ξR [w(X)2 ]/w2j as follows: ρξs (L∗ )ρξR (L∗ ) ζs,j ζR,j ρξs (Λj )ρξR (Λj ) = = 2 ρξr (Λj )2 ρξr (L∗ )2 ζr,j



sR r2

n/2

ρ1/ξs (L)ρ1/ξR (L) ζs,j ζR,j . 2 ρ1/ξr (L)2 ζr,j

Here the first equality follows by writing ρξt (Λj ) = 2−h ζt,j ρξt (L∗ ), and the p second equality is obtained by applying Poisson summation to L∗ . Plugging s = rR/(2R − r) and R/ r(2R − r) = 2ι(r,R) gives the multiplicative factor 2ι(r,R)n . The last two factors are at most 2 and n, respectively, for all sufficiently large n. This proves the result. Lemma 6.8. Let λ = λ1 (L) and λ ≤ d ≤ (1 + 1/n)λ. If s > t0 /2 and χ < 1/2 + g(r), then it holds simultaneously for every θ ∈ Fℓ2 :   wj µr,d bj (θ) − wj Gr,d,j (θ) max N =O n op θ∈Fℓ2 with probability 1 − O(n−1 ) over P, j, and the choices of Xa,i . Proof. Suppose that the conclusions of Lemma 6.7 hold, and fix the corresponding pair P, j. For every a, the ba,j (θ) is independent of a. From Eqs. (26) and (27), we have expectation of N h i T θ·VP (X) √ ba,j (θ)] = −4π 2 wj EX∼D E[N XX (−1) 1 {∥X∥≤C1 ξR n} . Λj ,ξr Consequently,   h i bj (θ) − wj Gr,d,j (θ) = N bj (θ) − E[N ba,j (θ)] + 4π 2 wj EX∼D N XX T (−1)θ·VP (X) 1{∥X∥>C1 ξR √n} . Λj ,ξr 26

We bound the two terms separately. We first bound the first term by applying Chebyshev’s inequality to each entry. Fix a, θ and the entry ba,j (θ))p,q = M −1 PM Yi by defining indices p, q. Write (N i=1 Yi := −4π 2 w(Xa,i )(Xa,i )p (Xa,i )q (−1)θ·VP (Xa,i ) 1{∥Xa,i ∥≤C1 ξR √n} . This gives the following upper bound  E

M 2   1 1 X  ba,j (θ) − E[N ba,j (θ)] E (Yi − E[Yi ])2 ≤ E[Y12 ]. N = 2 M i=1 M p,q

where the cross terms between Yi − E[Yi ] and Yk − E[Yk ] vanish for i ̸= k since the Yi are independent. Consequently,  2    1 b b E Na,j (θ) − E[Na,j (θ)] ≤ EX∼DΛj ,ξR w(X)2 (4π 2 Xp Xq )2 1{∥X∥≤C1 ξR √n} . M p,q 4 2 When the indicator is nonzero, (4π 2 Xp Xq )2 = O(ξR n ) = O(ξr8 λ4 ). Hence

 E

 8 4  2  ξr λ 2 b b Na,j (θ) − E[Na,j (θ)] =O EX∼DΛj ,ξR [w(X) ] = O M p,q

nw2j ξr8 λ4 2ι(r,R)n M

! =O

w2j µ2r,d n5

!

where we use E[w(X)2 ] ≤ 2nw2j 2ι(r,R)n from Lemma 6.7 and the definition of µr,d and M from Eq. (29). Chebyshev’s inequality now gives    wj µr,d b b > Na,j (θ) − E[Na,j (θ)] P = O(n−1 ). n2 p,q Thus each of the n independent estimates of the (p, q)-entry has the required accuracy with probability 1 − O(n−1 ). If more than half of them have this accuracy, then their median has the same accuracy. By Lemma 2.13, the probability that the median does not have this accuracy is 2−Ω(n log n) . A union bound over θ ∈ Fℓ2 and p, q ∈ [n], together with ∥A∥op ≤ n maxp,q |Ap,q |, therefore gives  bj (θ) − E[N ba,j (θ)] max N θ∈Fℓ2

=O op

wj µr,d n



except with probability 2−Ω(n log n) . It remains to bound the second term. Since ζr,j ≥ 1/2 and its definition ζr,j = 2h ρξr (Λj )/ρξr (L∗ ), we have ρξr (Λj ) ≥ 2−h−1 ρξr (L∗ ). Since ξR > ξr , Lemma 2.8 shows that the operator norm of the second term in the decomposition is at most 4π 2 wj 2h+1 ξr2 n2−n . Dividing this bound by wj µr,d /n gives an upper bound O(n2h−(1−r)n ) = 2−Ω(n) , because h ≤ n/2 and r < 1/4. Therefore, the second term is much smaller: i h 4π 2 wj EX∼DΛj ,ξr XX T (−1)θ·VP (X) 1{∥X∥>C1 ξR √n} = o(wj µr,d /n). op

Combining the two terms proves the lemma. The total failure probability is the summand of O(n−1 ) from Lemma 6.7 and the additional failure probability 2−Ω(n log n) .

6.4

Recovering a shortest vector

The following lemma is almost identical to Lemma 5.7, except that we have a normalizing factor wj and we use Lemma 6.4 instead of Lemma 3.4.

27

Lemma 6.9. Let λ = λ1 (L) ≤ d ≤ (1 + 1/n)λ. Let v ∈ L satisfy ∥v∥ = λ, and let u∗ ∈ Fn2 satisfy v ∈ Bu∗ + 2L. Choose independent uniform P ∈ GLn (F2 ) and j ∈ Fh2 , and write P u∗ = (α∗ , θ∗ ). Assume that r ≥ 9/50, χ < 1/2 + g(r), χ − 1 − min{g(r), 2g(r)} + 2r < 0 and that the conclusion of Lemma 6.8 holds. The following holds with probability 1 − O(n−1 ) over P and j: Let q+ and q− be unit eigenvectors bj (θ∗ ), respectively. Then there are s ∈ {+, −} and corresponding to the largest and smallest eigenvalues of N τ ∈ {−1, 1} such that ∥qs − τ v/λ∥ = O(n−1/2 ). Consequently, the n−1/3 -BDD query at dqs returns τ v for all sufficiently large n. σ = (−1)α∗ ·j . By Lemma 6.4, Ar,d (u∗ ) = µr,d vbvbT + R, where ∥R∥F ≤ µr,d 2−Ω(n) . Proof. Put vb P= v/λ andj·(α−α ∗) Let SP,j := α̸=α∗ (−1) Ar,d (P −1 (α, θ∗ )). The calculation in the proof of Lemma 5.7, with t replaced by r, together with Lemma 5.2, gives 2

EP,j ∥SP,j ∥F ≤ µ2r,d 2(χ−1−min{g(r),2g(r)}+2r+o(1))n . The exponent is negative by assumption. Hence Markov’s inequality gives ∥SP,j ∥F ≤ µr,d 2−Ω(n) , except with probability 2−Ω(n) over P, j. By Lemma 5.3, ζr,j = 1 + O(2−Ω(n) ), except with probability 2−Ω(n) over P . Applying Lemma 5.6 and substituting the expressions for Ar,d (u∗ ) and SP,j , and then applying Lemma 6.8, gives, for some a ∈ R,   wj µr,d bj (θ∗ ) = aIn + wj µr,d vbvbT + E, σN . ∥E∥op = O ζr,j n If σ = 1, let q = q+ , and otherwise let q = q− . The remainder proof is identical to Lemma 5.7 except that we use wj µr,d /ζr,j instead of µt,d /ζt,j .

6.5

The importance-sampling algorithm

This section presents the algorithm using importance sampling. The time complexity is determined by the bj (θ), indexed 2(ι(r,R)+2r)n+o(n) samples used in Lemma 6.8 and the 2ℓ+o(n) = 2(1−χ)n+o(n) matrices, e.g., N ℓ by θ ∈ F2 . The space complexity is determined by the samples and these matrices. We choose the following parameters r = 0.2222355,

R = 0.400613,

χ = 0.3961331, 2

rR R which gives s = 2R−r = 0.1537683785 . . . and ι(r, R) = 12 log2 r(2R−r) = 0.1593947534 . . .. A direct numerical calculation shows that all the conditions of Lemmas 6.4, 6.6, 6.8 and 6.9, and   1 max , ι(r, R) + 2r, 1 − χ < 0.603867. (30) 2

Remark 6.10. Without the refined bound in Lemma 6.3, the source-coset sampling argument requires χ < g(R). Choose r = 0.222275, R = 0.400765, and χ = 0.395965. Then g(R) = 0.395965 . . . > χ,

ι(r, R) + 2r = 0.604035 . . . ,

1 − χ = 0.604035.

These values satisfy the other assumptions of the algorithm. Therefore, using g(R) instead of g2 (R) gives time and space 20.60404n+o(n) .

28

Algorithm 4: Importance-sampling affine-coset Hessian SVP 1. Construct the preprocessing n−1/3 -BDD data and the scale grid from Algorithm 1. 2. At every scale d, choose independent uniform P ∈ GLn (F2 ) and j ∈ Fh2 . Put M = ⌈n6 2(ι(r,R)+2r)n ⌉ and apply the sampling algorithm from Lemma 6.6. Abort the scale unless nM samples from DΛj ,ξR are obtained, and divide them into n families {Xa,1 , . . . , Xa,M }, a ∈ [n]. 3. For every a ∈ [n], construct the matrix-valued array Aa (y) := −

4π 2 M

X

T w(Xa,i )Xa,i Xa,i 1{∥Xa,i ∥≤C1 ξR √n} ,

y ∈ Fℓ2 .

1≤i≤M VP (Xa,i )=y

4. Apply the matrix-valued Walsh-Hadamard transform to each Aa . For every θ ∈ Fℓ2 , the output satisfies X ba,j (θ). (−1)θ·y Aa (y) = N (31) y∈Fℓ2

bj (θ) by taking the median of the corresponding entries of N b1,j (θ), . . . , N bn,j (θ). Define N 5. For every θ ∈ Fℓ2 , compute unit eigenvectors q+ and q− corresponding to the largest and smallest bj (θ) and query BDD at dq± . Store a nonzero output in L. Keep only the shortest vector eigenvalues of N found and discard the other vectors and temporary data. 6. Return the shortest vector over all scales. Theorem 6.11. Algorithm 4 solves Search-SVP with constant success probability in time 20.60387n+o(n) and space 20.60387n+o(n) . Proof. Suppose λ1 (L) ≤ d ≤ (1 + 1/n)λ1 (L) and let v be a shortest vector. We can ignore the other d’s as before. Choose u∗ ∈ Fn2 such that v ∈ Bu∗ + 2L, and write P u∗ = (α∗ , θ∗ ).
By Lemma 6.6, the algorithm obtains samples whose joint distribution is exp −Ω(n2 ) -close to independent ba,j (θ) for every a ∈ [n] and samples from DΛj ,ξR . By Eq. (31), the Walsh-Hadamard transforms compute N ℓ b θ ∈ F2 . Their entrywise medians are therefore the matrices Nj (θ) defined in Section 6.3. The conclusion of Lemma 6.8 holds simultaneously for every θ ∈ Fℓ2 , and Lemma 6.9 shows that one of the two BDD queries corresponding to θ∗ returns
one of ±v. The statistical distance in Lemma 6.6 changes the success probability by at most exp −Ω(n2 ) . Since every stored vector is verified to be a nonzero vector in L, the shortest stored vector has norm λ1 (L). We analyze the complexity. Generating and processing the samples takes 2(max{1/2,ι(r,R)+2r}+o(1))n time by Lemma 6.6. Constructing the arrays takes nM poly(n) time. Their Walsh-Hadamard transforms (Lemma 4.1), the entrywise medians, the eigenvector computations, and the BDD queries take 2ℓ+o(n) = 2(1−χ)n+o(n) time. Hence the time exponent is 0.60387 as in Eq. (30). The Gaussian samples use 2(ι(r,R)+2r)n+o(n) space, the arrays and their transforms use 2(1−χ)n+o(n) space, and the sampling algorithm uses 2n/2+o(n) space. Thus the space exponent is bounded by the same maximum in Eq. (30). This proves the claimed time and space bounds.

6.6

Reducing the space by sparsification

We use the same parameters as in the previous section. Choose independent uniform P ∈ GLn (F2 ) and j ∈ Fh2 . The algorithm in Section 6.5 stores n arrays indexed by Fℓ2 of size 2ℓ = 20.60387n+o(n) . To reduce the space, we randomly and sparsely select some of the samples before applying the Walsh-Hadamard transform, and they are only used in the later steps.

29

More precisely, we do the following. For X ∈ Λj , define   w(X) . π(X) := min 1, ι(r,R)n 2 (r/R)n/2

(32)

Note that all terms are efficiently computable. Conditional on each sampled X, independently choose Z ∈ {0, 1} such that Pr[Z = 1 | X] = π(X) and Pr[Z = 0 | X] = 1 − π(X). We use the following: For every function f for which the expectation exists,      Zf (X) Zf (X) EX,Z X = EX [f (X)]. (33) = EX E π(X) π(X) Let M = ⌈n6 2(ι(r,R)+2r)n ⌉, and take n independent families {Xa,1 , . . . , Xa,M }, a ∈ [n], of samples from DΛj ,ξR . Conditional on these samples, let the Za,i be independent random variables such that Za,i = 1 with probability π(Xa,i ) and Za,i = 0 otherwise. Define the sparsified estimator M 2 X

b sp (θ) := − 4π N a,j M

Za,i w(Xa,i ) T Xa,i Xa,i (−1)θ·VP (Xa,i ) 1{∥Xa,i ∥≤C1 ξR √n} . π(X ) a,i i=1

(34)

Because of Eq. (33), the expectation of this sparsification is the same as the expectation of the original b sp (θ) by taking the median among the corresponding entries of Eq. (27). For each matrix entry, define N j b sp (θ), . . . , N b sp (θ). N 1,j n,j The factor 1/π(Xa,i ) compensates for selecting a sample with probability π(Xa,i ): conditional on Xa,i , the expectation of Za,i w(Xa,i )/π(Xa,i ) is w(Xa,i ). Lemma 6.12. Let λ = λ1 (L) and λ ≤ d ≤ (1 + 1/n)λ. Then, the following holds for all θ ∈ Fℓ2 :   wj µr,d sp b max Nj (θ) − wj Gr,d,j (θ) =O n op θ∈Fℓ2 with probability 1 − O(n−1 ) over P, j, the samples Xa,i , and the variables Za,i . Proof. Fix P, j for which the conclusion of Lemma 6.7 holds, which happens with probability 1 − O(n−1 ). For fixed a, let EXa denote expectation over the independent samples Xa,1 , . . . , Xa,M ∼ DΛj ,ξR . Let EXa ,Za additionally include the conditionally independent choices Za,i | Xa,i ∼ Bernoulli(π(Xa,i )). b sp (θ)] = EX [N ba,j (θ)]. Consequently, By Eq. (33), EXa ,Za [N a a,j b sp (θ) − wj Gr,d,j (θ) = N b sp (θ) − EX ,Z [N b sp (θ)] + EX [N ba,j (θ)] − wj Gr,d,j (θ). N a a a j j a,j ba,j (θ)] − wj Gr,d,j (θ) is o(wj µr,d /n). We The proof of Lemma 6.8 shows that the operator norm of EXa [N bound the first difference using the same concentration argument. By the definition of π(X) and 1/π(X) = max(1, 2ι(r,R)n (r/R)n/2 /w(X)) ≤ 1 + 2ι(r,R)n (r/R)n/2 /w(X), " 2 # Zw(X) w(X)2 EZ|X = ≤ w(X)2 + 2ι(r,R)n (r/R)n/2 w(X), π(X) π(X) where Z | X ∼ Bernoulli(π(X)). In the proof of Lemma 6.8, we proved that 4π 2 XX T F = O(ξr4 λ2 ) if √ {∥X∥ ≤ C1 ξR n}. Hence Lemma 6.7, together with EX∼DΛj ,ξR [w(X)] = wj = (r/R)n/2 (1 + O(2−Ω(n) )), gives " # 2   Zw(X) 2 T 2 √ 4π XX F 1{∥X∥≤C1 ξR n} = O nw2j ξr8 λ4 2ι(r,R)n . E X∼DΛj ,ξR π(X) Z|X∼Bernoulli(π(X))

30

For fixed a, θ, p, q, the estimator entry is the average of M independent summands. Therefore, !  2  w2j µ2r,d sp sp b (θ)] b (θ) − EX ,Z [N =O EXa ,Za N a a a,j a,j n5 p,q by the definitions of M and µr,d in Eq. (29). This is the same bound used in the proof of Lemma 6.8. Applying its Chebyshev, median, and union-bound arguments proves the required operator-norm bound simultaneously for every θ ∈ Fℓ2 . The failure probability in Lemma 6.7 is O(n−1 ). The next lemma bounds the number of samples for which Za,i = 1. Lemma 6.13. Under the hypotheses of Lemma 6.12, with probability 1 − O(n−1 ) over P, √ j, the samples Xa,i , and the variables Za,i , the number of pairs (a, i) satisfying Za,i = 1 and ∥Xa,i ∥ ≤ C1 ξR n is at most n8 22rn . Proof. Since π(X) ≤ w(X)/(2ι(r,R)n (r/R)n/2 ), Lemma 6.7 gives EX∼DΛj ,ξR [π(X)] ≤

  wj −ι(r,R)n −Ω(n) 1 + O(2 = 2 ) . 2ι(r,R)n (r/R)n/2

The expected number of pairs satisfying Za,i = 1 is therefore O(nM 2−ι(r,R)n ) = O(n7 22rn ). The norm condition can only decrease this number. Markov’s inequality proves the lemma.

6.7

Space-efficient implementation

Now we introduce an algorithm with the reduced space complexity. For every importance-weighted sample, we choose the random variable Z using Eq. (32) and store the sample only if Z = 1. The division by π(X) preserves the expectation of its contribution. By Lemma 6.13, the number of stored samples is 22rn+o(n) . We choose the same parameters r, R, χ as before, satisfying the conditions of all the lemmas and Eq. (30). The time complexity remains 20.60387n+o(n) . Generating and selecting the samples takes 2(ι(r,R)+2r)n+o(n) time, and all the Walsh-Hadamard transforms and the examination of all matrices take 2ℓ+o(n) = 2(1−χ)n+o(n) time. The space complexity becomes 2n/2+o(n) , because the stored samples use 22rn+o(n) space for 2r < 1/2, and only 2⌊n/2⌋ matrices are processed at a time. Algorithm 5: Space-efficient importance-sampling SVP 1. Follow the first two √ steps of Algorithm 4, but process each sample Xa,i immediately and then discard it. If ∥Xa,i ∥ ≤ C1 ξR n, choose Za,i as in Eq. (32). When Za,i = 1, write ′ ′′ VP (Xa,i ) = (ka,i , ka,i ) ∈ Fb2 × Fℓ−b 2 , 4π 2 w(X

b = ⌊n/2⌋,

)

a,i ′ ′′ T 8 2rn and store (a, ka,i , ka,i , Wa,i ), where Wa,i := − M π(Xa,i ) Xa,i Xa,i . Abort the scale if more than n 2 tuples are stored.

2. For every θ′′ ∈ Fℓ−b and a ∈ [n], form 2 Aa,θ′′ (x) :=

′′

X

′′

(−1)θ ·k W,

x ∈ Fb2 .

(a,k′ ,k′′ ,W ) stored k′ =x

Apply the matrix-valued Walsh-Hadamard transform and take the entrywise median of the n outputs for each θ′ ∈ Fb2 . Perform the eigenvector and BDD steps of Algorithm 4, and discard the arrays before proceeding to the next θ′′ . 3. Keep the shortest verified vector over all scales. Repeat a sufficiently large constant number of times and return the shortest vector found.

31

Theorem 6.14. Algorithm 5 solves Search-SVP with success probability at least 2/3 in expected time 20.60387n+o(n) and space 2n/2+o(n) . Proof. The correctness follows from the proof of Theorem 6.11, replacing Lemma 6.8 by Lemma 6.12. The additional abort probability is O(n−1 ) by Lemma 6.13. The samples are discarded after selection step, so only 22rn+o(n) tuples are stored. For each fixed
the ′′ 2rn b o(n) θ , the algorithm takes 2 time and 2b+o(n) space. Therefore, since 2r < 1/2 and b = ⌊n/2⌋, +2 2
o(n) ℓ−b 2rn b 2 +2 2 the total time is 2 = 2(1−χ)n+o(n) . Together with the sampling time, this is 20.60387n+o(n) . The selected tuples, the arrays for one fixed θ′′ , the discrete Gaussian sampler, and the preprocessing BDD data use 2n/2+o(n) space. A constant number of repetitions gives success probability at least 2/3.

6.8

Quantum algorithm

We describe the quantum version of Algorithm 5 based on the quantum minimum finding algorithm [14]. The application is rather straightforward: We search for θ′′ ∈ Fℓ−b that minimizes the shortest vector 2 found by the preprocessing BDD algorithm. This reduces the complexity from 2ℓ−b+o(n) (22rn + 2b ) to 2(ℓ−b)/2+o(n) (22rn + 2b ). In the quantum version, the collected tuples (of size 22rn+o(n) ) and the preprocessing BDD advice (of size 2o(n) ) are stored in QRAM, which will be of size 22rn+o(n) at total. The overall steps for the Hessian estimation, eigenvector evaluations, and the BDD queries can be done reversibly. This gives the coherent oracle required by quantum minimum finding with only a 2o(n) multiplicative overhead. To maximize the speedup, we also choose b = ⌊2rn⌋ and other parameters by r = 0.180182,

R = 0.340429,

χ = 0.278262.

giving 20.54106n+o(n) time and 20.5n+o(n) space. Theorem 6.15. There is a quantum algorithm that solves Search-SVP with success probability at least 2/3 in expected time 20.54106n+o(n) and space 2n/2+o(n) . The QRAM size is 20.36036n+o(n) and 20.36036n+o(n) qubits.

References [1] Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, and Yixin Shen. Improved classical and quantum algorithms for the shortest vector problem via bounded distance decoding. SIAM Journal on Computing, 54(2):233–278, 2025. 3, 4, 7 [2] Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the shortest vector problem in 2n time using discrete Gaussian sampling: Extended abstract. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th ACM STOC, pages 733–742, Portland, OR, USA, June 14–17, 2015. ACM Press. 3, 4, 5, 7, 8, 9 [3] Divesh Aggarwal and Noah Stephens-Davidowitz. (Gap/S)ETH hardness of SVP. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, 50th ACM STOC, pages 228–238, Los Angeles, CA, USA, June 25–29, 2018. ACM Press. 3 [4] Dorit Aharonov and Oded Regev. Lattice problems in np ∩ conp. J. ACM, 52(5):749–765, September 2005. 3 [5] Dorit Aharonov and Oded Regev. Lattice problems in NP intersect coNP. Journal of the ACM, 52(5):749–765, 2005. 10 [6] Miklós Ajtai. The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In 30th ACM STOC, pages 10–19, Dallas, TX, USA, May 23–26, 1998. ACM Press. 3

32

[7] Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In 29th ACM STOC, pages 284–293, El Paso, TX, USA, May 4–6, 1997. ACM Press. 3 [8] Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In 33rd ACM STOC, pages 601–610, Crete, Greece, July 6–8, 2001. ACM Press. 3 [9] Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Robert Krauthgamer, editor, 27th SODA, pages 10–24, Arlington, VA, USA, January 10–12, 2016. ACM-SIAM. 3 [10] Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, and João Ribeiro. Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all ℓp norms. In Barna Saha and Rocco A. Servedio, editors, 55th ACM STOC, pages 553–566, Orlando, FL, USA, June 20–23, 2023. ACM Press. 3 [11] Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardness of learning with errors. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, pages 575–584, Palo Alto, CA, USA, June 1–4, 2013. ACM Press. 3 [12] Yanlin Chen, Kai-Min Chung, and Ching-Yi Lai. Space-efficient classical and quantum algorithms for the shortest vector problem. Quantum Info. Comput., 18(3–4):283–305, March 2018. 3 [13] Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. On the closest vector problem with a distance guarantee. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 98–109, 2014. 3, 10 [14] Christoph Durr and Peter Hoyer. A quantum algorithm for finding the minimum, 1999. 6, 32 [15] Yiming Gao, Yansong Feng, and Honggang Hu. Solving the shortest vector problem in 20.7314n+o(n) time via discrete gaussian sampling on superlattices. Cryptology ePrint Archive, Paper 2026/1587, 2026. 3 [16] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 197–206, Victoria, BC, Canada, May 17–20, 2008. ACM Press. 3 [17] Guillaume Hanrot and Damien Stehlé. Improved analysis of kannan’s shortest lattice vector algorithm. In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 170–186, Santa Barbara, CA, USA, August 19–23, 2007. Springer Berlin Heidelberg, Germany. 3 [18] Ishay Haviv and Oded Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In David S. Johnson and Uriel Feige, editors, 39th ACM STOC, pages 469–477, San Diego, CA, USA, June 11–13, 2007. ACM Press. 3 [19] Grigorii Anatolévich Kabatiansky and Vladimir Iosifovich Levenshtein. On bounds for packings on a sphere and in space. Problemy peredachi informatsii, 14(1):3–25, 1978. 6, 21 [20] Ravi Kannan. Improved algorithms for integer programming and related lattice problems. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 193–206, 1983. 3 [21] Subhash Khot. Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789–808, September 2005. 3 [22] Jiseung Kim, 2026. Personal communication. 3, 6 [23] J. C. Lagarias and A. M. Odlyzko. Solving low-density subset sum problems. J. ACM, 32(1):229–246, January 1985. 3

33

[24] Arjen K. Lenstra, Jr. Lenstra, Hendrik W., and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515–534, 1982. 3, 9 [25] Hendrik W Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of operations research, 8(4):538–548, 1983. 3 [26] Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on Gaussian measures. In 45th FOCS, pages 372–381, Rome, Italy, October 17–19, 2004. IEEE Computer Society Press. 3, 7 [27] Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In Leonard J. Schulman, editor, 42nd ACM STOC, pages 351–358, Cambridge, MA, USA, June 5–8, 2010. ACM Press. 3 [28] Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector problem. In Moses Charika, editor, 21st SODA, pages 1468–1480, Austin, TX, USA, January 17–19, 2010. ACM-SIAM. 3 [29] Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology, 2(2):181–207, 2008. 3 [30] OpenAI. Ten advances in mathematics and theoretical computer science. Technical report, OpenAI, August 2026. Published August 1, 2026. 3 [31] Amaury Pouly and Yixin Shen. Solving the shortest vector problem in 20.63269n+o(n) time on random lattices. In Joan Daemen and Emmanuel Thomé, editors, Advances in Cryptology – EUROCRYPT 2026, pages 92–123, Cham, 2026. Springer Nature Switzerland. 3 [32] Xavier Pujol and Damien Stehlé. Solving the shortest lattice vector problem in time 22.465n . Cryptology ePrint Archive, Report 2009/605, 2009. 3, 6, 21 [33] Oded Regev. Lattice-based cryptography (invited talk). In Cynthia Dwork, editor, CRYPTO 2006, volume 4117 of LNCS, pages 131–141, Santa Barbara, CA, USA, August 20–24, 2006. Springer Berlin Heidelberg, Germany. 3 [34] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), September 2009. 3, 7 [35] Oded Regev and Noah Stephens-Davidowitz. An inequality for gaussians on lattices. SIAM Journal on Discrete Mathematics, 31(2):749–757, 2017. 3 [36] Adi Shamir. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. In 23rd FOCS, pages 145–152, Chicago, Illinois, November 3–5, 1982. IEEE Computer Society Press. 3

34