Pith. sign in

REVIEW 2 major objections 2 minor 2 cited by

Quantum algorithm for Discrete Gaussian Sampling

T0 review · 2 major / 2 minor · reviewed 2026-05-20 · grok-4.3

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

Pith's one-line read A quantum rejection sampling algorithm produces discrete Gaussian samples on lattices with asymptotic quadratic speedup over the best classical method.

desk verdict The paper claims a quadratic quantum speedup for discrete Gaussian sampling via rejection sampling and applies it to improve dual attacks, but lacks the resource and error details needed to confirm the advantage holds. read the letter →

arxiv 2605.20133 v1 pith:IABNC3CR submitted 2026-05-19 quant-ph

Clémence Chevignard , Yixin Shen , André Schrottenloher This is my paper · ORCID
classification quant-ph
keywords discretegaussiansamplingquantumalgorithmlattice-basedcryptographyrejectiondualattacksshortintegersolutioncryptanalysis
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

The paper constructs a quantum algorithm for discrete Gaussian sampling on lattices by adapting the quantum rejection sampling technique. This yields a procedure whose complexity scales quadratically better than the leading classical sampler. The output is a quantum state that can be measured to obtain classical samples or fed directly into other quantum routines. Applying the sampler produces two improved versions of quantum dual attacks on lattice problems, one emphasizing speed and the other emphasizing low memory use. The same tool also accelerates quantum algorithms for the Short Integer Solution problem in arbitrary norms.

What carries the argument

Quantum rejection sampling technique applied to discrete Gaussian distributions on lattices, which prepares the target quantum state with reduced query or gate complexity.

What would settle it

A gate-by-gate resource count or small-parameter simulation on a quantum simulator that shows the total quantum operations required to reach a target statistical distance and whether that count is asymptotically half the classical count.

Watch

Extended reading notes

Core claim

We show a quantum algorithm based on the quantum rejection sampling technique whose complexity is asymptotically quadratically faster than its classical counterpart. Our sampler outputs a quantum state which can either be measured to get the desired distribution or be used directly as such in other quantum algorithms. By doing so, we derive two versions of quantum dual attacks that improve upon the previous ones. The second version requires only polynomial classical and quantum memory, excluding the classical memory used in the preprocessing step. Our quantum Discrete Gaussian sampler can also be used to speed up the algorithm for solving the Short Integer Solution problem, in any norm.

Load-bearing premise

The quantum rejection sampling technique can be instantiated for discrete Gaussian sampling on lattices without hidden polynomial factors or extra quantum resources that cancel the quadratic advantage.

Editorial extensions

If this is right

  • Two incomparable quantum dual attacks become available, one faster and one with only polynomial memory outside preprocessing.
  • The Short Integer Solution problem in any norm admits a quadratic quantum speedup via the new sampler.
  • The produced quantum state can be reused inside larger quantum algorithms without immediate measurement.
  • Classical and quantum memory requirements are separated so that only polynomial quantum memory is needed in one attack variant.

Reading between the lines

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

  • If the quadratic scaling survives concrete error analysis, security estimates for lattice-based signatures and encryption against quantum adversaries would need revision.
  • The low-memory attack variant could be run on near-term quantum devices that have limited qubit counts but access to classical preprocessing.
  • Similar rejection-sampling constructions might yield speedups for other lattice sampling tasks such as continuous Gaussians or uniform sampling over cosets.
  • Integration with existing quantum lattice algorithms could compound speedups for end-to-end cryptanalysis pipelines.
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, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The manuscript presents a quantum algorithm for discrete Gaussian sampling over lattices based on quantum rejection sampling. It claims an asymptotic quadratic speedup in complexity relative to the classical sampler of Wang & Ling (IEEE Trans. Inf. Theory 2019). The algorithm outputs a quantum state that can be measured to obtain samples from the target distribution or used directly in subsequent quantum algorithms. The work derives two incomparable versions of quantum dual attacks that improve on Pouly & Shen (EUROCRYPT 2024), one emphasizing speed and the other polynomial memory (excluding preprocessing), and indicates an application to speeding up the Short Integer Solution problem solver of Bollauf, Pouly & Shen (ePrint 2026/225).

