Quantum search speedups exceed quadratic limit with probabilistic advice
Pinpointing Super-Quadratic Quantum Enumeration Speedups: Exact and Certified Evaluation of the Guessing-Moment Exponent under Product-Distribution Advice
Cryptography and Security
Summary
Searching for a specific item in a large set usually takes time proportional to the square root of the set size using quantum techniques like Grover's algorithm. However, when additional hints about the likely location are available, the authors show that quantum search can be even faster, beating this quadratic speedup. They provide a precise way to measure and calculate these improvements for complex, realistic advice scenarios often seen in cryptanalysis. Their results reveal cases where the speedup can approach nearly four times better than classical guessing methods.
What this means in practice
- •For cryptography engineers: Optimize quantum attacks on cryptographic keys using probabilistic side-channel leakage models for faster key recovery.
- •For security analysts: Evaluate realistic quantum speedups in cryptanalysis by precisely quantifying the advantage gained from product-form advice distributions.
Authors
Carsten Schubert, Niklas Paskarbeit, Maximilian J. Kramer, Jean-Pierre Seifert, Marian Margraf
Abstract
Grover's algorithm gives an optimal quadratic query advantage for black-box search. In cryptanalysis, however, the search often comes with additional probabilistic advice over the candidates, frequently of product form, e.g. from side-channel leakage on independent key coordinates. Classically, guessing in likelihood order is optimal in expectation. In the quantum setting, Montanaro showed how to achieve an optimal expected query complexity, beating plain Grover on every non-uniform advice distribution (up to a constant overhead factor). What has been missing so far is a finite-size method for evaluating the quantum-classical guessing-moment separation induced by a given advice distribution. We provide such a method for product-distribution advice, thereby sharpening the previous entropy-based estimate of Bashiri et al. We reduce the classical and quantum guessing moments to functionals of the one-dimensional surprisal distribution, obtained for product advice by convolving the per-coordinate surprisal laws. When the surprisals lie on a common arithmetic grid (the commensurate case), the logarithmic moments and hence the speedup exponent can be evaluated as finite sums without discretization error; exponential tilting makes this computation numerically stable. For general product advice, we discretize the surprisals onto a common grid and derive an a-posteriori bound on the resulting binning error. We apply the framework to cold-boot leakage on seeds and block-cipher keys, to template-attack posteriors, and to synthetic i.i.d. Bernoulli posteriors calibrated to residual ranks reported for Keccak side-channel attacks on ML-KEM and ML-DSA. The resulting exponents substantially exceed 2 in several skewed-advice settings, reaching up to 3.97 in these synthetic models, and include cases where the previous entropy-based bound did not establish an exponent above 2.