PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2609.28226v1cs.CR

TL;DR

Finite-size evaluation of the quantum–classical guessing-moment separation for product advice has been missing. This paper reduces the moments to one-dimensional surprisal laws and computes the exponent exactly or with a certified binning error; its applications include skewed-advice models with exponents up to 3.97.

  • Problem

    A finite-size method for evaluating the guessing-moment exponent of a given advice distribution was missing, while entropy-based bounds can leave its surplus over 2 unresolved.

    Source: §1 · p. 2

  • Method

    The method reduces guessing moments to functionals of the one-dimensional surprisal law, computing commensurate product advice exactly and other product advice by binning with an a-posteriori error bound.

    Source: §1 · p. 2

  • Results

    The exponent reaches 3.97 in the synthetic model calibrated to the reported ML-DSA residual rank, and exceeds 2 across the practical cold-boot range.

    Source: §7 · p. 12

  • Takeaways & Limitations

    The framework yields a per-scheme guessing-moment exponent with bounded discretization error, including finite-parameter settings where the entropy-based estimate remains loose.

    Source: §8 · pp. 12–13

    If the bin width is coarser than the per-coordinate gaps, binning collapses distinct levels and the certificate can become vacuous.

    Source: §5 · p. 7

Abstract

from arXiv · show

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.

1 Introduction

The introduction identifies a gap in evaluating the finite-size quantum–classical guessing-moment exponent for product advice. It presents a method based on the surprisal distribution, exact on a common arithmetic grid and certified after binning otherwise.

Background

  • Montanaro’s advice search traverses candidates in geometrically growing segments, allowing likely keys to be found in early segments rather than searching the full space at once.The method runs Grover search on each segment.Source: §1 · p. 2

Motivation

  • The exponent s measures the finite-size separation through the classical and quantum guessing moments, while existing entropy bounds may fail to certify s > 2 at finite parameters.The introduction notes that the unresolved interval in the earlier bound can hide a substantial part of the surplus s−2.Source: §1 · p. 2

Approach

  • Product advice makes a key’s surprisal a sum of independent coordinate contributions, reducing the guessing-moment computation to a one-dimensional law.The method uses exponential tilting to keep the exact and general computations numerically stable.Source: §1 · p. 2
  • For commensurate surprisals, the exponent can be computed by finite sums without discretization error; arbitrary product advice is handled by grid binning with an a-posteriori error bound.Under the stated scaling-law hypotheses, the binning error decreases in proportion to the grid spacing.Source: §1 · p. 2

2 Setup and the speedup exponent

The setup models advice as a product distribution and ranks keys by likelihood, equivalently by increasing surprisal. It defines the speedup exponent from the logarithms of the classical and quantum guessing moments.

Model

  • The advice distribution is a product across key coordinates, so the key surprisal is the sum of coordinate surprisals; genuinely dependent coordinates are outside the stated model.The text notes that grouping positions into coarser coordinates can sometimes fit richer models into the product form.Source: §2 · p. 3

Guessing order

  • Guessing in increasing surprisal minimizes every positive guessing moment, and ties do not change the moment values.The optimal order is likelihood order; keys sharing a surprisal level occupy a consecutive rank block.Source: §2 · p. 3

Cost model and exponent

  • The classical query complexity equals E_P[G], while Montanaro’s quantum complexity is governed up to constant factors by the square-root guessing moment, with an additive overhead.The information-theoretic exponent is s = f(1)/f(1/2), where f(ρ) = ln E_P[G^ρ].Source: §2 · p. 3
  • Jensen’s inequality gives s ≥ 2, and under uniform advice the exponent approaches 2 as the key space grows.The nondegeneracy assumption used for saddle-point analysis excludes uniform advice, which can instead be evaluated directly.Source: §2 · p. 3

3 The rank–CDF reduction

The rank–CDF reduction replaces an exponentially large key space with two one-dimensional surprisal distributions. Their distributions under uniform counting and under the advice determine the guessing moments, including when surprisal levels contain ties.

Reduction

  • Because product advice makes surprisal additive, the distributions needed for the moments are m-fold convolutions of small per-coordinate laws.One law describes how many keys occur at each surprisal level, and the other describes the probability that the secret occurs there.Source: §3 · pp. 3–4