Significance. If the quadratic speedup is realized with only polylogarithmic overheads in the lattice dimension n and Gaussian parameter, and if the output state is shown to be close to the target distribution in total variation distance, the result would strengthen quantum cryptanalysis tools for lattice-based schemes. The direct usability of the quantum state and the memory-efficient dual-attack variant are potentially valuable features. The work would be more significant if it supplies explicit oracle query counts and error analysis that confirm the advantage is not cancelled by lattice-basis operations.

major comments (2)
  1. [Abstract] Abstract: the claim that the quantum rejection sampling technique yields an 'asymptotically quadratically faster' sampler is load-bearing for the central contribution, yet the text supplies neither the query complexity of the quantum oracle implementing the acceptance function nor an error analysis establishing that the output state is within negligible total-variation distance of the target discrete Gaussian without additional poly(n) factors.
  2. [Quantum dual attacks] The section deriving the two quantum dual attacks: the assertion that the second version requires only polynomial classical and quantum memory (excluding preprocessing) must be accompanied by a concrete resource count showing that the quantum state preparation and measurement steps do not introduce hidden polynomial costs in n that would erase the claimed quadratic advantage over prior work.
minor comments (2)
  1. [Abstract] The citation 'Bollauf, Pouly & Shen, ePrint 2026/225' should be verified for the correct year and arXiv identifier.
  2. [Introduction] Notation for the lattice dimension n and Gaussian parameter should be introduced consistently when first used in the complexity statements.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We have revised the paper to provide the requested explicit details on oracle query complexity, error bounds, and resource counts. Our point-by-point responses to the major comments follow.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that the quantum rejection sampling technique yields an 'asymptotically quadratically faster' sampler is load-bearing for the central contribution, yet the text supplies neither the query complexity of the quantum oracle implementing the acceptance function nor an error analysis establishing that the output state is within negligible total-variation distance of the target discrete Gaussian without additional poly(n) factors.

    Authors: We agree that the abstract would benefit from more explicit pointers to the supporting analysis. In the revised manuscript we have updated the abstract to state that the acceptance oracle is realized with O(log n) quantum queries to a classical evaluation oracle and that the output state is within total-variation distance 2^{-Ω(n)} of the target distribution. The full query-complexity derivation appears in Section 3 and the total-variation error analysis (showing no extra polynomial factors in n) is given in Section 4. These additions make the quadratic speedup claim self-contained while preserving the high-level nature of the abstract. revision: yes

  2. Referee: [Quantum dual attacks] The section deriving the two quantum dual attacks: the assertion that the second version requires only polynomial classical and quantum memory (excluding preprocessing) must be accompanied by a concrete resource count showing that the quantum state preparation and measurement steps do not introduce hidden polynomial costs in n that would erase the claimed quadratic advantage over prior work.

    Authors: We accept the need for a concrete accounting. The revised manuscript now includes a dedicated resource table and accompanying text in the quantum dual attacks section. Quantum state preparation for each discrete-Gaussian sample uses O(n log n) qubits and O(n log n) gates; a single measurement consumes one query to the acceptance oracle. These costs are polynomial in n yet remain lower-order compared with the quadratic improvement in the dominant sampling term relative to Pouly & Shen. The table also lists the polynomial classical memory (excluding the one-time preprocessing table) and confirms that the overall attack complexity retains the claimed quadratic advantage. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: quantum rejection sampling algorithm derived independently of inputs

full rationale

The paper introduces a quantum algorithm for discrete Gaussian sampling on lattices via quantum rejection sampling, claiming asymptotic quadratic speedup over the classical sampler of Wang & Ling (2019). The derivation chain relies on standard quantum techniques applied to the lattice setting, with no equations or steps that reduce a claimed prediction or result to a fitted parameter, self-defined quantity, or self-citation by construction. Citations to prior work (including overlapping-author reference to Pouly & Shen EUROCRYPT 2024 for context on dual attacks) are used for comparison and extension but do not bear the load of proving the core sampler's correctness or complexity; the algorithm is presented as a direct instantiation with independent resource analysis. No renaming of known results or ansatz smuggling occurs. The central claim remains self-contained and externally falsifiable against the cited classical baseline.

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

Abstract-only review; limited visibility into internal assumptions. Relies on standard quantum computing model and correctness of quantum rejection sampling.

assumptions (1)
  • domain assumption Quantum rejection sampling can be applied to discrete Gaussian distributions on lattices with quadratic speedup
    Central to the claimed complexity improvement; location: abstract description of the algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum algorithm for Discrete Gaussian Sampling." pith.science (2026). https://pith.science/paper/IABNC3CR

