Second-Order Expansion of Privacy Amplification Under f-Divergence Criteria

A. Motivation and problem setting

• Privacy amplification uses a public seed to hash Alice’s partially secret data into a shorter key, with security requiring the output to be uniform and independent of the adversary’s view.The view consists of the side information Y and public seed S.Source: A. Motivation and problem setting · p. 1
• At first order, extractable randomness is nH + o(n) and does not depend on the standard security criterion, but refined asymptotics can depend on that criterion.Here H is conditional entropy; the paper studies criteria based on f-divergences, including total variation and Rényi divergences of orders α ∈ (0, 1).Source: A. Motivation and problem setting · pp. 2–3

B. Main findings and discussion

• Two independent Gaussian limits describe fluctuations of the conditional mean across side-information values and of surprisal within each fixed fibre.Their variances sum to total varentropy V.Source: B. Main findings and discussion · p. 4
• The fixed-marginal limit generally depends on the split between across-side-information and within-fibre variance, whereas the optimized limit depends only on total varentropy.The fixed profile averages f of conditional Gaussian tails; the optimized profile applies f after averaging those tails.Source: B. Main findings and discussion · p. 4
• When f is affine on [0, 1], Jensen’s inequality is an equality and the two profiles coincide; total variation is the principal example, recovering its known expansion.The paper makes no novelty claim for the total-variation specialization.Source: B. Main findings and discussion · p. 4
• For Rényi criteria of orders α ∈ (0, 1), the corollary evaluates both second-order limits exactly, closing gaps left by earlier nonmatching bounds,.Hayashi and Tan’s Eqs. (73) and (74) gave nonmatching bounds for the two criteria rather than exact fixed-L limits.Source: B. Main findings and discussion · p. 4

C. Related work

• Prior quantum work obtained a tight second-order expansion under purified distance after optimizing the reference side-information state, while the corresponding fixed-marginal problem remained unsettled.The paper relates the optimized result to the order-1/2 Rényi-divergence criterion through monotone transformations between purified distance, fidelity, and D1/2.Source: C. Related work · p. 4
• These strong-converse results describe rates fixed beyond the first-order boundary, while the profiles resolve the nH + L√n + o(√n) transition window around that boundary, [28],.Source: C. Related work · p. 5
• Axiomatic characterization identifies exponential averages of conditional Rényi entropies as the general family of classical conditional entropies satisfying additivity, relabeling invariance, and monotonicity under conditional mixing [29].This provides structural context for the conditional Rényi quantities considered in the paper.Source: C. Related work · p. 5

II. FORMAL STATEMENT OF MAIN RESULTS

• The section states the exact second-order limits, explains the resulting Gaussian profiles, and derives the Rényi and total-variation corollaries.Source: §II · p. 5

A. Optimal leakage and the Gaussian f-profile

• At r = 0 the profile uses the constant Φ(x), while its continuous extension at r = 1 is f(0)Φ(−x).The endpoint at r = 1 follows by dominated convergence and f(1) = 0.Source: A. Optimal leakage and the Gaussian… · p. 5
• The Gaussian f-profile is continuous and nonincreasing, and is strictly decreasing when f is strictly decreasing on (0, 1).Source: A. Optimal leakage and the Gaussian… · p. 5
• For finite-support PXY, V > 0, an admissible generator, and log Mn = nH + √n L + o(√n), the theorem gives exact limits for both leakage criteria.Two-universal hashing achieves both limits, and both converses hold for arbitrary seeded hash families.Source: A. Optimal leakage and the Gaussian… · p. 6
• The optimized-marginal limit equals the lower bound; for the fixed-marginal limit, the lower and upper bounds are attained when V1 = 0 and V2 = 0, respectively.If f is affine on [0, 1], the bounds coincide and only total variance remains.Source: A. Optimal leakage and the Gaussian… · p. 6