Rank and surprisal levels

  • Under uniform counting, N·F_S(t) counts keys at least as likely as a key with surprisal t, and the ranks at that level form a consecutive interval.The interval contains exactly the keys whose surprisal equals t.Source: §3 · p. 4

Moment computation

  • The advice probability of a surprisal level is π(t) = n(t)e^−t, and averaging rank powers across each level makes the guessing moments independent of tie-breaking.The reduction’s identity is the basis for the later exact computation or binned approximation with an a-posteriori error bound.Source: §3 · p. 4

4 Exact evaluation and the stable engine

The section develops exact finite evaluation for commensurate advice and a numerically stable implementation, then extends the exact route to bounded-rank surprisal levels. The stable engine uses exponential tilting and log-domain recovery to handle exponentially small quantities.

4.1 The exact evaluation

  • For commensurate advice, the exponent is computed as an exact finite sum in Õ(R/h + B_in) time, or Õ(m/h) for extensive range R = O(m).The sum runs over grid levels, and each level's contribution is evaluated from adjacent surprisal CDF values.Source: §4.1 · p. 4
  • Bounded-rank marginals extend the exact engine beyond commensurate advice by keeping the number of surprisal levels polynomial in m.The levels correspond to integer vectors; for extensive spreads, there are O(m^d) levels, which are sorted by their induced surprisal order before cumulation.Source: §4.1 · p. 5
  • When finite-rank levels cannot be separated at working precision, merging them yields a certified enclosure rather than an exact value.The required adaptive-precision sorting has no a priori precision bound; merged blocks provide upper and lower bounds on the true moment.Source: §4.1 · p. 5

4.2 Stable evaluation

  • Exponential tilting centers the count law on moment-dominating levels, while carrying the removed exponential scale analytically so the computation avoids underflow.Tilting commutes with convolution, so merging tilted coordinate laws introduces no bias.Source: §4.2 · pp. 5–6
  • For 1/2-decaying chains, truncation makes the stable merge cost Õ((√(mB_in) + m)/η), or Õ(m/η) for bounded alphabets, independently of surprisal range.The corresponding space bound is Õ(√B_in/η).Source: §4.2 · p. 6

5 Binning: the general case

For non-commensurate advice, the method bins per-coordinate surprisals onto a common grid, computes the exponent from the resulting histograms, and certifies binning error. Its guarantees depend on resolving per-coordinate surprisal gaps, with cost and error bounds specified under stated conditions.

5 Binning: the general case

  • Binning per-coordinate surprisals onto ηZ makes the summed support manageable, unlike direct enumeration of up to ∏ᵢbᵢ total surprisal values.Strict upward rounding places each key’s binned surprisal within mη of its true value; rounding probabilities instead does not yield the same support reduction.Source: §5 · pp. 6–7
  • The two convolved histograms track true P-mass and U-counts separately, while only surprisal values entering the rank are binned.The estimator substitutes the binned mass law and cumulative count into the finite-sum computation; the outer measure remains the true P.Source: §5 · p. 7
  • Round-to-nearest is admissible, but its O(η/√m) error behavior is heuristic rather than guaranteed.Its two-sided offsets widen the proof window to (m+1)η and increase ε_m by 1/m.Source: §5 · p. 7
  • The bin width must resolve per-coordinate gaps, and the empty-lattice diagnostic must be recomputed after refinement because its checked band widens as η shrinks.If bins collapse distinct levels, the certificate remains valid but becomes vacuous; the empty-lattice fraction near the mean is a rigorous falsifier under the stated condition.Source: §5 · p. 7
  • For every bin width η, the exact-arithmetic estimator has a computable certificate B on |sη−s|; directed-rounding interval arithmetic makes the enclosure end-to-end rigorous.The floating-point realization incurs an additional error unless that interval-arithmetic approach is used.Source: §5 · p. 7
  • Under the scaling-law hypotheses, B=O(C(s)η); for uniformly bounded alphabets, target δ above the atom-spacing floor costs Õ(mC(s)/δ), independent of surprisal range.The leading constant can grow as H̄₂/₃→0, and high-confidence advice can inflate it by more than an order of magnitude over a mildly biased coordinate.Source: §5 · p. 7

6 Accuracy of the binned estimator

This section evaluates the accuracy of binned estimates, relating rank changes to lattice-CDF growth and distinguishing exact finite-sum evaluation from computable, non-asymptotic error certificates. It presents a scaling-law bound and an a-posteriori certificate, alongside the estimator’s computational choices and precision limits.