@misc{pith2026260520133,
  author       = {Pith},
  title        = {Pith review of: Quantum algorithm for Discrete Gaussian Sampling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IABNC3CR}},
  note         = {Machine review of arXiv:2605.20133}
}
read the original abstract

Discrete Gaussian Sampling on lattices is a fundamental problem in lattice-based cryptography. It appears both in basic cryptographic primitives such as digital signatures and as an important cryptanalysis building block for solving hard lattice problems. In this paper, we show a quantum algorithm based on the quantum rejection sampling technique whose complexity is asymptotically quadratically faster than its classical counterpart in [Wang & Ling, IEEE Trans. Inf. Theory 2019]. Our sampler outputs a quantum state which can either be measured to get the desired distribution or be used directly as such in other quantum algorithms. By doing so, we derive two versions of quantum dual attacks that improve upon the previous ones in [Pouly & Shen, EUROCRYPT 2024]. The two versions are incomparable, each having distinct advantages (speed vs memory requirement). The second version is particularly interesting as it requires only polynomial classical and quantum memory, excluding the classical memory used in the preprocessing step of the Discrete Gaussian sampler. Our quantum Discrete Gaussian sampler can also be used to speed up the algorithm for solving the Short Integer Solution problem, in any norm, of [Bollauf, Pouly & Shen, ePrint 2026/225].

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. One Discrete Gaussian Sample in $2^{n/2+o(n)}$ Time

    cs.DS 2026-08 conditional novelty 8.0 of 10

    One discrete Gaussian sample at an arbitrary parameter can be drawn in 2^(n/2+o(n)) expected time, resolving an open question from ADRS15.

  2. Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding

    quant-ph 2026-07 accept novelty 7.0 of 10

    Sparse QROM has optimal Clifford+T cost Θ(√(sm)+√(sn)), yielding matching optimal T-counts for s-sparse state preparation and s-sparse block encoding.

Reference graph

Works this paper leans on

52 extracted references · 52 canonical work pages · cited by 2 Pith papers

  1. [1]

    In: STACS

    Aggarwal, D., Chen, Y., Kumar, R., Shen, Y.: Improved (provable) algorithms for the shortest vector problem via bounded distance decoding. In: STACS. LIPIcs, vol. 187, pp. 4:1–4:20. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik (2021). https://doi.org/10.4230/LIPICS.STACS.2021.4

    work page doi:10.4230/lipics.stacs.2021.4 2021

  2. [2]

    Aggarwal, D., Chen, Y., Kumar, R., Shen, Y.: Improved classical and quantum algorithms for the shortest vector problem via bounded distance decoding. SIAM J. Comput.54(2), 233–278 (2025).https://doi.org/10.1137/22M1486959,https: //doi.org/10.1137/22m1486959

    work page doi:10.1137/22m1486959 2025

  3. [3]

    Ambainis, Y

    Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the short- est vector problem in 2 n time using discrete gaussian sampling: Extended ab- stract. In: STOC. pp. 733–742. ACM (2015).https://doi.org/10.1145/2746539. 2746606

    work page doi:10.1145/2746539 2015

  4. [4]

    Aharonov, D., Regev, O.: Lattice problems in NP cap conp. J. ACM52(5), 749– 765 (2005).https://doi.org/10.1145/1089023.1089025,https://doi.org/10. 1145/1089023.1089025 29

    work page doi:10.1145/1089023.1089025 2005

  5. [5]

    Ajtai, Generating hard instances of lattice problems, extended abstract, in Proceedings of the 28th ACM Symposium on Theory of Computing, ACM, 1996, pp

    Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC. pp. 99–108. ACM (1996).https://doi.org/10.1145/237814.237838

    work page doi:10.1145/237814.237838 1996

  6. [6]

    In: EUROCRYPT (2)

    Albrecht, M.R.: On dual lattice attacks against small-secret LWE and pa- rameter choices in helib and SEAL. In: EUROCRYPT (2). Lecture Notes in Computer Science, vol. 10211, pp. 103–129 (2017).https://doi.org/10.1007/ 978-3-319-56614-6_4

    work page 2017

  7. [7]

    In: ASIACRYPT (2)

    Albrecht, M.R., Gheorghiu, V., Postlethwaite, E.W., Schanck, J.M.: Estimating quantum speedups for lattice sieves. In: ASIACRYPT (2). pp. 583–613. Lec- ture Notes in Computer Science, Springer (2020).https://doi.org/10.1007/ 978-3-030-64834-3_20

    work page 2020

  8. [8]

    IACR Cryptol

    Albrecht, M.R., Shen, Y.: Quantum augmented dual attack. IACR Cryptol. ePrint Arch. p. 656 (2022),https://eprint.iacr.org/2022/656

    work page 2022

