Slide Reduction, Revisited---Filling the Gaps in SVP Approximation

Divesh Aggarwal; Jianwei Li; Noah Stephens-Davidowitz; Phong Q. Nguyen

REVIEW 2 major objections 4 minor 35 references

Slide Reduction, Revisited---Filling the Gaps in SVP Approximation

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper removes the divisibility barrier in slide reduction and proves the fastest provable algorithms for approximate SVP across the cryptography-relevant range $\delta \in [n^{1/2+\varepsilon}, n^{O(1)}]$.

desk verdict Real results with a localized, fixable gap in Appendix A; worth refereeing and likely correct after correction. read the letter →

arxiv 1908.03724 v1 pith:M3LVPLK4 submitted 2019-08-10 cs.DS cs.CR

Divesh Aggarwal , Jianwei Li , Phong Q. Nguyen , Noah Stephens-Davidowitz This is my paper · ORCID

classification cs.DScs.CR MSC 68Q1768W2511H0694A60

keywords latticebasisreductionshortestvectorproblemslideHermiteSVPDBKZalgorithmapproximationalgorithmspost-quantumcryptography

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper shows that Gama and Nguyen's slide reduction can be extended to every block size $k \ge 2$, removing the old requirement that $k$ divide the lattice rank $n$. The authors prove efficient reductions from approximate Shortest Vector Problem (SVP) on rank-$n$ lattices to $\delta$-SVP on rank-$k$ lattices, for every $n \ge 2k$ and for $k \le n \le 2k$, with the target approximation factors given in Theorems 1.1 and 1.2. These factors match the best known Hermite-SVP bound and, combined with known subexponential SVP solvers, yield the fastest provable running times for $\delta$-SVP for every approximation factor $n^{1/2+\varepsilon} \le \delta \le n^{O(1)}$. This matters because this is the approximation range on which lattice-based cryptography's security estimates rest.

What carries the argument

The central object is the slide-reduced basis: a size-reduced basis whose primal blocks $B[ik+q+1,(i+1)k+q]$ are $\delta$-SVP-reduced and whose shifted dual blocks are $\delta$-DSVP-reduced (dual reduction means the reversed dual basis is SVP-reduced after LLL), with the first block replaced by an $\eta$-HSVP-reduced block of size $k+q$ for $\eta = (\delta^2\gamma_k)^{\frac{k+q-1}{2(k-1)}}$. The proof is carried by the gluing lemma, which shows how two reduced blocks with controlled decay of Gram-Schmidt vectors combine into a larger reduced block; together with the twin-reduction inequality $\|b_1\| \le \delta^{2d/(d-1)}\|b^*_{d+1}\|$, it turns the local reduction conditions into the global approximation factor. The big first block is Hermite-SVP-reduced by the DBKZ algorithm, which supplies exactly the needed bound, and the potential $\mathrm{vol}(B[1,ik+q])^2$ bounds the number of iterations polynomially.

What would settle it

Run the DBKZ algorithm on a rank $2k$ lattice for a representative $k$ (for example, random $q$-ary lattices at cryptographic dimensions) with a $\delta$-SVP oracle and measure the ratio $\|b_1\|/\mathrm{vol}(L)^{1/n}$. If any input family makes this ratio exceed $(1+\varepsilon)(\delta^2\gamma_k)^{(2k-1)/(2(k-1))}$ by a constant factor, the convergence claim behind Theorem 2.3 is false and the central reduction's approximation factors collapse.

Watch

Extended reading notes

Core claim

The central discovery is that a slide-reduced basis does not require every primal block to be SVP-reduced; the first block can be replaced by a Hermite-SVP-reduced block of size $k+q$, and the gluing analysis still delivers the full approximation factor $\delta(\delta^2\gamma_k)^{(n-k)/(k-1)}$ for SVP when $n \ge 2k$, and $\delta\sqrt{\gamma_k}(\delta^2\gamma_q)^{\frac{q+1}{q-1}\cdot\frac{n-k}{2k}}$ for $n = k+q \le 2k$. This removes the rounding penalty $\lceil n \rceil_k/k$ that forced earlier slide reduction to lose a constant in the exponent whenever $k$ did not divide $n$. For $n \le 2k$, the extra oracle call on the extended block $B[1,k]$, whose volume is bounded through the slide-reduced structure, yields sublinear approximation factors in a regime where no provable sublinear algorithm was previously known. The result matches the DBKZ approximation factor for Hermite-SVP, so one algorithm now attains the best proven bound for both problems.

