pith. sign in

arxiv: 2605.24798 · v1 · pith:7GAJIW2Tnew · submitted 2026-05-24 · 🪐 quant-ph · cs.DS

Improved Dual Attack and Trapdoor Sampling via Quantum Rejection Sampling

Cong Ling , Hao Yan , Nicholas Zhao This is my paper

Pith reviewed 2026-06-30 01:24 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS
keywords quantum rejection samplingdual attacklattice Gaussian samplingKyberGPV trapdoor samplingKlein's algorithmpost-quantum cryptographyquantum algorithms
0
0 comments X

The pith

Quantum rejection sampling quadratically accelerates lattice Gaussian sampling for dual attacks, cutting estimated costs on Kyber parameters by 9, 4, and 13 bits.

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

The paper focuses on the lattice Gaussian sampling step that often dominates the cost of dual attacks against schemes like Kyber. It combines the lower bound from Wang and Ling's analysis of Klein's algorithm with the quantum rejection sampling framework to obtain a quantum procedure that prepares the required truncated dual q-ary lattice Gaussian distribution. Because the lower bound supplies the exact pointwise domination condition needed for rejection sampling under coherent oracle access, the procedure achieves a quadratic reduction in sampling complexity while keeping total variation distance to the full Gaussian negligible. Substituting the new sampler into the dual attack framework produces lower overall attack-cost estimates than those obtained from Pouly and Shen's modern classical attack under identical parameters. The same replacement also yields a quadratic speedup when applied to the GPV trapdoor sampling used in signature generation.

Core claim

The authors show that the domination condition supplied by the lower bound on Klein's algorithm is precisely what quantum rejection sampling requires when given coherent access to a truncated Klein proposal; this yields a quantum algorithm for the truncated dual q-ary lattice Gaussian whose query complexity is quadratically smaller than the classical sampler, with the truncation radius chosen so the output remains negligibly close in total variation distance to the ideal lattice Gaussian.

What carries the argument

Quantum rejection sampling applied to a truncated Klein proposal distribution under coherent oracle access, using the pointwise domination condition from Wang and Ling's analysis of Klein's algorithm.

If this is right

  • Attack cost estimates drop by 9 bits for Kyber-512, 4 bits for Kyber-768, and 13 bits for Kyber-1024 relative to Pouly and Shen's attack under the same parameters.
  • Corresponding cost reductions hold when modulus switching is also applied.
  • Replacing the MCMC sampler with the QRS algorithm produces a quadratic speedup in the GPV signing procedure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same domination-plus-rejection technique could be tested on other classical samplers whose analysis already supplies a suitable lower bound.
  • If the quadratic saving persists across a wider range of lattice dimensions, security estimates for other module-lattice and ideal-lattice schemes would require similar downward adjustment.
  • Implementation of the coherent oracle access model on near-term quantum hardware would provide a direct test of whether the predicted sampling speedup materializes in practice.

Load-bearing premise

The lower bound from Wang and Ling's analysis of Klein's algorithm supplies exactly the pointwise domination condition that quantum rejection sampling needs for the truncated proposal distribution.

What would settle it

An explicit computation or numerical check showing that, for the chosen truncation radius, the total variation distance between the truncated and full lattice Gaussian exceeds a negligible bound, or that the domination inequality fails to hold pointwise for the Klein proposal.

Figures

Figures reproduced from arXiv: 2605.24798 by Cong Ling, Hao Yan, Nicholas Zhao.

