Improved Dual Attack and Trapdoor Sampling via Quantum Rejection Sampling
For post-quantum cryptanalysis, this provides a concrete quantum speedup for lattice-based attacks and signatures, though the improvement is incremental over existing methods.
This work quantumly accelerates the lattice Gaussian sampling bottleneck in dual attacks and GPV trapdoor sampling using quantum rejection sampling, achieving a quadratic reduction in sampling complexity and reducing attack costs by 9, 4, and 13 bits for Kyber-512, Kyber-768, and Kyber-1024, respectively.
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.