Load-bearing premise

The load-bearing premise is that the DBKZ algorithm provably achieves the Hermite-SVP bound $\|b_1\| \le (1+\varepsilon)(\delta^2\gamma_k)^{(n-1)/(2(k-1))}\mathrm{vol}(L)^{1/n}$ on blocks of rank $k+q$ when given only a $\delta$-SVP oracle for rank $k$; the paper's advertised SVP approximation factors are directly proportional to this bound.

Editorial extensions

If this is right

For every $n \ge 2k$, there is an efficient reduction from $\delta(\delta^2\gamma_k)^{(n-k)/(k-1)}$-SVP on rank-$n$ lattices to $\delta$-SVP on rank-$k$ lattices, matching the best known Hermite-SVP factor and removing the rounding loss that Gama-Nguyen slide reduction incurred when $k$ does not divide $n$.
For $k \le n \le 2k$, the reduction achieves a factor of about $\delta(\delta^2\gamma_k)^{n/(2k)}$, giving provable sublinear approximation factors in a range where no provable sublinear SVP algorithm was previously known.
Combined with the $2^{0.802k}$-time approximate SVP oracle of Wei, Liu, and Wang, the reductions give running time $2^{0.802n/(c+1)}$ for $\delta = n^c$ with $c \ge 1$, and $2^{0.802n/(2c)}$ for $1/2 < c < 1$; the paper states these are the fastest provable running times for $\delta \in [n^{1/2+\varepsilon}, n^{O(1)}]$.
For approximation factors $n^c$ with $c$ slightly smaller than an integer, the exponent improves from $\lceil c+1 \rceil$ to $c+1$, removing a constant-factor gap that directly affected cryptographic security estimates.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the SVP approximation factor for $n \ge 2k$ is governed by $(\delta^2\gamma_k)^{(n-k)/(k-1)}$, further progress on Hermite-SVP algorithms such as DBKZ would translate directly into faster SVP reductions; this paper effectively identifies Hermite-SVP, not SVP, as the bottleneck for this regime.
The $n \le 2k$ construction's extra oracle call on $B[1,k]$ suggests that other volume information inside a slide-reduced basis, not just the first vector, could be exploited to find still shorter vectors within the same oracle model.
Removing the divisibility barrier implies that lattice-cryptography parameter sets no longer need to pad the rank to a multiple of $k$; concrete security evaluations for schemes such as LWE and NTRU could shift if these reductions are instantiated with practical heuristic block reduction.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Read this one. It gives the best proven running times for δ-SVP across the cryptographic range, and the n≤2k algorithm is a genuinely new idea. But before you trust Theorem 1.1, know that Appendix A has a localized bug in the proof of the tail SVP bound (Eq. 9). It's fixable, but it needs to be fixed.

What's new: previous slide reduction required k | n, and the padding cost changed the exponent of the approximation factor. The n≥2k generalization removes that by HSVP-reducing a larger first block, matching DBKZ's HSVP factor. The n≤2k case is the more interesting part: slide reduction with unequal blocks, then a volume argument shows a rank-k prefix has small determinant, and one more oracle call finds a short vector. That is a real contribution, and the proof structure around Fact 2.1 and Lemma 2.2 is clean. The explicit dependence on δ for the SVP oracle is useful, and the paper is honest about relying on the DBKZ/Neumaier result as a dependency.

Where I'd push back: the stress-test is right. In Theorem A.1's induction, the second case says B[d+1,d+k+1] is δ-SVP-reduced when Definition 4.1 only guarantees B[d+1,d+k] SVP-reduced and B[d+2,d+k+1] DSVP-reduced. The size-(k+1) block is not a reduced block, and the sentence's "b1" should be "b*_{d+1}". The fix is simple: split on whether the shortest vector of the tail lies in B[d+1,d+k]. If it does, that block's SVP-reduction gives the bound directly; if not, Lemma 2.2 with tail B[d+k+1,n] applies. So Eq. (9) is unproven as written, but the gap is local and the main theorem can survive it.

