Pith. sign in

REVIEW 2 major objections 3 minor 41 references

An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

T0 review · 2 major / 3 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read A quantum algorithm for 3-tuple lattice sieving runs in 2^{0.2846d} time, improving on the previous 2^{0.3098d}, with memory capped at 2^{0.1887d}.

desk verdict Genuinely new two-level amplitude amplification for 3-tuple sieving, but the main theorem's proof has a numerical bound contradicted by its own Lemma 2.8; the stated 2^{0.2846d} is not established as written. read the letter →

arxiv 2510.08473 v3 pith:HAI2ST74 submitted 2025-10-09 quant-ph cs.CR

Lynn Engelberts , Yanlin Chen , Amin Shiraz Gilani , Maya-Iggy van Hoof , Stacey Jeffery , Ronald de Wolf This is my paper
classification quant-phcs.CR PACS 03.67.Ac
keywords ShortestVectorProblemlatticesieving3-tuplequantumalgorithmamplitudeamplificationrandomproductcodesQCRAMpost-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 aims to show that the quantum time cost of 3-tuple lattice sieving can be reduced from 2^{0.3098d} to 2^{0.2846d} while keeping the memory requirement at the minimal 2^{0.1887d}. The improvement matters because the Shortest Vector Problem (SVP) in high-dimensional lattices underpins post-quantum public-key cryptography; faster attacks help calibrate security parameters. The algorithm solves the 'find many triples' subproblem: given a list of m uniform unit vectors, find m triples (x,y,z) with ||x−y−z|| ≤ 1. It does so with nested two-level amplitude amplification, guided by random product codes that preassociate each list vector with nearby center points. If correct, this is the fastest known quantum SVP algorithm when total memory is limited to 2^{0.1887d}.

What carries the argument

The central mechanism is nested amplitude amplification run in three layers, applied to a two-oracle search: first find R-collisions (pairs of list vectors sharing a center point c under relation R), refine to pairs with inner product about cos(θ), then for each pair search z among vectors sharing an R′-collision with the normalized difference, flagging triples that satisfy the norm bound. The efficiency comes from random product codes (RPCs), structured random subsets of the sphere that are efficiently decodable yet behave like uniform random sets for collision probabilities; preprocessing stores the induced relations in a QCRAM data structure to allow fast superpositions. The two-stage nea

What would settle it

Simulate one sieving round with m = (27/16)^{d/4} random unit vectors and count triples (x,y,z) with ||x−y−z|| ≤ 1; if the observed count is far below the predicted m for d around 100–200, or if correlations among outputs from shared parents reduce the next round's yield, the 2^{0.2846d} attack fails. More directly, test whether the stronger property ⟨x,y⟩ ≈ 1/3 and ⟨(x−y)/||x−y||,z⟩ ≈ √(1/3) holds for m triples at this list size.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3.1: with a list of m = (27/16)^{d/4+o(d)} vectors drawn uniformly from the unit sphere, a quantum algorithm can find m triples with ||x−y−z|| ≤ 1 in time 2^{0.284551d+o(d)}, using 2^{0.1887d} classical and QCRAM bits and 2^{o(d)} qubits. Because these triples yield shorter lattice vectors in each sieving round, the theorem translates, under the paper's uniform heuristic, into a heuristic quantum SVP algorithm with the same exponent. The key is to search not over all triples but over pairs that share a nearby 'center point' from a random product code, and then over z close to the normalized difference x−y; a nested amplitude amplification replaces the nai

Load-bearing premise

The SVP claim rests on the uniform heuristic—that after each sieving round the list is, up to rescaling, an i.i.d. uniform sample from a thin spherical annulus; the paper concedes this is technically false because output vectors like x+y and x+z are correlated.

Editorial extensions

If this is right

  • Assuming the uniform heuristic, 3-tuple sieving becomes faster in quantum time than the best classical 2-tuple sieving while using less memory.
  • At a memory cap of 2^{0.1887d}, this is the fastest heuristic quantum SVP algorithm currently known.
  • The algorithm avoids quantum-readable quantum-writable quantum memory: it needs only 2^{o(d)} qubits and QCRAM, a more conservative hardware assumption.
  • For cryptographic parameter setting, the modest exponent drop does not overturn security estimates, since these already budget for a quadratic quantum speedup.

