betaFeedback

WorksComputer Science

Gaussian Difference Dynamics: Breaking the 2n/22^{n/2} Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling

Abstract

We give classical randomized algorithms in a word RAM model that break the 2n/22^{n/2} barrier for both discrete Gaussian sampling (DGS) and the Shortest Vector Problem (SVP). For every fixed α>1α>1, shifted DGS on arbitrary lattices at width σ≥αη1/2(L)σ\geαη_{1/2}(L) takes (3/2)n/2+o(n) timeand(4/3)n/2+o(n) space. (3/2)^{n/2+o(n)}\text{ time} \qquad\text{and}\qquad (4/3)^{n/2+o(n)}\text{ space}. These bounds match the Becker–Ducas–Gama–Laarhoven (BDGL) heuristic sieving exponents. At widths at least 3η1/2(L)/23η_{1/2}(L)/2, the same total cost suffices for an entire batch of ⌊(4/3)n/2⌋\lfloor(4/3)^{n/2}\rfloor samples jointly close to independent target Gaussians. For SVP on arbitrary lattices, our algorithm returns a shortest nonzero vector with high probability in 20.4130n+o(n) timeand20.3138n+o(n) space. 2^{0.4130n+o(n)}\text{ time} \qquad\text{and}\qquad 2^{0.3138n+o(n)}\text{ space}. As a corollary, we obtain centered DGS at every width with the same exponents, answering a question of Stephens-Davidowitz (SODA 2016). We introduce Gaussian difference dynamics (GDD), a framework for tracking expected counts and pairwise clustering of vectors through repeated differencing. A closed recursion for the first two counting moments controls these quantities relative to a Gaussian reference, without requiring independence within intermediate lists. Accurate moment bounds let us extract a Gaussian sample by weighted selection, while the weaker bounds needed to establish a shortest vector representation allow us to retain more differences. We perform these transitions on thin spherical shells, where the Gaussian rejection weights can be renormalized at subexponential cost. For batch sampling, we combine this geometry with the double rejection technique of Doulgerakis and Laarhoven to control the joint distribution of outputs while reusing vectors.

Introduction

The Shortest Vector Problem (SVP) and discrete Gaussian sampling (DGS) are basic problems in lattice algorithms, complexity, and cryptography. For a full rank lattice L⊂RnL \subset\mathbb{R}^n, SVP asks for a shortest nonzero vector, while DGS samples lattice points with probabilities proportional to e−π∥x∥2/r2e^{-\pi\lVert x\rVert^2/r^2} at a prescribed width rr. Discrete Gaussians connect sampling with the search for short vectors, and Gaussian identities give quantitative control over the distributions produced by repeatedly combining vectors. Geometric sieving exploits the fact that nearby vectors have a shorter difference, suggesting algorithms that combine Gaussian distributional control with the efficiency of geometric search.

The 2n/22^{n/2} barrier in provable algorithms. Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS) gave an SVP algorithm using 2n+o(n)2^{n+o(n)} time and space via Gaussian sampling at arbitrary width [2], and Aggarwal and Stephens-Davidovich later simplified the algorithm by pairing and averaging [4]. ADRS also give a faster sampler above smoothing that generates 2n/22^{n/2} independent samples in 2n/2+o(n)2^{n/2+o(n)} time and space. Building on sampling above smoothing, our earlier work uses random superlattices to reach the shortest vector scale, first by direct sampling in time 20.7314n+o(n)2^{0.7314n+o(n)} [13] and then by geometric pair search in time 20.5596n+o(n)2^{0.5596n+o(n)} [14]. More recently, Hhan’s qq-ary coset difference tree brings arbitrary lattice SVP to 2n/2+o(n)2^{n/2+o(n)} time and space [20], while Kim obtains one centered Gaussian sample at any width in expected 2n/2+o(n)2^{n/2+o(n)} time [22].

The fast ADRS sampler combines pairs x,yx,y by averaging, (x+y)/2(x+y)/2. Before rescaling, it pairs vectors from the same coset of Li+1⊂LiL_{i+1} \subset L_i and retains their sum, with 2Li⊆Li+12L_i \subseteq L_{i+1}. Its lattice tower satisfies