Other soft spots are minor. Theorem 3.2 has a couple of typos in the proof (wrong Gram-Schmidt index, a missing factor), and "fastest" should be "best known" absent a lower bound. The outsourced DBKZ proof is acceptable, but should be flagged explicitly as an external dependency. The citation pattern is appropriate; the self-citations to GN08 and MW16 are standard and not a problem.

Bottom line: this is a serious paper with real results for lattice cryptography and algorithms. If I were the editor, I'd send it out. The referee should ask for the appendix fix and the typo cleanup; I'd expect the corrected version to be correct. Worth bringing to reading group.

Referee Report

2 major / 4 minor

Summary. The paper generalizes Gama and Nguyen's slide reduction to all ranks n >= k, removing the requirement that the block size divide the rank. For n >= 2k it claims a reduction from δH-HSVP and δS-SVP on rank n to δ-SVP on rank k with δH = (δ²γ_k)^((n-1)/(2(k-1))) and δS = δ(δ²γ_k)^((n-k)/(k-1)); for k <= n <= 2k it claims δS approximately δ(δ²γ_k)^(n/(2k)). The algorithms use a δ-SVP oracle, and the n >= 2k case invokes the Micciancio-Walter DBKZ algorithm to treat the first block with HSVP reduction. The paper argues that these bounds give the fastest provable running times for δ-approximate SVP in the range n^{1/2+ε} <= δ <= n^{O(1)}, with explicit dependence on the oracle approximation factor δ.

Significance. If the proof gap identified below is repaired, this is a strong contribution. The paper fills a real gap in slide reduction, shows that the DBKZ HSVP bound can be matched by a single algorithm for both HSVP and SVP, and gives concrete improvements to the provable approximation factor for SVP in the polynomial approximation regime. The gluing lemma (Lemma 2.2) and the twin-reduction bound (Fact 2.1) are clean and reusable, and the paper is transparent about its reliance on the DBKZ analysis of Micciancio and Walter and Neumaier. The oracle-accounting in the algorithms is careful, and the claimed running-time improvements are stated with explicit constants. However, the central SVP approximation theorem for n >= 2k is currently not proven as written because of a gap in Appendix A.

major comments (2)

[Appendix A, proof of Theorem A.1] The induction step is not justified. The text says that 'B satisfies the requirements of the theorem with d′ := d+k and p′ := p−1,' but Definition 4.1's Mordell condition applies only to the prefix B[1,k+q], not to the larger prefix B[1,d+k]. Neither the whole matrix nor the suffix B[d+k+1,n] satisfies the hypotheses of Theorem A.1 with that parameter shift, so the displayed bounds on ‖b*_{d+k+1}‖ and ‖b_{d+k+1}‖ do not follow from the stated induction. Since these bounds are used in Lemma 2.2 and then in Theorem 4.2, this leaves Eq. (9) and therefore the n >= 2k SVP approximation factor unsupported.
[Appendix A, proof of Eq. (9), second case] The text asserts that B[d+1,d+k+1] is δ-SVP-reduced when λ1(L(B[d+1,n])) = λ1(L(B[d+1,d+k+1])). This block is not one of the reduced blocks in Definition 4.1; only B[d+1,d+k] is δ-SVP-reduced and B[d+2,d+k+1] is δ-DSVP-reduced. The displayed '‖b1‖' in that sentence should also be '‖b_{d+1}‖' when working inside the suffix. The case therefore requires an actual argument, for example splitting on whether a shortest vector has a nonzero component along b*_{d+k+1}, but the manuscript does not supply one. This is load-bearing because Eq. (9) is used in Theorem 4.2 Eq. (6) and in Corollary 4.4.

minor comments (4)

[Theorem 3.2, proof] In the chain bounding vol(B[1,k]), the factor ‖b*_q‖^q should be ‖b*_{q+1}‖^q when applying Eq. (4) of Fact 2.1 to the twin-reduced block B[1,q+1]; with that correction the displayed inequality and the final bound are consistent.
[Theorem 3.2, proof] The notation in the exponent (n−k)/2 is correct but would be clearer as q/2, since n−k=q in this section; as written the reader must perform that substitution to verify the final exponent.
[Appendix A, proof of Theorem A.1] The second induction bound for ‖b_{d+k+1}‖ contains the expression n−3k−ℓ, where ℓ is not defined and the exponent appears to be a typo for the correct n−d−2k (equivalently, the corresponding expression in p).
[Theorem A.1 / Definition 4.1] The variable p is overloaded: Definition 4.1 writes n = pk+q, while Theorem A.1 writes n = pk+d with d = k+q, so the suffix rank is (p−1)k in one notation and pk in the other. The relation between the two notations should be stated explicitly to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the SVP bounds are derived from explicit reduction conditions, gluing lemmas, and external DBKZ/prior-work bounds; the choice of eta is a design parameter, not a fitted prediction.

