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

Carsten Schubert; Jean-Pierre Seifert; Marian Margraf; Maximilian J. Kramer; Niklas Paskarbeit

REVIEW

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

Carsten Schubert, Niklas Paskarbeit, Maximilian J. Kramer, Jean-Pierre Seifert, Marian Margraf

Cryptography and Security · Submitted 23 Sep 2026 · Published version

Pith's verdict: The real content is a finite, certified computation of the Montanaro-vs-Grover exponent for product advice, and the math holds up; the headline 3.97 rests on a disclosed synthetic surrogate, not a measured posterior, but Block A carries the practical claim on genuinely product advice.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 24, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.28226 (version 2)

Pith IDRIFWKAYF, Pith's permanent record of this paper and its review

CitationCarsten Schubert, Jean-Pierre Seifert, Marian Margraf, Maximilian J. Kramer, Niklas Paskarbeit. "Pinpointing Super-Quadratic Quantum Enumeration Speedups: Exact and Certified Evaluation of the Guessing-Moment Exponent under Product-Distribution Advice." arXiv:2609.28226 (2026). https://pith.science/paper/RIFWKAYF

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The genuine contribution is turning the speedup exponent for product advice from something you bound asymptotically into something you compute, with a certificate. The rank-CDF reduction (Lemma 3.1) is clean and correct: likelihood ordering minimizes every moment, and the moments become functionals of the one-dimensional surprisal law. For product advice that collapses to convolutions, the commensurate case yields exact finite sums via tilting, and the a-posteriori binning certificate (Prop 6.9), which needs no local CLT and no saddlepoint hypotheses, is the strongest piece in the paper. Bashiri et al.'s entropy bounds genuinely cannot close the interval on s−2; this framework does.

The mathematics is careful, not performative. The appendices carry real proofs, the exact ratio identity s_eta − s = (e_1 − s e_{1/2})/f_eta(1/2) powers the certificate without asymptotic input, and the authors flag their own floors, including the unspecified polynomial in Lemma 4.4. The disclosure on Block B is explicit: the 3.97 exponent is that of a fitted Bernoulli model, not of the belief-propagation posterior.

Soft spots, in proportion. First, no code ships, so the floating-point claims (floor near 1e−10, root error near 1e−14) are asserted rather than reproducible, and Table 2 never reports the certificate bounds B from Prop 6.9, so a reader cannot see how tight the binned rows actually are. Second, the product-form assumption is genuinely load-bearing in the applications. The stress-test note is right about Keccak: belief propagation exists to create sharp correlated marginals, so dependence is the mechanism there, not a second-order correction, and the AES case adopts sixteen independent per-byte posteriors without validation. The paper concedes both points. But the stress-test overstates the damage: Block A (cold boot) is genuinely product, with exponents above 3.8, so the broad claim that settings exist where Montanaro beats plain Grover survives on Block A alone. The dependence worry does not touch the mathematical core, which is where the value sits.

This deserves a serious referee. It is a genuine advance over [7], and the certificate is a model of honest finite-size evaluation. The referee should push for a code release, for certificate bounds reported beside each exponent, and for the Block C independence assumption to be validated or scaled back. Conditional acceptance with those requests is the right call.

Referee report

Significance

If the results hold, the paper supplies a genuinely useful finite-size tool for evaluating Montanaro-style quantum speedups under product advice, going beyond the asymptotic Rényi-entropy brackets of Bashiri et al. The rank–CDF reduction, the exact finite-sum evaluation for commensurate advice, the certified binning error, and the explicit scaling law are well-constructed and transparently stated. The paper is careful to distinguish the asymptotic scaling law (with its lattice-span and small-error hypotheses) from the a-posteriori certificate, which avoids those hypotheses. The mathematical core appears sound. The main weakness is interpretive: the headline cryptographic applications either rely on the unvalidated product-form assumption (Keccak surrogate, AES template posteriors) or on a fitted synthetic model whose true posterior is known to be correlated, so the reported exponents do not directly quantify the speedup for the actual attacks. No code is shipped, and the floating-point certificate is not rigorous end-to-end in the reference implementation, which tempers the 'exact and certified' claim as advertised.

Major objections (3)