Show all 52 references
  1. [9]

    In: ASIACRYPT (1)

    Aono, Y., Nguyen, P.Q., Shen, Y.: Quantum lattice enumeration and tweaking dis- crete pruning. In: ASIACRYPT (1). Lecture Notes in Computer Science, vol. 11272, pp. 405–434. Springer (2018).https://doi.org/10.1007/978-3-030-03326-2_14

    2018 doi

  2. [10]

    de Boer, K.: Random Walks on Arakelov Class Groups. Ph.D. thesis, Leiden Uni- versity (2022),https://hdl.handle.net/1887/3463719, phD thesis, Institutional Repository of Leiden University

    2022

  3. [11]

    IACR Cryptol

    de Boer, K., Felderhoff, J.: Quantumly computing s-unit groups in quantified polynomial time and space. IACR Cryptol. ePrint Arch. p. 1825 (2025),https: //eprint.iacr.org/2025/1825

    2025

  4. [12]

    Cryptology ePrint Archive, Paper 2026/225 (2026),https://eprint.iacr.org/ 2026/225

    Bollauf, M.F., Pouly, A., Shen, Y.: Solving SIS in any norm via gaussian sampling. Cryptology ePrint Archive, Paper 2026/225 (2026),https://eprint.iacr.org/ 2026/225

    2026

  5. [13]

    In: EUROCRYPT (5)

    Bonnetain, X., Chailloux, A., Schrottenloher, A., Shen, Y.: Finding many collisions via reusable quantum walks - application to lattice sieving. In: EUROCRYPT (5). Lecture Notes in Computer Science, vol. 14008, pp. 221–251. Springer (2023). https://doi.org/10.1007/978-3-031-30589-4_8

    2023 doi

  6. [14]

    In: EuroS&P

    Bos, J.W., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Schwabe, P., Seiler, G., Stehl´ e, D.: CRYSTALS - kyber: A cca-secure module- lattice-based KEM. In: EuroS&P. pp. 353–367. IEEE (2018).https://doi.org/ 10.1109/EUROSP.2018.00032

    2018 doi

  7. [15]

    Fortschritte der Physik: Progress of Physics46(4-5), 493–505 (1998).https://doi

    Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics46(4-5), 493–505 (1998).https://doi. org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P

    1998 doi

  8. [16]

    In: STOC

    Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehl´ e, D.: Classical hardness of learning with errors. In: STOC. pp. 575–584. ACM (2013).https://doi.org/ 10.1145/2488608.2488680

    2013 doi

  9. [17]

    Contemporary Mathematics305, 53–74 (2002).https://doi.org/ 10.1090/conm/305/05215

    Brassard, G., Hoyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Contemporary Mathematics305, 53–74 (2002).https://doi.org/ 10.1090/conm/305/05215

    2002 doi

  10. [18]

    In: CRYPTO (1)

    Carrier, K., Meyer-Hilfiger, C., Shen, Y., Tillich, J.: Assessing the impact of a variant of matzov’s dual attack on kyber. In: CRYPTO (1). Lecture Notes in Computer Science, vol. 16000, pp. 444–476. Springer (2025).https://doi.org/ 10.1007/978-3-032-01855-7_15

    2025 doi

  11. [19]

    IACR Cryptol

    Carrier, K., Shen, Y., Tillich, J.: Faster dual lattice attacks by using coding theory. IACR Cryptol. ePrint Arch. p. 1750 (2022)

    2022

  12. [20]

    In: ASI- ACRYPT (4)

    Chailloux, A., Loyer, J.: Lattice sieving via quantum random walks. In: ASI- ACRYPT (4). Lecture Notes in Computer Science, vol. 13093, pp. 63–91. Springer (2021).https://doi.org/10.1007/978-3-030-92068-5_3 30

    2021 doi

  13. [21]

    ePrint Arch

    Cho, B., Hhan, M., Kim, T., Lee, J., Shen, Y.: Does quantum lattice sieving require quantum RAM? IACR Cryptol. ePrint Arch. p. 1700 (2024),https://eprint. iacr.org/2024/1700

    2024

  14. [22]

    Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehl´ e, D.: Crystals-dilithium algorithm specifications and supporting documen- tation (2017),https://api.semanticscholar.org/CorpusID:198994007

    2017

  15. [23]

    IACR Trans

    Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehl´ e, D.: Crystals-dilithium: A lattice-based digital signature scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst.2018(1), 238–268 (2018).https://doi.org/10. 13154/TCHES.V2018.I1.238-268,https://d...

    2018 doi

  16. [24]

    Lecture Notes in Computer Science, vol

    Ducas, L., Pulles, L.N.: Does the dual-sieve attack on learning with errors even work? In: CRYPTO (3). Lecture Notes in Computer Science, vol. 14083, pp. 37–69. Springer (2023).https://doi.org/10.1007/978-3-031-38548-3_2

    2023 doi

  17. [25]

    CoRRquant- ph/9607014(1996),http://arxiv.org/abs/quant-ph/9607014

    D¨ urr, C., Høyer, P.: A quantum algorithm for finding the minimum. CoRRquant- ph/9607014(1996),http://arxiv.org/abs/quant-ph/9607014

    1996

  18. [26]

    In: INDOCRYPT

    Espitau, T., Joux, A., Kharchenko, N.: On a dual/hybrid approach to small se- cret LWE - A dual/enumeration technique for learning with errors and application to security estimates of FHE schemes. In: INDOCRYPT. Lecture Notes in Com- puter Science, vol. 12578, pp. 440–462. Spr...

    2020

  19. [27]

    In: STOC

    Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC. pp. 197–206. ACM (2008).https://doi. org/10.1145/1374376.1374407

    2008 doi

  20. [28]

    In: ASIACRYPT (4)

    Guo, Q., Johansson, T.: Faster dual lattice attacks for solving LWE with ap- plications to CRYSTALS. In: ASIACRYPT (4). Lecture Notes in Computer Science, vol. 13093, pp. 33–62. Springer (2021).https://doi.org/10.1007/ 978-3-030-92068-5_2

    2021

  21. [29]

    In: ICALP

    Høyer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error inputs. In: ICALP. Lecture Notes in Computer Science, vol. 2719, pp. 291–299. Springer (2003).https://doi.org/10.1007/3-540-45061-0_25

    2003 doi

  22. [30]

    Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform. Theor. Comput. Sci.43(2–3), 169–188 (Jul 1986)

    1986

  23. [31]

    arXiv preprint arXiv:0801.0342 (2008)

    Kitaev, A., Webb, W.A.: Wavefunction preparation and resampling using a quan- tum computer. arXiv preprint arXiv:0801.0342 (2008)

    2008 arXiv

  24. [32]

    In: SODA

    Klein, P.N.: Finding the closest lattice vector when it’s unusually close. In: SODA. pp. 937–941. ACM/SIAM (2000).https://doi.org/DBLP:conf/soda/Klein00

    2000

  25. [33]

    Addison-Wesley, 4 edn

    Knuth, D.E.: The Art of Computer Programming, Volume 2: Seminumerical Al- gorithms. Addison-Wesley, 4 edn. (2011)

    2011

  26. [34]

    Laarhoven, T.: Search problems in cryptography: From fingerprinting to lattice sieving. Ph.D. thesis, Eindhoven University of Technology (2015)

    2015

  27. [35]

    In: PQCrypto

    Laarhoven, T., Mosca, M., van de Pol, J.: Solving the shortest vector problem in lattices faster using quantum search. In: PQCrypto. Lecture Notes in Com- puter Science, vol. 7932, pp. 83–101. Springer (2013).https://doi.org/10.1007/ 978-3-642-38616-9_6

    2013

  28. [36]

    MATZOV: Report on the security of LWE: Improved dual lattice attack (Apr 2022).https://doi.org/10.5281/zenodo.6412487,https://doi.org/10.5281/ zenodo.6412487

    2022 doi

  29. [38]

    Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput.37(1), 267–302 (2007).https://doi.org/10.1137/ S0097539705447360,https://doi.org/10.1137/S0097539705447360

    2007 doi

  30. [39]

    Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences471(2181), 20150301 (09 2015).https://doi.org/10.1098/rspa.2015.0301,https://doi

    Montanaro, A.: Quantum speedup of monte carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences471(2181), 20150301 (09 2015).https://doi.org/10.1098/rspa.2015.0301,https://doi. org/10.1098/rspa.2015.0301

    2015 doi

  31. [40]

    Cambridge University Press, USA, 10th edn

    Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, USA, 10th edn. (2011)

    2011

  32. [41]

    ACM Trans

    Ozols, M., Roetteler, M., Roland, J.: Quantum rejection sampling. ACM Trans. Comput. Theory5(3), 11:1–11:33 (2013).https://doi.org/10.1145/2493252. 2493256,https://doi.org/10.1145/2493252.2493256

    2013 doi

  33. [42]

    In: EURO- CRYPT (6)

    Pouly, A., Shen, Y.: Provable dual attacks on learning with errors. In: EURO- CRYPT (6). Lecture Notes in Computer Science, vol. 14656, pp. 256–285. Springer (2024).https://doi.org/10.1007/978-3-031-58754-2_10

    2024 doi

  34. [43]

    In: PQCrypto (2)

    Pouly, A., Shen, Y.: Discrete gaussian sampling for BKZ-reduced basis. In: PQCrypto (2). Lecture Notes in Computer Science, vol. 15578, pp. 63–88. Springer (2025).https://doi.org/10.1007/978-3-031-86602-9_3

    2025 doi

  35. [44]

    Post-Quantum Cryptogra- phy Project of NIST (2020)

    Prest, T., Fouque, P.A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Ricosset, T., Seiler, G., Whyte, W., Zhang, Z.: Falcon. Post-Quantum Cryptogra- phy Project of NIST (2020)

    2020

  36. [45]

    In: ASIACRYPT (3)

    Qu, H., Xu, G.: On the provable dual attack for LWE by modulus switching. In: ASIACRYPT (3). Lecture Notes in Computer Science, vol. 16247, pp. 34–64. Springer (2025).https://doi.org/10.1007/978-981-95-5099-9_2

    2025 doi

  37. [46]

    Regev, O.: On lattices, learning with errors, random linear codes, and cryptogra- phy. vol. 56, pp. 34:1–34:40 (2009).https://doi.org/10.1145/1568318.1568324, https://doi.org/10.1145/1568318.1568324

    2009 doi

  38. [47]

    In: STOC

    Regev, O., Stephens-Davidowitz, N.: A reverse minkowski theorem. In: STOC. pp. 941–953. ACM (2017).https://doi.org/DBLP:conf/stoc/0001S17

    2017

  39. [48]

    Sanders, Y.R., Low, G.H., Scherer, A., Berry, D.W.: Black-box quantum state preparation without arithmetic. Phys. Rev. Lett.122, 020502 (Jan 2019). https://doi.org/10.1103/sanders2019black,https://link.aps.org/doi/10. 1103/sanders2019black

    2019 doi

  40. [49]

    IEEE Trans

    Wang, Z., Ling, C.: Lattice gaussian sampling by markov chain monte carlo: Bounded distance decoding and trapdoor sampling. IEEE Trans. Inf. Theory 65(6), 3630–3645 (2019).https://doi.org/10.1109/TIT.2019.2901497,https: //doi.org/10.1109/TIT.2019.2901497

    2019 doi

  41. [50]

    good”) with probability at least 9/10, andsreturns a “faulty

    Yoder, T.J., Low, G.H., Chuang, I.L.: Fixed-point quantum search with an optimal number of queries. Physical review letters113(21), 210501 (2014) A Finding the maximum in a register In this section, we prove Theorem 2 from Section 2.5. Theorem 2.[[25,29]] Letsbe an efficient r...

    2014

  42. [51]

    Choosej∈ {0,1} ℓ uniformly at random

  43. [52]

    Apply quantum exponential search [15] over the space{0,1} ℓ to findi∈ {0,1} ℓ such thats(i)> s(j). Letj←i

  44. [53]

    the total running time is less than 22.5 √ 2ℓ + 1.4 log2(2ℓ)

    Go back to Step 2. One should repeat this loop until “the total running time is less than 22.5 √ 2ℓ + 1.4 log2(2ℓ)”, as per [25]. Indeed, after some time, there will not be any new isuch thats(i)> s(j), and the exponential search step will just run forever (before we stop it)....

Pith tools

Reviewed May 20, 2026 · model on record in the stance chip above.