full rationale

Walking the derivation chain: the n<=2k result (Theorem 3.2) starts from the (delta,k)-slide-reduced conditions of Definition 3.1 and derives vol(B[1,k]) using Fact 2.1 and Hermite's constant; no target bound is assumed. For n>=2k, Definition 4.1 explicitly sets eta := (delta^2 gamma_k)^((k+q-1)/(2(k-1))) because the external Micciancio-Walter DBKZ algorithm (Theorem 2.3, with proof outsourced to [MW16, Neu17]) guarantees exactly this HSVP output. This is a design choice that makes the gluing lemma apply, not an assumption of the theorem's conclusion. The HSVP statement in Theorem 4.2 deliberately reproduces the DBKZ bound, but the paper's novel SVP bound (Eq. (6)) is obtained through Theorem A.1's SVP-reduction claim and Lemma 2.2, i.e., through a separate argument rather than by construction. No fitted parameter is renamed as a prediction; no uniqueness theorem from the authors is imported; the citations to [GN08] (one shared author) and [MW16] are external prior results with stated assumptions that do not include this paper's target bounds. The possible gap in the Appendix A induction is a proof-validity concern, not a circularity: even if Eq. (9) were unsupported, that would make the bound unproven rather than equivalent to its inputs.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters: all quantities (δ, k, ε) are user-chosen inputs to the reductions, and γ_k is a classical constant. The work relies on four external pillars: geometry-of-numbers bounds, the DBKZ HSVP guarantee, the oracle model for SVP, and the fastest known exact/near-exact SVP algorithms. No new physical or mathematical entities are postulated.

assumptions (4)

standard math Hermite's constant γ_n = Θ(n) and the bound λ1(L) ≤ √γ_n vol(L)^{1/n} hold for every rank-n lattice.
Used throughout to convert between SVP and HSVP bounds, e.g., in Section 2.3 and Theorem 3.2. This is a classical theorem in geometry of numbers.
domain assumption The Micciancio-Walter DBKZ algorithm achieves Theorem 2.3's HSVP bound (δ²γ_k)^{(n-1)/(2(k-1))} vol(L)^{1/n} using a δ-SVP oracle on rank k.
Theorem 2.3 is stated with only a proof sketch; the full proof is outsourced to [MW16, Neu17]. Definition 4.1 sets η to exactly this bound, making it load-bearing.
domain assumption A δ-SVP oracle for rank-k lattices exists and can be used as a black box to SVP/DSVP-reduce blocks in the algorithms.
The paper's results are reductions in the oracle model; Algorithms 1-3 call such an oracle. This is the standard framework for basis reduction.
domain assumption The current fastest δ-SVP algorithms used for comparison (2^{0.802n} for constant δ, 2^n for exact SVP) are correct and have the stated running times.
Table 1 and Figure 1 compare against [ADRS15], [WLW15], and [GN08]. The 'fastest' claim depends on these external results.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Slide Reduction, Revisited---Filling the Gaps in SVP Approximation." pith.science (2026). https://pith.science/paper/M3LVPLK4

@misc{pith2026190803724,
  author       = {Pith},
  title        = {Pith review of: Slide Reduction, Revisited---Filling the Gaps in SVP Approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/M3LVPLK4}},
  note         = {Machine review of arXiv:1908.03724}
}

abstract

We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP). As a result, we show the fastest provably correct algorithm for $\delta$-approximate SVP for all approximation factors $n^{1/2+\varepsilon} \leq \delta \leq n^{O(1)}$. This is the range of approximation factors most relevant for cryptography.

Figures

Figures reproduced from arXiv: 1908.03724 by the authors.

