Metraipolis › archive › dc_bdb60fa2b015

Pinpointing Super-Quadratic Quantum Enumeration Speedups: Exact and Certified Evaluation of the Guessing-Moment Exponent under Product-Distribution Advice — arXiv:2609.28226

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.28226
License (as archived): CC0-1.0
Archived: 2026-10-08T10:13:28.748Z
SHA-256 of the archived text: 229c77260b5873953618dac3dcae71729f75916829b65271134e8e388a604a20
Stable URL of this page: https://metraipolis.com/documento/dc_bdb60fa2b015

How to cite

Pinpointing Super-Quadratic Quantum Enumeration Speedups: Exact and Certified Evaluation of the Guessing-Moment Exponent under Product-Distribution Advice — arXiv:2609.28226 — arXiv (en), https://arxiv.org/abs/2609.28226 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bdb60fa2b015 (Metraipolis archive dc_bdb60fa2b015, sha256 229c77260b5873953618dac3dcae71729f75916829b65271134e8e388a604a20)

BibTeX

@misc{dcbdb60fa2b015,
  title = {Pinpointing Super-Quadratic Quantum Enumeration Speedups: Exact and Certified Evaluation of the Guessing-Moment Exponent under Product-Distribution Advice — arXiv:2609.28226},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.28226},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bdb60fa2b015; sha256 229c77260b5873953618dac3dcae71729f75916829b65271134e8e388a604a20},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.28226. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-24 in cs.CR).
Categorie arXiv: Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2609.28226 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T09:26:35.725Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-24?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).