pith. sign in

arxiv: 2605.20133 · v1 · pith:IABNC3CRnew · submitted 2026-05-19 · 🪐 quant-ph

Quantum algorithm for Discrete Gaussian Sampling

Cl\'emence Chevignard , Yixin Shen , Andr\'e Schrottenloher This is my paper

Pith reviewed 2026-05-20 05:11 UTC · model grok-4.3

classification 🪐 quant-ph
keywords discrete gaussian samplingquantum algorithmlattice-based cryptographyrejection samplingquantum dual attacksshort integer solutionquantum cryptanalysis
0
0 comments X

The pith

A quantum rejection sampling algorithm produces discrete Gaussian samples on lattices with asymptotic quadratic speedup over the best classical method.

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

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.

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.

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].

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

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

axioms (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.

pith-pipeline@v0.9.0 · 5738 in / 1150 out tokens · 35175 ms · 2026-05-20T05:11:28.736482+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

52 extracted references · 52 canonical work pages · 1 internal anchor

  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]

    In: STOC

    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]

    In: STOC

    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

  9. [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

    work page doi:10.1007/978-3-030-03326-2_14 2018

  10. [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

    work page 2022

  11. [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

    work page 2025

  12. [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

    work page 2026

  13. [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

    work page doi:10.1007/978-3-031-30589-4_8 2023

  14. [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

    work page doi:10.1109/eurosp.2018.00032 2018

  15. [15]

    Fortschritte der Physik 46(4-5), 493–505 (1998)

    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

    work page doi:10.1002/(sici)1521-3978(199806)46:4/5 1998

  16. [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

    work page doi:10.1145/2488608.2488680 2013

  17. [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

    work page doi:10.1090/conm/305/05215 2002

  18. [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

    work page doi:10.1007/978-3-032-01855-7_15 2025

  19. [19]

    IACR Cryptol

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

    work page 2022

  20. [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

    work page doi:10.1007/978-3-030-92068-5_3 2021

  21. [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

    work page 2024

  22. [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

    work page 2017

  23. [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://doi.org/10.13154/tches.v2018.i1. 238-268

    work page doi:10.13154/tches.v2018.i1 2018

  24. [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

    work page doi:10.1007/978-3-031-38548-3_2 2023

  25. [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

    work page arXiv 1996

  26. [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. Springer (2020).https://doi.org/10. 1007/978-3-030-65277-7_20

    work page 2020

  27. [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

    work page doi:10.1145/1374376.1374407 2008

  28. [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

    work page 2021

  29. [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

    work page doi:10.1007/3-540-45061-0_25 2003

  30. [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)

    work page 1986

  31. [31]

    Wavefunction preparation and resampling using a quantum computer

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

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  32. [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

    work page 2000

  33. [33]

    Addison-Wesley, 4 edn

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

    work page 2011

  34. [34]

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

    work page 2015

  35. [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

    work page 2013

  36. [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

    work page doi:10.5281/zenodo.6412487 2022

  37. [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

    work page doi:10.1137/s0097539705447360 2007

  38. [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

    work page doi:10.1098/rspa.2015.0301 2015

  39. [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)

    work page 2011

  40. [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

    work page doi:10.1145/2493252 2013

  41. [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

    work page doi:10.1007/978-3-031-58754-2_10 2024

  42. [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

    work page doi:10.1007/978-3-031-86602-9_3 2025

  43. [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)

    work page 2020

  44. [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

    work page doi:10.1007/978-981-95-5099-9_2 2025

  45. [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

    work page doi:10.1145/1568318.1568324 2009

  46. [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

    work page 2017

  47. [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

    work page doi:10.1103/sanders2019black 2019

  48. [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

    work page doi:10.1109/tit.2019.2901497 2019

  49. [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 randomized algorithm that, on input i∈ {0,1} ℓ, returnss(i), wheres(i)equals a va...

    work page 2014

  50. [51]

    Choosej∈ {0,1} ℓ uniformly at random

    work page

  51. [52]

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

    work page

  52. [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). Theorem 12 ([25, Theorem 1, Lemma 2]).Consider a functionswith quantum oracle a...

    work page