**Figure 1.** Running time T as a function of approximation factor δ for δ-SVP. The y-axis is log2 (T)/n, and the x-axis is logn δ. 1.2 Our techniques We first briefly recall some of the details of Gama and Nguyen’s slide reduction. Slide reduction divides the basis B = (b1, . . . , bn) ∈ R m×n evenly into disjoint “primal blocks” B[ik+1,(i+1)k] of length k. (Notice that this already requires n to be divisible by k.) It also defi… view at source ↗

**Figure 2.** Slide reduction of an upper-triangular matrix for [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 34 canonical work pages

[1]

Solving the Shortest Vector Problem in 2^n time via Discrete Gaussian Sampling

Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz . Solving the Shortest Vector Problem in 2^n time via Discrete Gaussian Sampling . In STOC , 2015. http://arxiv.org/abs/1412.7994

arXiv 2015
[2]

Generating hard instances of lattice problems

Mikl \'o s Ajtai. Generating hard instances of lattice problems. In STOC , 1996

work page 1996
[3]

Sivakumar

Mikl \'o s Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the Shortest Lattice Vector Problem . In STOC , 2001

work page 2001
[4]

Albrecht, Rachel Player, and Sam Scott

Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning with Errors . J. Mathematical Cryptology , 9(3), 2015. http://eprint.iacr.org/2015/046

work page 2015
[5]

Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)

Divesh Aggarwal and Noah Stephens-Davidowitz . Just take the average! A n embarrassingly simple 2^n -time algorithm for SVP (and CVP ). In SOSA , 2018. http://arxiv.org/abs/1709.01535

work page Pith review arXiv 2018
[6]

Yuanmi Chen and Phong Q. Nguyen. Faster algorithms for approximate common divisors: Breaking fully-homomorphic-encryption challenges over the integers. In EUROCRYPT , 2012

work page 2012
[7]

Enumerative lattice algorithms in any norm via M -ellipsoid coverings

Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative lattice algorithms in any norm via M -ellipsoid coverings. In FOCS , 2011

work page 2011
[8]

Nicolas Gama, Nick Howgrave-Graham , Henrik Koy, and Phong Q. Nguyen. Rankin's constant and blockwise lattice reduction. In CRYPTO , 2006

work page 2006

Show all 35 references

[9]

Nicolas Gama, Nick Howgrave-Graham , and Phong Q. Nguyen. Symplectic lattice reduction and NTRU . In EUROCRYPT , 2006

2006
[10]

Nicolas Gama and Phong Q. Nguyen. Finding short lattice vectors within Mordell's inequality. In STOC , 2008

2008
[11]

Trapdoors for hard lattices and new cryptographic constructions

Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC , 2008. https://eprint.iacr.org/2007/432

2008
[12]

Analyzing blockwise lattice algorithms using dynamical systems

Guillaume Hanrot, Xavier Pujol, and Damien Stehl \'e . Analyzing blockwise lattice algorithms using dynamical systems. In CRYPTO , 2011

2011
[13]

Lattice reduction: A toolbox for the cryptanalyst

Antoine Joux and Jacques Stern. Lattice reduction: A toolbox for the cryptanalyst. J. Cryptology , 11(3), 1998

1998
[14]

Improved algorithms for integer programming and related lattice problems

Ravi Kannan. Improved algorithms for integer programming and related lattice problems. In STOC , 1983

1983
[15]

Lenstra, Jr

Hendrik W. Lenstra, Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research , 8(4), 1983

1983
[16]

Lenstra, Hendrik W

Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and L \'a szl \'o Lov \'a sz. Factoring polynomials with rational coefficients. Mathematische Annalen , 261(4), 1982

1982
[17]

Jianwei Li and Phong Q. Nguyen. Approximating the densest sublattice from Rankin’s inequality. LMS J. of Computation and Mathematics , 17(A), 2014

2014
[18]

An algorithmic theory of numbers, graphs and convexity

L \'a szl \'o Lov \'a sz. An algorithmic theory of numbers, graphs and convexity . Society for Industrial and Applied Mathematics, 1986

1986
[19]

Shortest lattice vectors in the presence of gaps

Mingjie Liu, Xiaoyun Wang, Guangwu Xu, and Xuexin Zheng. Shortest lattice vectors in the presence of gaps. http://eprint.iacr.org/2011/139, 2011

2011
[20]