6.1 The lattice shift sandwich

  • The true and binned ranks of each key lie in the common window [N eF(S(x)), N eF(S(x)+mη)], reducing rounding error to lattice-CDF growth across that window.Strict upward rounding is essential to the endpoint comparisons, and binning need not preserve key order.Source: §6.1 · p. 8

6.2 The level-saddle apparatus and the rate

  • Exponential tilting makes the lattice-CDF growth rate |τ_t|, with exact edge value θ*=|τ_H|=1 and rate decreasing to zero by t=μ_U.The explicit local-CLT error can be large at moderate m, which is why the certificate does not rely on that asymptotic route.Source: §6.2 · p. 9

6.3 The edge term and the worst-case bound

  • For t≥H, the reversed-hazard ratio is bounded by η(1+ε_r), yielding Theorem 6.7’s worst-case |sη−s| scaling with η relative to per-coordinate entropy.The scaling law requires its stated hypotheses, including the lattice-span and computed small-error conditions; the computable certificate does not require them.Source: §6.3 · p. 10

6.4 The computable certificate

  • On exhaustively enumerable models (m≤10), the certificate bracket held and lay within 1.14–1.45× C(s)η for η≤0.1, tightening with m and η.On heterogeneous advice, it scaled linearly in η across seven halvings. The certificate covers binning error in exact arithmetic; floating-point error is separate, and the reference implementation does not provide a rigorous end-to-end enclosure.Source: §6.4 · p. 11
  • Proposition 6.9 gives a non-asymptotic, computable bound B on |s_eta-s| under engine assumptions alone; Theorem 4.1 is an exact finite-level-sum identity, with floating-point error covered by Lemma 4.4.Theorem 6.7 is instead an asymptotic scaling law with computed constants and its own hypotheses.Source: §6.4 · p. 11
  • e^-Θ(m) atom spacing is irrelevant for heterogeneous advice because the floating-point floor δ ∼ 10^-10 binds first; for k-symbol i.i.d. advice, Θ(m^(1-k)) spacing stalls the certificate where the exact engine applies.That finite-rank regime needs no certificate.Source: §6.4 · p. 11
  • At m=8, substituting f(1/2) ≈ 1/2 m^-H2/3 overstates its true value by ≈20%; the epsilon_m term keeps the scaling-law certificate conservative, while the computed certificate avoids the substitution.The computed certificate divides by the computed f_eta(1/2).Source: §6.4 · p. 11
  • O(m^d) levels permit the exact engine for commensurate or bounded-rank surprisals; otherwise, bin with Algorithm 2 and refine eta until B ≤ delta, while the scaling law O(C(s)eta) is explanatory, not load-bearing.The scaling law holds under its own hypotheses.Source: §6.4 · p. 11

7 Cryptographic applications

The applications evaluate guessing-moment exponents for cryptographic advice settings where likelihood-ordered enumeration is the classical attack. The results vary with advice shape: skewed advice can yield substantially super-quadratic exponents, while smooth posteriors may remain close to 2.

7 Cryptographic applications

  • For cold-boot advice, independent asymmetric bit flips form an exact binary product posterior, and equal-length seeds and block-cipher keys carry identical advice.For AES-128, the exponent lies in [3.77, 4.11] at β=0.01 and [2.70, 2.85] at β=0.05 over the binomial sampling distribution of observed bit counts (95%).Source: §7 · p. 11
  • For seeds and ciphers without an algebraic shortcut, likelihood-ordered enumeration is the classical attack, and the corresponding cipher Grover oracles have been built and costed.The reported cipher oracles tolerate up to 40% noise; rank-2 marginals make these entries exact under the finite-rank engine.Source: §7 · p. 12
  • The ML-KEM and ML-DSA application uses a synthetic i.i.d. Bernoulli advice model calibrated to reported residual key ranks, not measured post-propagation marginals.The true marginals are heterogeneous and, on a graph with cycles, not exactly independent.Source: §7 · p. 12
  • Template attacks provide real-valued, noncommensurate product advice from sixteen independent per-byte posteriors, requiring binning in this framework.The posteriors are simulated from a Gaussian leakage model at literature SNR anchors.Source: §7 · p. 12
  • Above 2.7 across the practical cold-boot range and up to 3.97 in the synthetic model calibrated to the reported ML-DSA residual rank, the exponent is substantially super-quadratic for skewed advice.The 3.97 value is for the synthetic model, not the unknown belief-propagation posterior.Source: §7 · pp. 11–12
  • At residual 0.54 bits per byte, Block C reaches only 2.011; smooth Gaussian-shaped posteriors also stay near 2, whereas skew drives larger exponents.The asymmetric channel gives 2.763 against 2.532 for a symmetric one at n=128, β=0.05; in five rows the prior bound falls below 2.Source: §7 · p. 12

