Pinpointing Super-Quadratic Quantum Enumeration Speedups: Exact and Certified Evaluation of the Guessing-Moment Exponent under Product-Distribution Advice
Researchers give an exact method to measure super-quadratic quantum speedups from product side-channel advice.
The paper provides a finite-size method for measuring the quantum-versus-classical guessing-moment gap when cryptanalytic search has product-form probabilistic advice, such as side-channel leakage on independent key coordinates. Classical and quantum moments reduce to functionals of a one-dimensional surprisal distribution; commensurate surprisals give exact finite sums, and general cases receive a certified binning-error bound. Applied to cold-boot leakage, template-attack posteriors, and synthetic Bernoulli posteriors calibrated to Keccak side-channel residual ranks for ML-KEM and ML-DSA, exponents reached up to 3.97, above Grover's quadratic factor.
- Gives a finite-size method for quantum-classical guessing-moment separation.
- Commensurate surprisals yield exact finite sums without discretization error.
- General product advice receives a certified binning-error bound.
- Synthetic models reach a speedup exponent of up to 3.97.
- Cases include cold-boot leakage and ML-KEM and ML-DSA side channels.
Full article264 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.28226