Li+2⊆2Li⟹[Li:Li+1][Li+1:Li+2]=[Li:Li+2]≥2n.L_{i+2} \subseteq2L_i \quad\Longrightarrow\quad[L_i:L_{i+1}][L_{i+1}:L_{i+2}] = [L_i:L_{i+2}] \ge2^n.

Balancing the adjacent indices gives 2n/2+o(n)2^{n/2+o(n)} cosets per level, which sets the sampler’s list scale [2 Proposition 5.7, Definition 5.8, and Theorem 5.11]. Algorithms that use this batch interface inherit its generation cost, while Hhan’s half exponent arises from a balance between Gaussian signal, estimation error, and coset table size [20 Section 1.1 and Remark 1.2]. Improving these bounds calls for revisiting how intermediate vectors are generated and how much supply the final task needs. Stephens-Davidowitz asks for a faster centered sampler, possibly producing only one sample, and writes that “entirely new techniques would be needed” to go below 2n/22^{n/2} [33 Section 1.4, p. 7].

Making geometric sieving provable on arbitrary lattices. Sieving began with the algorithm of Ajtai, Kumar, and Sivakumar [6] and developed through both provable and heuristic analyses [29, 31, 9]. Under heuristic assumptions on the successive lists, the batched BDGL sieve takes (3/2)n/2+o(n)(3/2)^{n/2+o(n)} time and (4/3)n/2+o(n)(4/3)^{n/2+o(n)} space [8]. Recent work of Doulgerakis and Laarhoven [11] and Zhou, Wang, and Wang [36] proves these SVP exponents for Haar-random lattices, using distributional estimates for random lattice geometry and the generated lists. Doulgerakis and Laarhoven also construct Gaussian batches at every width.

Extending this efficiency to arbitrary input lattices requires control of both the geometry and the dependence of the generated vectors. Repeated differences share inputs and ancestors, while local lattice geometry governs the numbers of partners of an input and representations of an output, especially at widths below smoothing. A rigorous iteration must therefore follow the supply at the intended locations together with the correlations that affect its availability.

We combine Gaussian distributional control with geometric sieving to obtain algorithms on every lattice. Above smoothing, Gaussian sampling attains the BDGL time and space exponents, while SVP and centered sampling at arbitrary width take 20.4130n+o(n)2^{0.4130n+o(n)} time and 20.3138n+o(n)2^{0.3138n+o(n)} space. We first describe the counting framework behind the single sample and shortest vector constructions, then state their guarantees and the stronger batch result.

Gaussian difference dynamics

We start with wide Gaussian samples and repeatedly form weighted short differences to reach a smaller Gaussian width. Once the vectors reach a suitable scale, we use the resulting lists to produce the desired output. For DGS above smoothing, one weighted selection gives a Gaussian sample. For SVP, we first build additional representations and then use BDGL filters to search for short differences between two terminal lists. The final task thus determines what guarantees the intermediate lists must provide.

The main difficulty is to control the lists produced by this iteration. Differences sharing an input are correlated, and later rounds inherit dependence through common ancestors. The heuristic BDGL sieve analyzes successive lists under assumptions on their angular distribution [8]. The ADRS Gaussian combiner instead maintains a joint distribution close to independent Gaussian samples through successive rounds [2]. Retaining many differences reuses the same inputs, so an analysis of this iteration must account for the resulting dependence.

We track two counting moments relative to a Gaussian reference: the expected number of records in a region and the expected number of ordered pairs of distinct records in two regions. The first describes where records appear, while the second controls their clustering. At each merge, conditional independence between the two separately generated child lists gives a closed recursion for these moments, even though either list may be internally correlated. These bounds connect expected counts to the probability of producing useful vectors and to the work needed to find them. We call this evolution Gaussian difference dynamics.1

Thin spherical shells let us renormalize Gaussian rejection weights at subexponential cost. On a fixed superlattice smooth at all midpoint widths, the Gaussian midpoint identity gives the reference counts for each cooling round. Geometric search finds the pairs needed for the next list.

The final task determines the required moment accuracy. For Gaussian sampling, weighted selection divides by the list’s random total weight. Accurate moments control this normalization when the reference total weight is sufficiently large. Sparse activation followed by isolation preserves this precision, retaining a pair only when no other activated pair shares either input.