• The leakage criterion is nondecreasing in the integer output length for either marginal choice.Source: B. Fixed-leakage expansions · p. 6
• For the i.i.d. laws in the corollary, the supremum over feasible output lengths is bounded for sufficiently large n and is attained.The attained supremum is the largest extractable integer output length.Source: B. Fixed-leakage expansions · p. 6
• Under the assumptions of Corollary 2, fixed-leakage output lengths have an asymptotic expansion for each δ in (0, f(0)).The supplied passage states the corollary and its assumptions but does not include the expansion formula.Source: B. Fixed-leakage expansions · p. 6

• For α in (0, 1), the Rényi specialization gives exact second-order limits for both fixed- and optimized-marginal criteria.The power generator is fα(t) = (1 − t^α)/(1 − α), and applying the Rényi transformation to the f-divergence limits yields the profile.Source: C. Rényi divergences as a corollary · pp. 6–7
• Two-universal hashing achieves the stated Rényi limits, and the converses apply to arbitrary seeded hash families.Source: C. Rényi divergences as a corollary · p. 7
• The Rényi profile lies between Φ(x) and Φ(x)^α.The supplied result states Φ(x) ≤ Gα,r(x) ≤ Φ(x)^α.Source: C. Rényi divergences as a corollary · p. 8
• For nonlinear generators, a single total variance does not determine the second-order penalty.With a fixed reference, the conditional variance split remains; optimizing the marginal depends only on the unconditional surprisal tail.Source: C. Rényi divergences as a corollary · pp. 8–9
• Total variation has the same exact second-order leakage for fixed and optimized reference marginals, although their finite-blocklength values may differ.This recovers the result in,,.Source: C. Rényi divergences as a corollary · pp. 8–9

• The section establishes the finite-blocklength converse and achievability bounds used in the asymptotic proof.Source: §III · p. 9
• The capped cost is the smallest f-divergence cost compatible with the coordinate cap, with unused mass assigned to dummy symbols.In the application, c = 2^-h and h = log M gives the cap 1/M associated with a uniform law on M output symbols.Source: §III · p. 9
• For the fixed-reference criterion, the one-shot quantity averages optimal capped costs separately across conditional fibres using the actual marginal P_Y.Source: §III · p. 9
• For the optimized criterion, the reference marginal is chosen to minimize the weighted sum of scaled fibre costs.Source: §III · pp. 9–10
• Two-universality controls the expected squared deviation of hash-bin weights from equal allocation by the sum of squared input weights.This is the second-moment estimate used in the direct part.Source: §III · p. 11
• The light-symbol cutoff leaves each retained symbol a factor 2^-τ below the target bin mass, enabling near-uniform spreading by two-universal hashing.The modulus of continuity converts the resulting ℓ1 approximation into an approximation of the f-divergence cost.Source: §III · p. 11

• Water filling raises a common multiplier from t = 1 until coordinates reach the ceiling c, with t fixed by the total-mass constraint.Source: §IV · p. 12
• The capped optimization has a common optimizer for the objectives in (50) and (52), independent of both f and a.When the cap times support size is below one, the support coordinates are capped and remaining mass goes to dummy symbols; otherwise a normalizing multiplier sets the total mass to one.Source: §IV · pp. 12–13
• The water-filling value has an exact representation in terms of the surprisal Jp = −log pX(X).The supplied passages introduce the threshold and representation but do not include the full displayed formula.Source: §IV · p. 13
• Under the stated anti-concentration and support-size conditions, the capped-divergence limit holds uniformly over compact scale intervals.The passage states that this asymptotic link is used when the reference marginal is optimized.Source: §IV · pp. 13–14

Gaussian limits

• The centered conditional mean of the block surprisal has a Gaussian limit, with the degenerate interpretation Zn = 0 when V1 = 0.The ordinary central limit theorem gives this limit.Source: §V · p. 15

Capped divergences