8 Conclusion

For product-distribution advice, the paper makes the Montanaro speedup exponent computable: exactly for finite-rank advice and with certified discretization error otherwise. This yields concrete per-scheme exponents at finite cryptographic parameters, including settings where the entropy-based estimate of remains loose.

8 Conclusion

  • For finite-rank product advice, the speedup exponent is computed exactly; otherwise it can be computed to precision above atom-spacing and floating-point floors, with a per-run certificate.A family of exponential tilts makes the computation provably accurate and numerically stable.Source: §8 · pp. 12–13
  • The method reduces moment dependence to one-dimensional convolutions of the surprisal law and uses exponential tilting for stable computation.Source: §8 · p. 13
  • The framework turns an asymptotic super-quadratic claim into a finite-parameter, per-scheme exponent, including cases where the entropy-based estimate of remains loose.Source: §8 · p. 13

and for a product source ln Í

For a product source, the cited passage gives asymptotic scales for the logarithmic guessing moments and their exponent ratio.

and for a product source ln Í

B Proof of the local CLT

The local-CLT proof controls the binned surprisal sum across its frequency band using a product characteristic-function hypothesis, then bounds low- and high-frequency contributions. The resulting error bound retains a quartic correction that can be numerically significant at finite size.

B Proof of the local CLT

  • The binned surprisals become independent integer-valued, nonidentically distributed summands, so the local CLT requires a product-characteristic-function hypothesis across the band |t| ≤ π/η.A per-coordinate Cramér condition has the wrong form because each coordinate can resonate inside the band.Source: B Proof of the local CLT · p. 14
  • Λ_η is the computed product hypothesis used to bound the high-frequency characteristic function, and its surrogate is chosen to remain FFT-certifiable and safe.The exact minimum is not FFT-certifiable and its Lipschitz constant can blow up when a coordinate characteristic function approaches zero.Source: B Proof of the local CLT · p. 14
  • The low-frequency bound expands the logarithm of each characteristic function, retaining a quartic term because a cubic-only remainder bound can fail.The ratio reaches 1.09 for i.i.d. Bernoulli(0.8) advice at m=256.Source: B Proof of the local CLT · p. 14
  • At m=256, the O(1/m) term is numerically 14–38% of the cubic term across representative ensembles, despite being asymptotically smaller under the stated regularity.Source: B Proof of the local CLT · p. 14
  • The high-frequency contribution is controlled by Λ_η on δ₁ ≤ |t| ≤ π/η, and the Gaussian-tail contribution is evaluated separately rather than treated as aliasing.For the tested ensembles at m=256, the computed Gaussian-tail bound is below 10^-15.Source: B Proof of the local CLT · pp. 14–15
  • Sharp density-level control is needed because the O(√m) increment in log-CDF exceeds the o(m) accuracy supplied by Cramér-level theory.Source: B Proof of the local CLT · p. 15

C Proofs of the rate lemma and the edge term

The rate proof controls the binned-to-exact error through a localized saddle-range bound and explicit propagation constants. Under bounded alphabets, the regularity estimates make the resulting error terms computable.

C Proofs of the rate lemma and the edge term

  • Outside the saddle range, the single-step ratio is O(η/σ_t), below its saddle-range order, so the supremum is governed by the saddle range.The proof uses the Gaussian hazard when z_t = O(1).Source: C Proofs of the rate lemma and the… · p. 15
  • The value-level hazard bound avoids differentiation and covers the near-uniform regime without requiring z to be large.The edge correction retains z^-2 within a relative factor.Source: C Proofs of the rate lemma and the… · p. 15
  • The propagated bound on ε_m combines the single-step rate with the saddle-range correction and an exponentially small localization remainder.The argument localizes to S ≥ H because the lower-surprisal region contributes exponentially little to both moments.Source: C Proofs of the rate lemma and the… · p. 16
  • At m = 256 on heterogeneous Bernoulli advice, ε_τ ≈ 0.070, exceeding 1/(m Var_1) ≈ 0.013 in the displayed error budget.The first term dominates numerically.Source: C Proofs of the rate lemma and the… · p. 16
  • For bounded alphabets, tilted per-coordinate variances and third moments yield uniform regularity estimates across the tilt range.Coordinates with zero surprisal range contribute nothing, so no per-coordinate variance floor is needed.Source: C Proofs of the rate lemma and the… · p. 16