For SVP, it suffices that a shortest vector is represented with probability e−o(n)e^{-o(n)}, since repetition then costs only a subexponential factor. This weaker requirement permits a fixed number of full differencing layers that retain every eligible pair, building more representations before the final search. These layers keep the reference width fixed and lower the shell energy. We compare two terminal lists in a common random affine coset and select differences that belong to the original lattice.

An exponential batch additionally requires the joint output law to be close to a product of target Gaussians. We combine the same shell geometry with the two rejection corrections of Doulgerakis and Laarhoven [11]. At each merge, these corrections make the complete trial law, including failure, independent of the reused partner list. Uniform estimates for these lists and mixing across radial bins then give the batch guarantee. § 2 develops these constructions.

The counting framework has also been applied to l∞l_\infty-SVP with uniform reference counts on cubes [Gao26].

Main results

For a rational lattice L=BZnL = B\mathbb{Z}^{n}, write

ρσ(x)=e−π∥x∥2/σ2,Da+L,σ(x)=ρσ(x)ρσ(a+L).\rho_{\sigma}(x) = e^{-\pi\lVert x\rVert^{2}/\sigma^{2}}, \qquad D_{a+L,\sigma}(x) = \frac{\rho_{\sigma}(x)}{\rho_{\sigma}(a+L)}.

The smoothing parameter is defined by ρ1/ηε(L)(L∗∖{0})=ε\rho_{1/\eta_{\varepsilon}(L)}(L^{*} \setminus\{0\}) = \varepsilon. We write L(X)\mathcal{L}(X) for the law of XX and dTVd_{\mathrm{TV}} for total variation distance. Write

αG=12log⁡2(3/2),βG=12log⁡2(4/3),J(z)=z−1−log⁡z2log⁡2.\alpha_{G} = \frac{1}{2}\log_{2}(3/2), \qquad\beta_{G} = \frac{1}{2}\log_{2}(4/3), \qquad J(z) = \frac{z - 1 - \log z}{2\log2}.

Our algorithms use a randomized word RAM, and their time and bit space bounds hold on every execution, including random bit generation and finite arithmetic. We suppress polynomial factors in the binary input length BB and the accuracy parameter ff, when present. The computational model and finite implementation are given in Appendix § 14.6.§ 1.1 and Proposition 6.3.

Our first application of GDD is a Gaussian sampler. Controlling the first two counting moments of the correlated list suffices to obtain one Gaussian sample by weighted selection, at the BDGL time and space exponents.

Theorem 1.1 (Single sample DGS above smoothing). Fix α>1\alpha> 1 and ξ>0\xi> 0. *There is a classical randomized algorithm that, given a full rank rational lattice LL, a rational shift aa, and a positive rational squared width σ2\sigma^{2} with σ≥αη1/2(L)\sigma\ge\alpha\eta_{1/2}(L), outputs X∈a+LX \in a + L with

dTV(L(X),Da+L,σ)≤exp⁡[−Ω(n/log⁡2+ξ(n+2))].d_{\mathrm{TV}}(\mathcal{L}(X), D_{a+L,\sigma}) \le\exp[-\Omega(n/\log^{2+\xi}(n+2))].

Its time is 2αGn+o(n)2^{\alpha_{G}n+o(n)} and its bit space is 2βGn+o(n)2^{\beta_{G}n+o(n)}.

§ 7 proves this result. The constants may depend on α\alpha and ξ\xi.

To obtain an exponential batch within the time and space bounds of Theorem 1.1, we combine the Gaussian geometry above with the double rejection technique of Doulgerakis and Laarhoven [11]. This gives the stronger joint sampling guarantee below.

Theorem 1.2 (Batch DGS above smoothing). Fix α>1\alpha> 1 and 0<b<min⁡{βG,J(α−2)}0 < b < \min\{\beta_{G}, J(\alpha^{-2})\}. Given a full rank rational lattice L=BLZnL = B_{L}\mathbb{Z}^{n}, a rational shift aa, and a positive rational squared width σ2\sigma^{2} satisfying σ≥αη1/2(L)\sigma\ge\alpha\eta_{1/2}(L), an algorithm outputs B=⌊2bn⌋B = \lfloor2^{bn}\rfloor points in a+La + L with