• The conditional tail approximation transfers to capped divergences locally uniformly over the scale used for reference-marginal optimization.This is the stated role of the next lemma.Source: §V · p. 15

Endpoint case

• When V2 = 0, each nonzero conditional distribution is uniform on its support, and a separate endpoint argument establishes the limits.The endpoint lemma treats this variance regime separately.Source: §V · p. 18

Conditional limits

• The capped one-shot quantity for the converse and the conditional light-tail quantity for achievability converge to the same fixed-reference Gaussian profile.The two limits identify that profile in different forms.Source: §V · p. 18

Optimized marginal

• Optimizing the reference marginal collapses the conditional profile to f applied to a single unconditional Gaussian tail.The proposition also gives the unconditional tail limit used for achievability.Source: §V · p. 19

Fixed marginal

• For fixed marginals, the converse uses conditional water filling, while hashing the light part of each conditional source reduces achievability to the same conditional Gaussian profile.The achievability argument uses a two-universal family and a vanishing modulus-of-continuity error.Source: §VI · p. 21

Optimized marginal

• Conditional water filling and the Gaussian-profile limit evaluate the optimized-reference converse, while tail-tilted two-universal hashing gives the matching achievability bound.The achievability argument reduces the remaining quantity to the unconditional surprisal tail.Source: §VI · pp. 21–22

Optimized-marginal achievability

• The shifted unconditional tail converges to Φ(x), yielding the matching optimized-marginal upper bound.The proof uses the tail sandwich with shift τn.Source: §VI · p. 22

Fixed-leakage consequence

• The profiles are continuous and strictly decreasing, and the rounded feasible and infeasible output lengths bracket the largest admissible integer length.The resulting limits give the fixed-leakage expansions for both marginal treatments.Source: §VI · pp. 22–23

Scope of divergence criteria

• The finite-constant profile assumes lim_{t→∞} f(t)/t = 0; forward relative entropy and superlinear divergences such as χ2 violate this condition.At the central-limit rate, relative-entropy leakage has √n scaling.Source: §VII · p. 23

Marginal dependence

• The total-variation generator is affine on [0, 1], giving the same second-order profile with fixed or optimized marginals; nonlinear generators generally retain separate V1 and V2 dependence only for the fixed criterion.Source: §VII · p. 23

Alphabet assumptions

• Finite alphabets provide uniform third moments and conditional anti-concentration; countable-alphabet extensions may require moment, support-growth, and uniform-integrability hypotheses.Quantitative third-order control is described as separate from the established second-order profile.Source: §VII · p. 23

APPENDIX A WHY FIXING AND OPTIMIZING THE REFERENCE MARGINAL DIFFER

• The converse caps large conditional probabilities at the threshold and scales smaller entries uniformly; near threshold, those entries contribute f(q_n(y_n)).The capped entries contribute vanishingly under the stated assumption f(t)/t → 0.Source: Appendix A · p. 24
• With a fixed reference, f is applied before averaging over side information, so the leakage profile can depend separately on V1 and V2.V2 controls the conditional Gaussian transition; V1 describes variation in its location across side information.Source: Appendix A · p. 24
• Optimizing the reference aggregates conditional tail probabilities before applying f, so the profile depends only on total variance V despite both fluctuation sources remaining.The optimized tail is the unconditional probability that block surprisal exceeds the threshold.Source: Appendix A · pp. 24–25
• When V1=0 both criteria give f(Φ(x)); when V2=0 they give f(0)Φ(−x) versus f(Φ(x)), while affine f makes them coincide for every variance split.Total variation is the cited affine example.Source: Appendix A · p. 25

APPENDIX B NEAR-BOUNDARY COMPATIBILITY WITH FIXED-RATE EXPONENTS

• The fixed-rate exponent and second-order expansion have the same parameter and coefficient on a common scale, but this iterated-limit match establishes no moderate-deviation theorem.The comparison also does not address the optimized-marginal criterion.Source: Appendix B · pp. 25–26