Reading between the lines

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

  • A direct numerical test is to simulate the 'find many triples' step with random unit vectors at intermediate dimensions and measure whether m triples satisfying ||x−y−z|| ≤ 1 appear at list size (27/16)^{d/4}; if correlations cut the yield, the practical exponent worsens.
  • The same recipe—nested amplitude amplification with RPC-preprocessed center points—could be tried for 4-tuple sieving or the approximate k-list problem, potentially lowering memory-limited exponents further.
  • For a rigorous worst-case SVP guarantee, one would need to replace the uniform heuristic by perturbation or discrete Gaussian sampling; the gap between the heuristic exponent and a provable one remains to be quantified.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper presents a quantum algorithm for 3-tuple lattice sieving, targeting the k-list problem (Problem 1): given a list of m i.i.d. uniform samples on the unit sphere, find m triples (x,y,z) with ||x−y−z|| ≤ 1. The main result (Theorem 3.1) is a quantum algorithm solving this random-list problem for m = (27/16)^{d/4+o(d)} = 2^{0.1887d+o(d)} in time 2^{0.2846d+o(d)}, using QCRAM and 2^{o(d)} qubits. This improves the previous 2^{0.3098d} quantum exponent for 3-tuple sieving. The algorithm combines nested amplitude amplification with locality-sensitive filtering based on random product codes (RPCs). The SVP application (Heuristic Claim 1) relies on the standard uniform heuristic, which the paper explicitly acknowledges to be technically false but widely used in heuristic sieving. The core theorem for the random-list problem is proved rigorously with detailed pseudocode and a chain of lemmas.

Significance. If the result holds, it is a concrete improvement in the quantum time exponent for low-memory 3-tuple sieve, and it gives the fastest known heuristic quantum SVP algorithm in the 2^{0.1887d}-memory regime. The paper's strengths include: full pseudocode for every subroutine, machine-checkable lemmas for the random-list problem, explicit parameter choices, and a clear separation between the rigorous Theorem 3.1 and the heuristic SVP claim. The use of only 2^{o(d)} qubits is a practical advantage over quantum-walk approaches that need exponential qubit memory. The improvement, while modest, is in line with recent progress in the area.

major comments (2)
  1. [§3.6, proof of Theorem 3.1] I checked the numerical concern raised by the stress-test about the bound W(θ,α|α) ≥ 2^{−0.136318d}. The apparent contradiction with Lemma 2.8 stems from a misreading of the three-argument notation. Here W(θ,α|α) means cap angles θ and α with center separation α, not the α=β special case of Lemma 2.8. Using the general formula in Lemma 2.8 with cosθ=1/3 and cosα=0.347606 gives W(θ,α|α) ≈ 2^{−0.13636d}, consistent with the claimed bound. The other quoted exponents (pα, pα′, mW(θ′,α′|α′)) also match direct numerical evaluation up to the stated o(d) terms. The stress-test concern does not land.
  2. [§3.6, Lemma 3.16] The statement of Lemma 3.16 lists the assumption mpθ′ = 2^{o(d)}. For the parameters used in Theorem 3.1, mpθ′ is actually 2^{−Θ(d)} (about 2^{−0.1038d}), not 2^{o(d)}. The proof, however, only needs the weaker condition mpθ′ ≤_d 1, which does hold. This is a wording error in the lemma statement, not a flaw in the argument, but it should be corrected for precision.
minor comments (3)
  1. [§2.4] The notation W(α,β|θ) with three angular arguments is easy to misread, as happened in review. Consider adding a remark that W(θ,α|α) denotes cap angles θ and α with center separation α, not a permutation of the arguments.
  2. [§3.6, proof of Theorem 3.1] The phrase 'cos(θ′) is so close to 1/√3 that we will without loss of generality assume they are equal' is informal. Since the difference is subexponential, a short justification using the definition of equality up to 2^{o(d)} would strengthen the exposition.
  3. [§4.2] Heuristic 1 is explicitly acknowledged as 'technically incorrect'. This is appropriately candid, but the SVP claim in Heuristic Claim 1 should perhaps be phrased as a conjecture under the uniform heuristic to avoid any ambiguity that it is a theorem.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation; only a non-load-bearing self-citation, with the main caveats being heuristic assumptions and a numerical correctness concern.

full rationale