Figure 1
Figure 1. Figure 1: Discrete Gaussian mass on Z 2 ∩ [−15, 15]2 with Gaussian parameter s = 10 (left) and s = 4 (right). The plotted values show the unnormalized mass underlying DZ2,s,0(x) = ρs,0(x)/ρs,0(Z 2 ). Corollary 1 ([24]). Let L ⊂ R m be a lattice, let c ∈ R m, let s > 0 and let εtail ∈ (0, 1). If R ≥ s r m 2π + r log(1/εtail) π ! , (10) then ρs ((L − c) \ Bm(R)) ≤ εtailρs(L). (11) Here Bm(R) denotes the radius-R Eucli… view at source ↗
Figure 2
Figure 2. Figure 2: Oracle-level decomposition of our quantum sampler. The top wire is the [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: MCMC and QRS upper bounds derived from [29]’s [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗
read the original abstract

In this work, we revisit the dual attack and GPV trapdoor sampling, focusing on the lattice Gaussian sampling term, which can be a significant bottleneck in the overall complexity. We show that this sampling step can be quantumly accelerated by combining the lower bound underlying Wang and Ling's analysis of Klein's algorithm with the quantum rejection sampling (QRS) framework proposed by Ozols et al. Specifically, this lower bound gives precisely the pointwise domination condition required for quantum rejection sampling when given coherent oracle access to a truncated Klein proposal distribution, which yields a quantum procedure for preparing the truncated dual $q$-ary lattice Gaussian with a quadratic reduction in the sampling complexity. The truncation radius is chosen so that the truncated distribution is negligibly close to the full lattice Gaussian in total variation distance. Substituting this sampler into the dual attack framework results in reduced overall attack-cost estimates. Compared with Pouly and Shen's modern dual attack under the same parameter choices, our estimates reduce the attack cost by \(9\), \(4\), and \(13\) bits for Kyber-512, Kyber-768, and Kyber-1024, respectively. We also report the corresponding estimates with modulus switching. Finally, by replacing the Markov chain Monte Carlo (MCMC) sampler with the QRS algorithm, we achieve a similar quadratic speedup in the GPV signing process.

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 / 1 minor

Summary. The paper claims that the lower bound underlying Wang and Ling's analysis of Klein's algorithm supplies exactly the pointwise domination function needed to apply Ozols et al.'s quantum rejection sampling to a coherent oracle for the truncated Klein proposal distribution. This is asserted to yield a quadratic reduction in the query complexity of preparing truncated dual q-ary lattice Gaussians (with truncation radius chosen for negligible total-variation distance to the target). Substituting the resulting sampler into the dual-attack framework produces concrete attack-cost reductions of 9, 4, and 13 bits versus Pouly-Shen for Kyber-512/768/1024 (with and without modulus switching); an analogous quadratic speedup is claimed for GPV signing by replacing the MCMC sampler.

Significance. If the claimed exact pointwise domination holds under coherent access and truncation, the work would supply a concrete quantum improvement to a core primitive in lattice-based cryptanalysis and signature generation, directly lowering bit-security estimates for standardized Kyber parameters and thereby affecting concrete security assessments in post-quantum cryptography.

major comments (2)
  1. [Abstract] Abstract and the section describing the QRS application: the central claim that the Wang-Ling lower bound 'gives precisely the pointwise domination condition' for the truncated Klein proposal is stated without exhibiting the explicit domination function f or deriving that q(x) ≤ f(x)·target(x) holds pointwise inside the truncation support when the oracle is coherent. This equivalence is load-bearing for the quadratic query reduction and the reported 9/4/13-bit savings; an average-case or asymptotic bound would not suffice.
  2. [Section on truncation and TV distance] The paragraph on truncation radius and total-variation closeness: no explicit error analysis or verification is supplied showing that the chosen radius preserves the domination inequality inside the support while keeping TV distance negligible; coherent-access normalization or phase issues are not addressed.
minor comments (1)
  1. Notation for the truncated proposal distribution and the coherent oracle could be introduced earlier and used consistently when invoking the Ozols QRS theorem.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments, which highlight areas where the presentation of our central claims can be strengthened. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract and the section describing the QRS application: the central claim that the Wang-Ling lower bound 'gives precisely the pointwise domination condition' for the truncated Klein proposal is stated without exhibiting the explicit domination function f or deriving that q(x) ≤ f(x)·target(x) holds pointwise inside the truncation support when the oracle is coherent. This equivalence is load-bearing for the quadratic query reduction and the reported 9/4/13-bit savings; an average-case or asymptotic bound would not suffice.

    Authors: We agree that the manuscript states the equivalence without an explicit pointwise derivation of the domination function or verification of q(x) ≤ f(x)·target(x) for the coherent truncated proposal. In the revised version we will add a dedicated subsection that extracts the explicit domination function f from the Wang-Ling lower bound and proves the required pointwise inequality holds inside the truncation support under coherent oracle access. This will make the application of Ozols et al.'s framework fully rigorous and self-contained. revision: yes

  2. Referee: [Section on truncation and TV distance] The paragraph on truncation radius and total-variation closeness: no explicit error analysis or verification is supplied showing that the chosen radius preserves the domination inequality inside the support while keeping TV distance negligible; coherent-access normalization or phase issues are not addressed.

    Authors: The current manuscript selects the truncation radius to achieve negligible total-variation distance but does not supply a detailed error analysis confirming that the domination inequality survives truncation, nor does it discuss coherent-access normalization or phase considerations. We will insert an explicit analysis in the revision that (i) bounds the truncation error while preserving the pointwise domination, (ii) quantifies the resulting TV distance, and (iii) explains how the coherent oracle is normalized and how phase factors are handled within the QRS procedure. revision: yes

Circularity Check

0 steps flagged

Central speedup combines externally published results; no reduction to internal fit or self-definition

full rationale

The paper's derivation chain rests on citing the Wang-Ling lower bound for Klein's algorithm and the Ozols QRS framework, then observing that the former supplies the exact pointwise domination needed for the latter under coherent truncated-Klein access. This observation is presented as the key step enabling quadratic query reduction and the reported 9/4/13-bit savings. No equation in the provided text defines a quantity in terms of itself, renames a fitted parameter as a prediction, or imports a uniqueness result from the authors' own prior work to force the choice. The truncation radius is chosen for TV-negligibility (an external criterion), and the final attack-cost estimates are computed from the combined sampler rather than being forced by parameters fitted inside this manuscript. The shared author (Ling) on the cited Wang-Ling work constitutes a minor self-citation but is not load-bearing in the sense that the central claim reduces to an unverified self-reference; the cited bound is treated as an independent mathematical fact. The derivation therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the applicability of the Wang-Ling lower bound to the QRS domination condition and on the total-variation closeness of the truncated distribution; no new free parameters or invented entities are introduced.

axioms (2)
  • domain assumption Wang and Ling's lower bound on Klein's algorithm supplies the pointwise domination condition for QRS
    Invoked to justify the quadratic query reduction
  • domain assumption Truncated Klein distribution is negligibly close to the full lattice Gaussian in total variation distance
    Required to substitute the sampler into the dual attack without changing the attack's correctness

pith-pipeline@v0.9.1-grok · 5767 in / 1398 out tokens · 29207 ms · 2026-06-30T01:24:58.407976+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

32 extracted references · 17 canonical work pages

  1. [1]

    In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing

    Aharonov, D., Ta-Shma, A.: Adiabatic quantum state generation and statistical zero knowledge. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing. pp. 20–29. Association for Computing Machinery (2003). https://doi.org/10.1145/780542.780546 22

    work page doi:10.1145/780542.780546 2003

  2. [2]

    In: Coron, J.S., Nielsen, J.B

    Albrecht, M.R.: On dual lattice attacks against small-secret LWE and param- eter choices in HElib and SEAL. In: Coron, J.S., Nielsen, J.B. (eds.) Ad- vances in Cryptology – EUROCRYPT 2017, Part II. Lecture Notes in Computer Science, vol. 10211, pp. 103–129. Springer (2017).https://doi.org/10.1007/ 978-3-319-56614-6_4

    2017

  3. [3]

    Cryptology ePrint Archive, Paper 2022/656 (2022).https://doi.org/10.48550/ARXIV.2205.13983, https://eprint.iacr.org/2022/656

    Albrecht, M.R., Shen, Y.: Quantum augmented dual attack. Cryptology ePrint Archive, Paper 2022/656 (2022).https://doi.org/10.48550/ARXIV.2205.13983, https://eprint.iacr.org/2022/656

    work page doi:10.48550/arxiv.2205.13983 2022

  4. [4]

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

    In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC ’13)

    Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC ’13). pp. 575–584. ACM (2013).https://doi.org/ 10.1145/2488608.2488680

    work page doi:10.1145/2488608.2488680 2013

  6. [6]

    In: Advances in Cryptology – CRYPTO

    Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from Ring-LWE and security for key dependent messages. In: Advances in Cryptology – CRYPTO

  7. [7]

    6841, pp

    Lecture Notes in Computer Science, vol. 6841, pp. 505–524. Springer (2011).https://doi.org/10.1007/978-3-642-22792-9_29,https://www.iacr. org/archive/crypto2011/68410501/68410501.pdf

    work page doi:10.1007/978-3-642-22792-9_29 2011

  8. [8]

    Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification andestimation.ContemporaryMathematics305,53–74(2002).https://doi.org/ 10.1090/conm/305/05215

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

  9. [9]

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

    Chevignard, C., Schrottenloher, A., Shen, Y.: Quantum algorithm for Discrete Gaussian Sampling. Cryptology ePrint Archive, Paper 2026/984 (2026),https: //eprint.iacr.org/2026/984

    2026

  10. [10]

    Lecture Notes in Com- puter Science, vol

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

    2023

  11. [11]

    Fouque, P.A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Prest, T., Ricosset, T., Seiler, G., Whyte, W., Zhang, Z.: Falcon: Fast-Fourier lattice-based compact signatures over NTRU. Specification v1.2, National Institute of Standards and Technology (Jan 2020),https://falcon-sign.info/falcon.pdf, submission to the NIST Post-Quantum Cryptogra...

    2020

  12. [12]

    In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC)

    Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC). pp. 197–206. ACM (2008).https://doi.org/ 10.1145/1374376.1374407

    work page doi:10.1145/1374376.1374407 2008

  13. [13]

    In: Tibouchi, M., Wang, H

    Guo, Q., Johansson, T.: Faster dual lattice attacks for solving LWE with applica- tions to CRYSTALS. In: Tibouchi, M., Wang, H. (eds.) Advances in Cryptology – ASIACRYPT 2021, Part IV. 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 doi:10.1007/978-3-030-92068-5_2 2021

  14. [14]

    In: Pro- ceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

    Klein, P.N.: Finding the closest lattice vector when it’s unusually close. In: Pro- ceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 937–941. Society for Industrial and Applied Mathematics (2000)

    2000

  15. [15]

    SIAM Journal on Computing40(1), 142–164 (2011).https://doi.org/10.1137/ 090745854 23

    Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. SIAM Journal on Computing40(1), 142–164 (2011).https://doi.org/10.1137/ 090745854 23

    2011

  16. [16]

    MATZOV: Report on the security of LWE: Improved dual lattice attack. Tech. rep., Zenodo (April 2022).https://doi.org/10.5281/zenodo.6493704,https:// doi.org/10.5281/zenodo.6493704

    work page doi:10.5281/zenodo.6493704 2022

  17. [17]

    SIAM Journal on Computing37(1), 267–302 (2007).https://doi.org/ 10.1137/S0097539705447360

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

    work page doi:10.1137/s0097539705447360 2007

  18. [18]

    National Institute of Standards and Technology: Module-Lattice-Based Key- Encapsulation Mechanism Standard. Federal Information Processing Standards Publication 203, National Institute of Standards and Technology (2024).https: //doi.org/10.6028/NIST.FIPS.203,https://doi.org/10.6028/NIST.FIPS.203

    work page doi:10.6028/nist.fips.203 2024

  19. [19]

    In: Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, vol

    von Neumann, J.: Various techniques used in connection with random digits. In: Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, vol. 12, pp. 36–38. U.S. Government Printing Office, Washington, DC (1951), notes by G. E. Forsythe

    1951

  20. [20]

    ACM Trans- actions on Computation Theory5(3), 11:1–11:33 (2013).https://doi.org/10

    Ozols, M., Roetteler, M., Roland, J.: Quantum rejection sampling. ACM Trans- actions on Computation Theory5(3), 11:1–11:33 (2013).https://doi.org/10. 1145/2493252.2493256

    arXiv 2013

  21. [21]

    In: Advances in Cryptology – EUROCRYPT 2024

    Pouly, A., Shen, Y.: Provable dual attacks on learning with errors. In: Advances in Cryptology – EUROCRYPT 2024. Lecture Notes in Computer Science, vol. 14657, 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

  22. [22]

    In: Advances in Cryptology – ASIACRYPT 2025

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

    2025

  23. [23]

    Journal of the ACM56(6), 34:1–34:40 (2009).https://doi.org/10.1145/ 1568318.1568324

    Regev, O.: On lattices, learning with errors, random linear codes, and cryptogra- phy. Journal of the ACM56(6), 34:1–34:40 (2009).https://doi.org/10.1145/ 1568318.1568324

    arXiv 2009

  24. [24]

    Theoretical Computer Science53(2–3), 201–224 (1987).https://doi.org/10

    Schnorr, C.P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science53(2–3), 201–224 (1987).https://doi.org/10. 1016/0304-3975(87)90064-8

    1987

  25. [25]

    Stephens-Davidowitz, N.: On the Gaussian Measure Over Lattices. Ph.D. the- sis, New York University (2017),https://cs.nyu.edu/media/publications/ stephens-davidowitz_noah.pdf

    2017

  26. [26]

    In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science

    Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. pp. 32–41. IEEE Computer Society (2004).https://doi.org/10.1109/FOCS.2004.53

    work page doi:10.1109/focs.2004.53 2004

  27. [27]

    Nature471(7336), 87–90 (2011).https://doi.org/10

    Temme, K., Osborne, T.J., Vollbrecht, K.G.H., Poulin, D., Verstraete, F.: Quan- tum Metropolis sampling. Nature471(7336), 87–90 (2011).https://doi.org/10. 1038/nature09770

    2011

  28. [28]

    In: 2015 IEEE International Symposium on Information The- ory (ISIT)

    Wang, Z., Ling, C.: Independent Metropolis–Hastings–Klein algorithm for lattice Gaussian sampling. In: 2015 IEEE International Symposium on Information The- ory (ISIT). pp. 2470–2474. IEEE (2015).https://doi.org/10.1109/ISIT.2015. 7282900

    work page doi:10.1109/isit.2015 2015

  29. [29]

    IEEE Transactions on Information Theory64(2), 738–751 (2018).https://doi.org/10.1109/TIT.2017.2742509

    Wang, Z., Ling, C.: On the geometric ergodicity of Metropolis–Hastings algorithms for lattice Gaussian sampling. IEEE Transactions on Information Theory64(2), 738–751 (2018).https://doi.org/10.1109/TIT.2017.2742509

    work page doi:10.1109/tit.2017.2742509 2018

  30. [30]

    IEEE Transactions on Infor- mation Theory65(6), 3630–3645 (2019).https://doi.org/10.1109/TIT.2019

    Wang, Z., Ling, C.: Lattice Gaussian sampling by Markov chain Monte Carlo: Bounded distance decoding and trapdoor sampling. IEEE Transactions on Infor- mation Theory65(6), 3630–3645 (2019).https://doi.org/10.1109/TIT.2019. 2901497 24

    work page doi:10.1109/tit.2019 2019

  31. [31]

    Physical Review A 78(4), 042336 (2008).https://doi.org/10.1103/PhysRevA.78.042336

    Wocjan, P., Abeyesinghe, A.: Speedup via quantum sampling. Physical Review A 78(4), 042336 (2008).https://doi.org/10.1103/PhysRevA.78.042336

    work page doi:10.1103/physreva.78.042336 2008

  32. [32]

    Physical Review Letters113(21), 210501 (2014).https://doi

    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).https://doi. org/10.1103/PhysRevLett.113.210501 25

    work page doi:10.1103/physrevlett.113.210501 2014