C.1 Proof of the scaling law

The scaling-law proof bounds moment error by controlling rank distortion above a threshold and treating the lower region separately. It propagates the resulting moment bounds into an exponent certificate.

C.1 Proof of the scaling law

  • The proof telescopes single-step hazards above H, while the region below H contributes exponentially little to either guessing moment.The bound uses the pointwise rate above H and the fact that ranks below the entropy level are at most e^H.Source: §C.1 · p. 16
  • The binned and exact logarithmic moments differ by at most ρmη(1 + ε_m), plus an exponentially small remainder absorbed into ε_m.The proof controls rank distortion above H and bounds the contribution below H by localization.Source: §C.1 · p. 16
  • The certificate divides by the computed binned half-moment, avoiding the asymptotic input otherwise needed for a lower bound on the true denominator.The passage identifies this route as requiring no Arıkan input or asymptotic ingredient.Source: §C.1 · p. 16

D Proofs for the computable certificate

The certificate brackets true and binned rank moments using binwise bounds, then propagates computed intervals into an exponent error bound. The proof also distinguishes validity from informativeness and bounds the cost of a block-maximal shortcut.

D Proofs for the computable certificate

  • Binwise rank windows, a Chernoff cap, and a window-ratio bound enclose each key’s rank moment, yielding a computed interval for the true moment.Each bin uses whichever of the three bounds is tightest, without a threshold or tail-localization term.Source: D Proofs for the computable certificate · p. 17
  • The certificate is valid under the engine assumptions alone, but may be uninformative when the level structure is sparse.For Bernoulli(0.999) advice at m = 256, it returns 15.3; finite-rank exact evaluation covers families where the certificate is vacuous.Source: D Proofs for the computable certificate · p. 17

E.1 Optimality and the level averages

  • Likelihood-ordered guessing minimizes both classical and quantum guessing moments, and the minimizing order is independent of the moment parameter.Every likelihood-ordered enumeration gives the same minimum, including permutations within equal-probability blocks.Source: §E.1 · p. 17
  • The level average A_ρ is bounded using a Riemann-sum comparison, and its block-maximal surrogate approaches the thin-level limit.The stated evaluation uses direct sums for small blocks and a two-sided bracket for larger blocks.Source: §E.1 · p. 17
  • The block-maximal rank shortcut has exponent bias O(1/m), with deviation sign not fixed in advance.It inflates both moments at each level, while the aggregate may move either way.Source: §E.1 · pp. 17–18

E.2 Merge cost and floating-point stability

The merge engine uses balanced convolution, truncation, and exponential tilting to compute the required distributions with controlled numerical error. Its floating-point analysis quantifies both the supported precision and the limits of that guarantee.

E.2 Merge cost and floating-point stability

  • The balanced merge has total time Õ(√(mB_in + m)/η) for bounded alphabets and space Õ(√B_in/η).The support-aware tree combines partial convolutions and truncates them to windows around their analytically known means.Source: §E.2 · p. 18
  • At m = 512, the measured double-precision root error is 3.3 × 10^-15, while the conservative tree-error budget includes a node-count factor.The budget is about 32 times a depth-only count at m = 256.Source: §E.2 · p. 19
  • Log-domain assembly uses the 1-Lipschitz property of log-sum-exp to propagate bounded input errors into the moment estimate.The final ratio error is O(u_m poly/m) when the half-moment is Θ(m).Source: §E.2 · p. 19
  • For heterogeneous advice, the analyzed IEEE-double precision floor is about δ_min ∼ 10^-10, and high-confidence advice amplifies induced exponent error.The passage says rigorous end-to-end certification at higher working precision requires interval arithmetic.Source: §E.2 · p. 19

Related papers

Loading 2609.28226v1…