A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations

Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. SIAM J. on Computing , 42(3), 2013

2013
[21]

Practical, predictable lattice basis reduction

Daniele Micciancio and Michael Walter. Practical, predictable lattice basis reduction. In Eurocrypt , 2016. http://eprint.iacr.org/2015/1123

2016
[22]

Bounding basis reduction properties

Arnold Neumaier. Bounding basis reduction properties. Designs, Codes and Cryptography , 84(1), 2017

2017
[23]

Post-quantum cryptography

Computer Security Division NIST. Post-quantum cryptography. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography, 2018

2018
[24]

Nguyen and Jacques Stern

Phong Q. Nguyen and Jacques Stern. The two faces of lattices in cryptology. In CaLC , 2001

2001
[25]

Nguyen and Thomas Vidick

Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the Shortest Vector Problem are practical. J. Mathematical Cryptology , 2(2), 2008

2008
[26]

Nguyen and Brigitte Vallée, editors

Phong Q. Nguyen and Brigitte Vallée, editors. The LLL algorithm: Survey and applications . Springer-Verlag, 2010

2010
[27]

The rise and fall of knapsack cryptosystems

Andrew M Odlyzko. The rise and fall of knapsack cryptosystems. Cryptology and Computational Number Theory , 42, 1990

1990
[28]

Public-key cryptosystems from the worst-case Shortest Vector Problem

Chris Peikert. Public-key cryptosystems from the worst-case Shortest Vector Problem . In STOC , 2009

2009
[29]

A decade of lattice cryptography

Chris Peikert. A decade of lattice cryptography. Foundations and Trends in Theoretical Computer Science , 10(4), 2016

2016
[30]

Solving the Shortest Lattice Vector Problem in time 2^ 2.465 n , 2009

Xavier Pujol and Damien Stehl \'e . Solving the Shortest Lattice Vector Problem in time 2^ 2.465 n , 2009. http://eprint.iacr.org/2009/605

2009
[31]

On lattices, learning with errors, random linear codes, and cryptography

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM , 56(6), 2009

2009
[32]

A hierarchy of polynomial time lattice basis reduction algorithms

Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. , 53(23), 1987

1987
[33]

Claus-Peter Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathmatical Programming , 66, 1994

1994
[34]

A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem

Adi Shamir. A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem. IEEE Trans. Inform. Theory , 30(5), 1984

1984
[35]

Finding shortest lattice vectors in the presence of gaps

Wei Wei, Mingjie Liu, and Xiaoyun Wang. Finding shortest lattice vectors in the presence of gaps. In CT - RSA , 2015

2015

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Solving the Shortest Vector Problem in 2^n time via Discrete Gaussian Sampling

Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz . Solving the Shortest Vector Problem in 2^n time via Discrete Gaussian Sampling . In STOC , 2015. http://arxiv.org/abs/1412.7994

arXiv 2015

[2] [2]

Generating hard instances of lattice problems

Mikl \'o s Ajtai. Generating hard instances of lattice problems. In STOC , 1996

work page 1996

[3] [3]

Sivakumar

Mikl \'o s Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the Shortest Lattice Vector Problem . In STOC , 2001

work page 2001

[4] [4]

Albrecht, Rachel Player, and Sam Scott

Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning with Errors . J. Mathematical Cryptology , 9(3), 2015. http://eprint.iacr.org/2015/046

work page 2015

[5] [5]

Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP)

Divesh Aggarwal and Noah Stephens-Davidowitz . Just take the average! A n embarrassingly simple 2^n -time algorithm for SVP (and CVP ). In SOSA , 2018. http://arxiv.org/abs/1709.01535

work page Pith review arXiv 2018

[6] [6]

Yuanmi Chen and Phong Q. Nguyen. Faster algorithms for approximate common divisors: Breaking fully-homomorphic-encryption challenges over the integers. In EUROCRYPT , 2012

work page 2012

[7] [7]

Enumerative lattice algorithms in any norm via M -ellipsoid coverings

Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative lattice algorithms in any norm via M -ellipsoid coverings. In FOCS , 2011

work page 2011

[8] [8]

Nicolas Gama, Nick Howgrave-Graham , Henrik Koy, and Phong Q. Nguyen. Rankin's constant and blockwise lattice reduction. In CRYPTO , 2006

work page 2006