dTV(L(X1,…,XB),Da+L,σ⊗B)≤exp⁡[−Ω(n/log⁡2(n+2))].d_{\mathrm{TV}}(\mathcal{L}(X_{1},\ldots,X_{B}), D_{a+L,\sigma}^{\otimes B}) \le\exp[-\Omega(n/\log^{2}(n+2))].

Its total time is 2αGn+o(n)2^{\alpha_{G}n+o(n)} and its bit space, including the output, is 2βGn+o(n)2^{\beta_{G}n+o(n)}. If α≥3/2\alpha\ge3/2, one may take the full batch B=⌊2βGn⌋B = \lfloor2^{\beta_{G}n}\rfloor.

The single sample construction gives a direct application of the counting moment framework, while the batch guarantee requires additional control of the joint output law. Retaining the first batch output also gives a single sample with this stronger error bound and the same BDGL exponents αG≈0.2925\alpha_{G} \approx0.2925 and βG≈0.2075\beta_{G} \approx0.2075.

In the full batch case, shared preprocessing gives average time 212log⁡2(9/8)n+o(n)2^{\frac{1}{2}\log_{2}(9/8)n+o(n)} per output. § 11.2 proves the joint law and total resource bounds.

Theorem 1.3 (SVP). Given a full rank rational lattice L=BZnL = B\mathbb{Z}^n, there is a classical randomized algorithm that returns a shortest nonzero vector with probability at least 1−2−Ω(nlog⁡n)1 - 2^{-\Omega(n \log n)}, in

T=20.4130n+o(n) time,S=20.3138n+o(n) space.T = 2^{0.4130n+o(n)}\ \text{time}, \qquad S = 2^{0.3138n+o(n)}\ \text{space}.

Every output is a nonzero vector of LL.

Stephens-Davidowitz [33 Theorem 4.6] gave a reduction from centered DGS at arbitrary width to SVP, with polynomial expected overhead and no increase in dimension. Applying this reduction to Theorem 1.3 gives a single Gaussian sample with the same time and space exponents, answering his question about sampling below 2n/22^{n/2}.

We use his notion of accuracy: a law is (γ,ε)(\gamma,\varepsilon)-close to the target if it is within total variation distance ε\varepsilon of a law whose pointwise probabilities differ from the target by at most a factor γ\gamma (§ 12.4).

Corollary 1.4 (Centered Gaussian sampling at arbitrary width). Let f:N→Z≥1f:\mathbb{N}\to\mathbb{Z}_{\ge1} be efficiently computable, with 1≤f(n)≤poly⁡(n)1 \le f(n) \le\operatorname{poly}(n). For a full rank rational lattice L=BZnL = B\mathbb{Z}^n and any positive rational width σ\sigma, one can sample X∈LX \in L whose law is (1+1/f(n),2−f(n))(1 + 1/f(n), 2^{-f(n)})-close to DL,σD_{L,\sigma}. The algorithm uses

T=20.4130n+o(n) time,S=20.3138n+o(n) spaceT = 2^{0.4130n+o(n)}\ \text{time}, \qquad S = 2^{0.3138n+o(n)}\ \text{space}

per sample.

The total variation error is O(1/f(n))+2−f(n)O(1/f(n)) + 2^{-f(n)}, permitting any prescribed inverse polynomial accuracy without changing the leading time or space exponent.

The comparison of direction weights in the proof of [33 Theorem 4.6] does not go through as stated for the additive grid of squared radii. We obtain the required control using a multiplicative grid and complete the proof within the original reduction framework. Appendix § 14.7 gives the counterexample and the repaired argument.