The paper's central derivation is not circular. Theorem 3.1 is obtained by optimizing the parameters α and α′ inside the exact cost expression (4); the exponents p_α, p_α′, W(θ,α|α), and W(θ′,α′|α′) are computed from the geometric Formulas in Lemma 2.7/Lemma 2.8, not fitted to the claimed runtime, so no prediction is statistically forced. The RPC facts are imported from [BDGL16] as independent prior results, and the volume lemmas are quoted with proofs referenced there. Heuristic 1 is explicitly flagged by the paper itself as 'of course, technically incorrect,' so the SVP application is openly heuristic rather than a hidden restatement of the result. The only author-overlapping citation is [ACKS25] in Section 1.1, which is used only to state a known worst-case quantum SVP exponent and plays no role in the 3-tuple sieving analysis; it is therefore a minor self-citation but not load-bearing. The skeptic's numerical concern about the lower bound W(θ,α|α) ≥ 2^{-0.136318d+o(d)} in the proof of Theorem 3.1 is a correctness risk: if the bound is wrong, the displayed 2^{0.284551d+o(d)} exponent may not follow from the written proof. That is a substantive mathematical issue, but it is not a circularity because the bound is not being used as its own conclusion, and no equation reduces to its own input by construction.

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

The central theorem rests on standard geometry, a cited RPC behavior lemma, and a quantum search primitive. The only genuinely assumed entity is the uniform heuristic, which the paper itself flags as technically false. The algorithmic parameters α, α′, ℓ, t are optimization/technical choices, not empirically fitted constants. No new physical or mathematical entities are introduced.

free parameters (4)
  • α (first RPC collision angle) = cos α = 0.347606
    Chosen by hand in the proof of Theorem 3.1 to balance the sizes of T0(R), T1(R), T_sol and the preprocessing/search costs; it is an optimization parameter, not fitted to data.
  • α′ (second RPC collision angle) = cos α′ = 0.427124
    Selected together with α to minimize the final time exponent while satisfying constraints (I) and (II) in the proof of Theorem 3.1.
  • ℓ (number of RPC repetitions in 3List) = ℓ = (pα/W(α,α|θ)) (pα′/W(α′,α′|θ′)) 2^{o(d)}
    Algorithm parameter set large enough to ensure every target triple is covered by some sampled RPC pair; contributes only 2^{o(d)} to complexity.
  • t (coupon-collector search threshold) = t = 2^{o(d)}
    Technical parameter in Lemma 2.4/Algorithm 1 chosen large enough to find all elements of T_sol(R,R′) without knowing its size; contributes only 2^{o(d)}.
assumptions (5)
  • domain assumption Heuristic 1 (uniform heuristic): after each sieving iteration, lattice vectors behave as i.i.d. uniform samples on a thin annulus after rescaling.
    Stated in Section 4.2 and explicitly acknowledged as "technically incorrect"; it is load-bearing for Heuristic Claim 1 (SVP application), though not for Theorem 3.1.
  • domain assumption Random product codes behave like uniform random subsets for collision probabilities (BDGL16 Theorem 5.1, restated as Lemma 2.13).
    The success probability and parameter balancing of the algorithm rely on this quoted prior lemma; invoked throughout Section 3.
  • standard math Spherical cap and wedge volume asymptotics (Lemmas 2.7, 2.8, and approximate versions 2.9, 2.10).
    Background geometry from BDGL16 used to estimate pα, pα′, W(α,α|θ), W(α′,α′|θ′).
  • standard math Fixed-point amplitude amplification (Lemma 2.3) works with superexponentially small failure probability at subexponential overhead.
    Standard primitive from [GSLW19, YLC14]; used as the outer and inner search engine.
  • domain assumption QCRAM model: a classical writable memory supports quantum random-access queries at O(log n) cost per query.
    Computational model defined in Section 2.3.1; the authors note the physical implementation is "nontrivial and controversial" due to quantum error-correction costs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Improved Quantum Algorithm for 3-Tuple Lattice Sieving." pith.science (2026). https://pith.science/paper/HAI2ST74

@misc{pith2026251008473,
  author       = {Pith},
  title        = {Pith review of: An Improved Quantum Algorithm for 3-Tuple Lattice Sieving},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HAI2ST74}},
  note         = {Machine review of arXiv:2510.08473}
}
abstract

The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension $d$, they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. $k$-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of $k$ of the input vectors. Iterating these ''sieving steps'' sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for $k=2$, but taking larger $k$ reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from $2^{0.3098 d}$ to $2^{0.2846 d}$, using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby ''center points'' to focus the search on the neighborhoods of these center points. Our algorithm uses $2^{0.1887d}$ classical bits and QCRAM bits, and $2^{o(d)}$ qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to $2^{0.1887d}$.

Figures

Figures reproduced from arXiv: 2510.08473 by the authors.