[§7(B), Table 2] The headline exponent 3.97 is computed for a synthetic i.i.d. Bernoulli posterior fitted to a reported Keccak SASCA residual rank, and the paper explicitly states that the true post-propagation marginals are heterogeneous and not exactly independent. Belief propagation exists precisely to create sharp correlated marginals, so dependence is not a second-order perturbation here; without any sensitivity analysis or comparison against a moderately correlated model, the reader cannot infer that a similar exponent holds for the actual attack posterior. The paper should either provide such evidence (e.g., a joint-posterior estimate or a family of correlated surrogates) or relegate the Keccak rows to purely illustrative synthetic examples and base the cryptanalytic conclusion solely on Block A, where the product assumption is exact.
[§6.4, Proposition 6.9 and §4.2] The title and abstract advertise 'exact and certified evaluation,' but the certificate of Proposition 6.9 is valid in exact arithmetic only; the floating-point error bound of Lemma 4.4 contains an unspecified polynomial, and the text concedes that the reference implementation does not provide a rigorous end-to-end numerical enclosure. Consequently, no concrete rigorous bound is attached to the numbers in Table 2. To sustain the 'certified' claim, the authors should either ship the directed-rounding interval-arithmetic route and report the resulting enclosures, or explicitly state in the abstract and conclusions that certification is for the binning error in exact arithmetic, with floating-point errors only controlled to a stated precision in the tested regime.
[§7(C)] The AES template-attack application assumes sixteen independent per-byte posteriors, which is the standard working hypothesis but is not validated against any measured or simulated joint posterior. Since the whole framework collapses to a one-dimensional surprisal convolution only under the product assumption (standing assumption (i)), the reported s values for Block C should be presented as conditional on that unverified independence, and the paper should state explicitly what would change if cross-byte leakage correlations were present. A remark to this effect already exists, but the table and its surrounding texture can easily be read as making a claim about actual template attacks.

Minor objections (5)

[Abstract / §6.4] The phrase 'exact and certified evaluation' in the title and abstract should be qualified: 'exact' refers to the finite-sum identity in the commensurate case, and 'certified' refers to a bound on binning error in exact arithmetic, not to a rigorous end-to-end floating-point enclosure.
[General] No code or reference implementation is provided or linked, despite several mentions of 'the reference implementation.' Readers cannot reproduce the numerical values in Table 2. A repository with the algorithms and the certificate would substantially strengthen the paper.
[§5, Algorithm 2, step 1] The choice of initial bin width η0 is left as 'small enough' relative to per-coordinate gaps, but the paper does not discuss how to detect when the certificate returns an informative bound versus a vacuous one, other than watching the bound's size. A short remark on diagnosing 'vacuous but valid' outputs from the certificate would be useful.
[§2, footnotes] Footnote 5 states that the composition of a binomially sampled observed bit count puts s in [3.77, 4.11] at β=0.01, but the distribution of the composition over the binomial counts is not described; the parenthetical is fine as a remark, but a reader may wonder whether this is a confidence interval or a support range.
[References] The related-work discussion mentions 'Martin et al. 2018' and 'Bashiri et al. 2026' with page numbers that appear plausible but should be checked against the published version, since two entries have linked DOIs with identical Springer pages (e.g., refs [7] and [15]); the bibliographic details should be reconciled.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

This paper makes the quantum/classical guessing-speedup exponent computable for product-form advice: exact on commensurate surprisals, certified otherwise, reaching values above 3 in skewed side-channel models.

The reading

The paper sets out to make the quantum-versus-classical speedup exponent computable rather than merely boundable for the cryptographic guessing problem. When a quantum attacker holds probabilistic advice over candidates, Montanaro's algorithm beats plain Grover, and the advantage is captured by the exponent $s = f(1)/f(1/2)$ with $f(\rho) = \ln E_P[G^\rho]$; $s = 2$ is the Grover-like floor and anything above it is a genuine super-quadratic separation. For advice of product form, the natural model for independent per-coordinate side-channel leakage, the paper shows both guessing moments are functionals of the one-dimensional surprisal law, so $s$ becomes a finite sum in the commensurate case and otherwise comes with a computable a-posteriori error certificate plus a scaling law in the bin width. Applications to cold-boot, template-attack, and Keccak-calibrated settings yield exponents up to 3.974, including cases where the earlier entropy-based bound could not certify $s > 2$.

What carries the argument

The carrying object is the rank–CDF reduction (Lemma 3.1): an optimal guessing order ranks keys by increasing surprisal $S(x) = -\ln P(x)$, and the $\rho$-th guessing moment is $E_P[G^\rho] = \sum_t \pi(t)A_\rho(t)$, where $\pi(t)$ is the level's $P$-mass and $A_\rho(t)$ the mean $\rho$-power of rank inside the level's block of consecutive ranks. For product advice, both $\pi$ and the uniform count CDF are $m$-fold convolutions of per-coordinate laws, collapsing the $m$-dimensional problem to one dimension. Two further devices carry the guarantees: exponential tilting (Lemma 4.2, tilt commutes with convolution), which keeps the $e^{-\Theta(m)}$ saddle magnitudes in closed analytic form so the finite sum survives double precision; and, for the binned route, the lattice-shift sandwich (Lemma 6.1), which bounds the binning error by the log-ratio of the lattice CDF across a widening window of size $m\eta$, reducing the accuracy question to a lattice local CLT (Lemma 6.3).

Extended reading notes