ProblemGuaranteeTime exponentSpace exponent
Single Gaussian sampleα>1\alpha> 1αG\alpha_{\mathrm{G}}βG\beta_{\mathrm{G}}
Full Gaussian batchα≥3/2\alpha\ge3/2αG\alpha_{\mathrm{G}}βG\beta_{\mathrm{G}}
Reusable BDDfixed r<0.3157071r < 0.3157071P:αG, D:βGP:\alpha_{\mathrm{G}},\ D:\beta_{\mathrm{G}}βG\beta_{\mathrm{G}}
Exact 3-uSVPλ2≥3λ1\lambda_2 \ge3\lambda_1αG\alpha_{\mathrm{G}}βG\beta_{\mathrm{G}}
4.15-GapSVPpromise decisionαG\alpha_{\mathrm{G}}βG\beta_{\mathrm{G}}
SVParbitrary lattice0.41300.3138
Centered DGSevery width0.41300.3138
4-CVP, SMP, SIVPconstant approximation0.46110.3138
γ\gamma-CVP, SMP, SIVPγ(n)=ω(1)\gamma(n) = \omega(1)0.41300.3138
O(nlog⁡n)O(\sqrt{n\log n})-SIVPnear smoothing samplingαG\alpha_{\mathrm{G}}βG\beta_{\mathrm{G}}

Table 1. Algorithmic consequences on arbitrary rational lattices. Time and bit space entries mean 2cn+o(n)2^{cn+o(n)}, with polynomial input factors suppressed. αG≈0.2925\alpha_{\mathrm{G}} \approx0.2925 and βG≈0.2075\beta_{\mathrm{G}} \approx0.2075. BDD has preprocessing PP and per-target work DD.