Figure 1
Figure 1. Illustration of the two-oracle search setup, where the task is to search for elements in the search [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Structure of the algorithm 3List, which repeats the following. First, the Sampling phase produces a pair (R, R′ ) of random relations that are stored in a data structure during the Preprocessing phase. The algorithm then repeatedly calls SolutionSearch, which is instructed to find an element of Tsol using a nested amplitude amplification (AA). Given a subroutine RCollisionSamp that creates a superposition over R-col… view at source ↗
Figure 3
Figure 3. Summary of the relations between vectors encountered during the [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

41 extracted references · 5 linked inside Pith

  1. [1]

    Improved classical and quantum algorithms for the shortest vector problem via bounded distance decoding

    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

    2025

  2. [2]

    Albrecht, L \'e o Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W

    Martin R. Albrecht, L \'e o Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite, and Marc Stevens. The general sieve kernel and new records in lattice reduction. In Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages 717--746. Springer, 2019

    2019

  3. [3]

    Solving the shortest vector problem in 2\( ^ n \) time using discrete G aussian sampling: Extended abstract

    Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens - Davidowitz. Solving the shortest vector problem in 2\( ^ n \) time using discrete G aussian sampling: Extended abstract. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing , pages 733--742, 2015

    2015

  4. [4]

    Generating hard instances of lattice problems (extended abstract)

    Mikl \' o s Ajtai. Generating hard instances of lattice problems (extended abstract). In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing , pages 99--108, 1996

    1996

  5. [5]

    Sivakumar

    Mikl \'o s Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing , pages 601--610, 2001

    2001

  6. [6]

    Quantum walk algorithm for element distinctness

    Andris Ambainis. Quantum walk algorithm for element distinctness. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS 2004) , pages 22--31, 2004

    2004

  7. [7]

    Quantum search with variable times

    Andris Ambainis. Quantum search with variable times. Theory of Computing Systems , 47(3):786--807, 2010

    2010

  8. [8]

    Just take the average! A n 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 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA , pages 12:1--12:19, 2018

    2018

Show all 41 references
  1. [9]

    Finding many collisions via reusable quantum walks

    Xavier Bonnetain, Andr \'e Chailloux, Andr \'e Schrottenloher, and Yixin Shen. Finding many collisions via reusable quantum walks. In Proceedings of the Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptograph...

    2023

  2. [10]

    New directions in nearest neighbor searching with applications to lattice sieving

    Anja Becker, L \' e o Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 10--24, 2016

    2016

  3. [11]

    Quantum amplitude amplification and estimation

    Gilles Brassard, Peter H yer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Information , volume 305 of Contemporary Mathematics , pages 53--74. American Mathematical Society, 2002

    2002

  4. [12]

    Quantum algorithm for the collision problem

    Gilles Brassard, Peter H yer, and Alain Tapp. Quantum algorithm for the collision problem. In Third Latin Symposium on Theoretical Informatics (LATIN 1998) , pages 163--169, 1998. arXiv:quant-ph/9705002

    1998 arXiv

  5. [13]

    Tuple lattice sieving

    Shi Bai, Thijs Laarhoven, and Damien Stehl \' e . Tuple lattice sieving. LMS Journal of Computational Mathematics , 19(A):146--162, 2016

    2016

  6. [14]

    Lattice-based FHE as secure as PKE

    Zvika Brakerski and Vinod Vaikuntanathan. Lattice-based FHE as secure as PKE . In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science , pages 1--12, 2014

    2014

  7. [15]

    A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations

    Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics , 23(4):493 -- 507, 1952

    1952

  8. [16]

    Lattice sieving via quantum random walks

    Andr \'e Chailloux and Johanna Loyer. Lattice sieving via quantum random walks. In Proceedings of the Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security , 2021

    2021

  9. [17]

    Classical and quantum 3 and 4-sieves to solve SVP with low memory

    Andr \'e Chailloux and Johanna Loyer. Classical and quantum 3 and 4-sieves to solve SVP with low memory. In International Conference on Post-Quantum Cryptography , pages 225--255. Springer, 2023

    2023

  10. [18]

    Another NP-complete partition problem and the complexity of computing short vectors in a lattice

    Peter Emde v an Emde Boas. Another NP-complete partition problem and the complexity of computing short vectors in a lattice . Report. Department of Mathematics. University of Amsterdam. 1981

    1981

  11. [19]

    Fully homomorphic encryption using ideal lattices

    Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing , pages 169--178, 2009

    2009

  12. [20]

    Quantum singular value transformation and beyond: E xponential improvements for quantum matrix arithmetics

    Andr \'a s Gily \'e n, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: E xponential improvements for quantum matrix arithmetics. In Proceedings of the 51st ACM Symposium on the Theory of Computing , pages 193--204, 2019. arXiv:1806.0...

    2019 arXiv

  13. [21]

    Improved quantum hypercone locality sensitive filtering in lattice sieving

    Max Heiser. Improved quantum hypercone locality sensitive filtering in lattice sieving. Cryptology ePrint Archive, Paper 2021/1295, 2021

    2021

  14. [22]

    Improved algorithms for the approximate k-list problem in E uclidean norm

    Gottfried Herold and Elena Kirshanova. Improved algorithms for the approximate k-list problem in E uclidean norm. In Public-Key Cryptography - PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings, Part I , volume 10174 of...

    2017

  15. [23]

    Speed-ups and time-memory trade-offs for tuple lattice sieving

    Gottfried Herold, Elena Kirshanova, and Thijs Laarhoven. Speed-ups and time-memory trade-offs for tuple lattice sieving. In Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings, Part I , volume 1...

    2018

  16. [24]

    Algorithms for the shortest and closest lattice vector problems

    Guillaume Hanrot, Xavier Pujol, and Damien Stehl \' e . Algorithms for the shortest and closest lattice vector problems. In Proceedings of Coding and Cryptology - Third International Workshop, IWCC 2011 , volume 6639 of Lecture Notes in Computer Science , pages 159--190, 2011

    2011

  17. [25]

    Oracles with costs

    Shelby Kimmel, Cedric Yen - Yu Lin, and Han - Hsuan Lin. Oracles with costs. In Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography , volume 44 of LIPIcs , pages 1--26. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2015

    2015

  18. [26]

    Postlethwaite, and Subhayan Roy Moulik

    Elena Kirshanova, Erik M rtensson, Eamonn W. Postlethwaite, and Subhayan Roy Moulik. Quantum algorithms for the approximate k -list problem and their application to lattice sieving. In Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Ap...

    2019

  19. [27]

    Search problems in cryptography, from fingerprinting to lattice sieving

    Thijs Laarhoven. Search problems in cryptography, from fingerprinting to lattice sieving . PhD thesis, Eindhoven University of Technology, 2016

    2016

  20. [28]

    Finding shortest lattice vectors faster using quantum search

    Thijs Laarhoven, Michele Mosca, and Joop van de Pol . Finding shortest lattice vectors faster using quantum search. Designs, Codes and Cryptography , 77, 12 2015

    2015

  21. [29]

    Worst-case to average-case reductions based on G aussian measures

    Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on G aussian measures. SIAM Journal on Computing , 37(1):267--302, 2007

    2007

  22. [30]

    Lattice-based cryptography, 2008

    Daniele Micciancio and Oded Regev. Lattice-based cryptography, 2008. https://cims.nyu.edu/ regev/papers/pqc.pdf

    2008

  23. [31]

    Probability and Computing: Randomized Algorithms and Probabilistic Analysis

    Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press, USA, 2005

    2005

  24. [32]

    Faster exponential time algorithms for the shortest vector problem

    Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector problem. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms , pages 1468--1480. SIAM, 2010

    2010

  25. [33]

    Nguyen and Thomas Vidick

    Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology , 2(2):181--207, 2008

    2008

  26. [34]

    Solving the shortest lattice vector problem in time 2\( ^ 2.465n \)

    Xavier Pujol and Damien Stehl \' e . Solving the shortest lattice vector problem in time 2\( ^ 2.465n \). Cryptology ePrint Archive, Paper 2009/605, 2009

    2009

  27. [35]

    Lattices in computer science, lecture 8, 2004

    Oded Regev. Lattices in computer science, lecture 8, 2004. https://cims.nyu.edu/ regev/teaching/lattices_fall_2004/ln/svpalg.pdf

    2004

  28. [36]

    Lattice-based cryptography

    Oded Regev. Lattice-based cryptography. In Proceedings of the Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference , pages 131--141, 2006

    2006

  29. [37]

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

    Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM , 56(6):1--40, 2009. Earlier version in STOC'05. arXiv:2401.03703 https://arxiv.org/abs/2401.03703

    2009 arXiv

  30. [38]

    A hierarchy of polynomial time lattice basis reduction algorithms

    Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science , 53:201--224, 1987

    1987

  31. [39]

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

    1994

  32. [40]

    Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer

    Peter Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing , 26(5):1484--1509, 1997. Earlier version in FOCS'94. arXiv:quant-ph/9508027 https://arxiv.org/abs/quant-ph/9508027

    1997 arXiv

  33. [41]

    Yoder, Guang Hao Low, and Isaac L

    Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang. Fixed-point quantum search with an optimal number of queries. Physical Review Letters , 113(21):210501, 2014. arXiv:1409.3305 https://arxiv.org/abs/1409.3305

    2014 arXiv

Pith tools

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