Core claim

The central claim is that the guessing-moment exponent $s$ is computable for product-distribution advice: exactly when all per-coordinate surprisals lie on a common arithmetic grid, and to any target precision above an atom-spacing and floating-point floor otherwise. The route is a rank–CDF reduction: because guessing in likelihood order is guessing in increasing surprisal $S = -\ln P$, both moments $E_P[G^\rho]$ collapse to one-dimensional sums over the level distribution of $S$; because $P$ is a product, that distribution is an $m$-fold convolution of small per-coordinate laws. In the commensurate case the level sum is finite and exact (Theorem 4.1), and exponential tilting, which commutes with convolution, makes it stable in double precision. For general product advice, rounding surprisals to a common grid adds a binning error that the paper bounds two ways: a scaling law $|s_\eta - s| \le \frac{2+s}{\bar{H}_{2/3}}\eta(1+\varepsilon_m)$ together with a run-derived a-posteriori certificate $|s_\eta - s| \le B$ free of asymptotic assumptions (Proposition 6.9), so a reported exponent carries its own non-asymptotic error bound.

Load-bearing premise

The whole method rests on the advice being a product, $P(x) = \prod_i p_i(x_i)$; if the true posterior has genuine coordinate dependence, as a belief-propagation posterior on a cyclic factor graph may, the one-dimensional surprisal collapse fails and the computed exponent no longer expresses the true guessing moments.

Editorial extensions

If this is right

For any product advice the speedup exponent can be pinned to any target precision above the atom-spacing and floating-point floors, turning the asymptotic 'there is a super-quadratic speedup' question into a concrete per-scheme number.
In skewed-advice settings the computed exponents exceed 3, reaching 3.974 in a synthetic Bernoulli model calibrated to a reported Keccak residual rank, and in five table rows the previous entropy-based bound fails to certify $s > 2$ while the new method does.
The shape of the advice, more than the strength of the leakage, decides the advantage: smooth 256-ary template-attack posteriors give $s \approx 2$ even at sharp residual, while heavy-tailed skewed advice gives large $s$.
Each binned run returns a certificate assembled from its own arrays, valid under the engine assumptions alone with no local-CLT, lattice-span, or regime hypotheses, so the certificate degrades visibly rather than silently where the scaling law fails.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The method's reach is bounded by the product-form assumption: real belief-propagation or template posteriors with cycle-induced dependence are fitted to product surrogates, and the unvalidated independence step means reported exponents describe the surrogate model, not the true posterior.
The exponent $s$ discards Montanaro's constant and additive overhead, so the operational query-count advantage can differ by a constant even where $s$ is large; the paper isolates the information-theoretic ratio, and translating it to real query counts needs the dropped overheads.
The rank–CDF reduction is not crypto-specific: any product-distribution guessing problem, such as password cracking or sequential decoding, could inherit the same exact-or-certified evaluation of its enumeration cost.
Because the certificate route is free of asymptotic hypotheses, it doubles as a validation harness: run on exhaustively enumerable small-$m$ instances, as the paper does, to map where the scaling law's computed conditions actually hold.

Original 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 average 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 3.92 for cold-boot advice and 3.12 in the synthetic models, and include cases where the previous entropy-based bound did not establish an exponent above 2.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-24: 1 request, 8,445 input tokens.

What the abstract itself states, as probabilities: claims first 0.44 · states limitation 0.57 · human participants 0.04 · controlled comparison 0.46 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.97 · mentions code or data availability 0.03.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Grover's algorithm gives an optimal quadratic query advantage for black-box search.	background 1.00	0.03	0.02	asserted 1.00
s1	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.	background 1.00	0.05	0.02	asserted 0.77
s2	Classically, guessing in likelihood order is optimal in expectation.	background 1.00	0.04	0.02	asserted 1.00
s3	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).	background 1.00	0.04	0.05	asserted 1.00
s4	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.	gap 1.00	0.06	0.05	asserted 0.99
s5	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.	contribution 0.79	0.96	0.37	asserted 1.00
s6	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.	method 0.98	0.84	0.09	asserted 1.00
s7	For general product advice, we discretize the surprisals onto a common grid and derive an a-posteriori bound on the resulting binning error.	method 0.97	0.95	0.05	asserted 1.00
s8	We apply the framework to cold-boot leakage on seeds and block-cipher keys, to template-attack posteriors, and to synthetic i.i.d.	contribution 0.74	0.90	0.05	asserted 0.98
s9	Bernoulli posteriors calibrated to residual ranks reported for Keccak side-channel attacks on ML-KEM and ML-DSA.	method 0.55	0.75	0.04	unclear 0.68
s10	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.	result 1.00	0.94	0.63	asserted 1.00

What kind of paper the classifier reports this is: method or tool 1.00 · evidence from proof or derivation 0.67.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.