References

  1. [1]Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, and Noah Stephens-Davidowitz. Dimension-preserving reductions between SVP and CVP in different p-norms. In Proceedings of SODA, pages 2444–2462, 2021. https://doi.org/10.1137/1.9781611976465.145.
  2. [2]Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the shortest vector problem in 2^n time using discrete Gaussian sampling. In Proceedings of STOC, pages 733–742, 2015. https://doi.org/10.1145/2746539.2746606.
  3. [3]Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, and Noah Stephens-Davidowitz. Slide reduction revisited—filling the gaps in SVP approximation. In Advances in Cryptology—CRYPTO, pages 274–295, 2020. https://doi.org/10.1007/978-3-030-56880-1_10.
  4. [4]Divesh Aggarwal and Noah Stephens-Davidowitz. Just take the average! An embarrassingly simple 2^n time algorithm for SVP (and CVP). In Proceedings of SOSA, volume 61 of OASIcs, pages 12:1–12:19, 2018. https://doi.org/10.4230/OASIcs.SOSA.2018.12.
  5. [5]Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of Mathematics, 160(2):781–793, 2004. https://doi.org/10.4007/annals.2004.160.781.
  6. [6]Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proceedings of STOC, pages 601–610, 2001. https://doi.org/10.1145/380752.380857.
  7. [7]Wojciech Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296:625–635, 1993. https://doi.org/10.1007/BF01445125.
  8. [8]Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Proceedings of SODA, pages 10–24, 2016. https://doi.org/10.1137/1.9781611974331.ch2.
  9. [9]Anja Becker, Nicolas Gama, and Antoine Joux. Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search. Cryptology ePrint Archive, Paper 2015/522, 2015. https://eprint.iacr.org/2015/522.
  10. [10]Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. On the closest vector problem with a distance guarantee. In Proceedings of CCC, pages 98–109, 2014. https://doi.org/10.1109/CCC.2014.18.
  11. [11]Emmanouil Doulgerakis and Thijs Laarhoven. Smooth sailing through spherical shells: provable random-lattice sieving in time 2^0.292n. arXiv:2609.37482, 2026. https://arxiv.org/abs/2609.37482.
  12. [13]Yiming Gao, Yansong Feng, and Honggang Hu. Solving the shortest vector problem in 2^0.7314n+o(n) time via discrete Gaussian sampling on superlattices. Cryptology ePrint Archive, Paper 2026/1587, 2026. https://eprint.iacr.org/2026/1587.
  13. [14]Yiming Gao, Yansong Feng, and Honggang Hu. Discrete Gaussian sampling meets BDGL decoding: solving the shortest vector problem in 2^{0.5596n+o(n)} time. Cryptology ePrint Archive, Paper 2026/1844, 2026. https://eprint.iacr.org/2026/1844.
  14. [15]Yiming Gao and Honggang Hu. Faster matrix multiplication leads to faster lattice sieving. Cryptology ePrint Archive, Paper 2026/2622, 2026. https://eprint.iacr.org/2026/2622.
  15. [16]Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of STOC, pages 197–206, 2008. https://doi.org/10.1145/1374376.1374407.
  16. [17]Guillaume Hanrot, Xavier Pujol, and Damien Stehlé. Analyzing blockwise lattice algorithms using dynamical systems. In Advances in Cryptology—CRYPTO, pages 447–464, 2011. https://doi.org/10.1007/978–3–642–22792–9_25.
  17. [18]Sariel Har-Peled and Micha Sharir. Relative (p, ε)-approximations in geometry. Discrete & Computational Geometry, 45(3):462–496, 2011. https://doi.org/10.1007/s00454–010–9248–1.
  18. [19]Minki Hhan. Solving the shortest vector problem in time 2^{0.6039n} via mid-point Hessian. arXiv:2608.02478, 2026. https://arxiv.org/abs/2608.02478.
  19. [20]Minki Hhan. Finding a shortest vector and more in 2^{n/2+o(n)} time using q-ary coset difference tree. arXiv:2609.02764, 2026. https://arxiv.org/abs/2609.02764.
  20. [21]Grigorii A. Kabatiansky and Vladimir I. Levenshtein. On bounds for packings on a sphere and in space. Problems of Information Transmission, 14(1):1–17, 1978.
  21. [22]Jiseung Kim. One discrete Gaussian sample in 2^{n/2+o(n)} time. arXiv:2608.03220, 2026. https://arxiv.org/abs/2608.03220.
  22. [23]Philip N. Klein. Finding the closest lattice vector when it is unusually close. In Proceedings of SODA, pages 937–941, 2000.
  23. [24]Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982. https://doi.org/10.1007/BF01457454.
  24. [25]Jianwei Li and Phong Q. Nguyen. A complete analysis of the BKZ lattice reduction algorithm. Journal of Cryptology, 38(1):12, 2025. https://doi.org/10.1007/s00145–024–09527–0.
  25. [26]Vadim Lyubashevsky and Daniele Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In Advances in Cryptology—CRYPTO, pages 577–594, 2009. https://doi.org/10.1007/978–3–642–03356–8_34.
  26. [27]Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on Gaussian measures. SIAM Journal on Computing, 37(1):267–302, 2007. https://doi.org/10.1137/S0097539705447360.
  27. [28]Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. SIAM Journal on Computing, 42(3):1364–1391, 2013. https://doi.org/10.1137/100811970.
  28. [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. https://doi.org/10.1515/JMC.2008.009.
  29. [30]Amaury Pouly and Yixin Shen. Solving the shortest vector problem in 2^0.63269n+o(n) time on random lattices. In Advances in Cryptology—EUROCRYPT, volume 16544 of LNCS, pages 92–123, 2026. https://doi.org/10.1007/978-3-032-25327-9_4.
  30. [31]Xavier Pujol and Damien Stehlé. Solving the shortest lattice vector problem in time 2^2.465n. Cryptology ePrint Archive, Paper 2009/605, 2009. https://eprint.iacr.org/2009/605.
  31. [32]J. Barkley Rosser and Lowell Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics, 6(1):64–94, 1962. https://doi.org/10.1215/ijm/1255631807.
  32. [33]Noah Stephens-Davidowitz. Discrete Gaussian sampling reduces to CVP and SVP. arXiv:1506.07490, 2016. https://arxiv.org/pdf/1506.07490.
  33. [34]Leizhang Wang. Analyzing Pump and Jump BKZ algorithm using dynamical systems. In Post-Quantum Cryptography—PQCrypto, pages 406–432, 2024. https://doi.org/10.1007/978-3-031-62743-9_14.
  34. [35]Doron Zeilberger and Wadim Zudilin. The irrationality measure of π is at most 7.103205334 . . . Moscow Journal of Combinatorics and Number Theory, 9(4):407–419, 2020. https://doi.org/10.2140/moscow.2020.9.407.
  35. [36]Yang Zhou, Zhedong Wang, and Mingsheng Wang. Exact SVP on Haar-random lattices at the heuristic sieving exponents. Cryptology ePrint Archive, Paper 2026/2271, 2026. https://eprint.iacr.org/2026/2271.

Paper details

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

views · 37

downloads · 0

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents