PaperlayerView exact revision on arXiv

Source-linked AI summary

Inevitability of Encrypted Traffic Side-Channel Leakage in the Multi-Class Setting

Guangjie Liu, Guang Cheng, Weiwei Liu

arXiv:2609.06322v1cs.CR

TL;DR

Existing information-theoretic results do not provide a positive leakage lower bound for every defense within a cost constraint in the realistic multi-class setting. This paper extends the binary result using per-class distinguishability and Wasserstein-1 defense budgets. On the 95-class dataset, measured MI has a strictly positive 95% confidence lower bound under every tested defense, while the paper identifies the limits of its empirical criterion.

  • Problem

    Existing information-theoretic guarantees do not bound leakage positively for every defense within a cost constraint, despite multi-class traffic analysis being a realistic setting.

    Source: §I · p. 1

  • Method

    The paper extends the binary theorem using per-class one-vs-rest distinguishability, Wasserstein-1 defense constraints, and summation, cascade, and accuracy bounds.

    Source: §I · p. 1

  • Results

    Measured MI has a strictly positive 95% confidence lower bound under every tested defense, and undefended OVR distinguishability predicts post-defense per-class leakage at Spearman ρ = 0.62–0.77.

    Source: §VI · p. 7

  • Takeaways & Limitations

    The per-class decomposition's structural advantage is that it supplies each class a critical cost and supports a cascade, unlike the pairwise construction.

    Source: §VI · p. 7

    With C = 0, ρ = 1, and plug-in W1 estimates, the operational criterion is empirical rather than a proof.

    Source: §V · p. 6

Abstract

from arXiv · show

The Side-Channel Existence Theorem proves $I(X;Y)>0$ in the binary, undefended setting, but is confined to pairwise arguments and ignores active defenses. We extend it to $k$ classes via the per-class decomposition $I(X;Y)=\sum_i\pi_i D_{\mathrm{KL}}(P_{Y|i}\|P_Y)$, with defense cost modelled by per-class Wasserstein-1 constraints $\sup_x W_1(Q_x^D,P_x)\le B$. Three results follow: (1) a summation-form MI lower bound over all active classes; (2) a cascade critical cost theorem and a per-class budget corollary, nonzero where the uniform-budget bound vanishes; (3) an accuracy corollary $\mathrm{Acc}^*\ge 2^{I_0}/k>1/k$. On a 95-class website fingerprinting dataset the measured MI has a strictly positive $95\%$ confidence lower bound under every defense tested. Against the strongest pairwise baseline---a convex program over all $\binom{k}{2}$ triangle constraints, also $\Theta(1)$ in $k$ under the same non-vanishing-gap conditions---the summation form is only $1.45\times$ stronger, so the case for the per-class decomposition is structural: only it gives each class a critical cost and a cascade. FRONT's apparent $122\times$ gap is inflated mainly by threshold exclusion rather than the inequality chain: on the active classes it is $21\times$, within $1.4\times$ of the $15\times$ measured undefended. Measuring the chain's two steps separately bounds the collapse onto one Lipschitz statistic below by $28\times$, against a divergence step measured at $1.5\times$. Undefended OVR distinguishability predicts post-defense per-class leakage at Spearman $\rho=0.62$--$0.77$, the transfer the certification procedure relies on. The framework carries over unchanged to a 100-class QUIC/TCP pair.

I. INTRODUCTION

The binary, undefended theorem leaves open how much information leaks across multiple classes under active defenses. This paper uses per-class distinguishability and Wasserstein-1 defense budgets to extend the analysis to defended k-class traffic.

I. INTRODUCTION

  • The prior theorem is binary and undefended, while existing information-theoretic work lacks a positive lower bound covering every defense within a cost constraint.The paper positions this result as the missing converse to prior work on achievable leakage reduction.Source: §I · p. 1
  • Per-class mutual-information decomposition motivates one-vs-rest distinguishability, with defense cost constrained by Wasserstein-1 distance.The defense acts on class-conditional protocol distributions; at zero budget, those distributions remain unchanged.Source: §I · p. 1, A. k-Class Causal Chain with Defense · p. 2
  • The paper establishes a summation-form leakage bound, per-class critical costs and budget bounds, and an accuracy lower bound above blind guessing.The summation form is reported as 1.45× stronger than the best pairwise construction; the per-class budget bound can remain nonzero when the uniform-budget bound vanishes.Source: §I · p. 1

A. k-Class Causal Chain with Defense

  • The framework assumes bounded mapping drift, Lipschitz class statistics, and observation non-degeneracy, with uniform constants across the statistic family.This common-constant condition licenses summing per-class bounds; the defense budget is accounted for separately.Source: A. k-Class Causal Chain with Defense · p. 2
  • Wasserstein-1 cost bounds the change in Lipschitz statistics, whereas KL can be infinite for support-changing defenses and total variation saturates for disjoint supports.The experiments use Euclidean distance on normalized features, not an overhead-based ground metric.Source: A. k-Class Causal Chain with Defense · p. 2

B. Per-Class One-vs-Rest Distinguishability

Per-class one-vs-rest distinguishability measures how class i differs from the prior-weighted mixture of all other classes. It aligns with the per-class MI decomposition in a way pairwise gaps do not.

B. Per-Class One-vs-Rest Distinguishability

  • One-vs-rest distinguishability compares a class with the prior-weighted conditional expectation over all non-i classes.It measures how far class i deviates from the mixture of the others.Source: B. Per-Class One-vs-Rest… · p. 2
  • The per-class decomposition indexes each MI term by its distance to the population mixture, while pairwise gaps constrain those distances only through triangle inequalities.Even a convex program using all pairwise triangle constraints cannot identify an individual class or yield its critical cost and cascade.Source: B. Per-Class One-vs-Rest… · p. 2
  • For a centroid class, signed pairwise gaps can cancel, making its OVR distinguishability zero despite pairwise distinguishability from every other class.The sufficient condition therefore says nothing about that class.Source: B. Per-Class One-vs-Rest… · p. 2

C. Critical Costs and Active Class Set

Per-class critical costs determine when classes remain active under a defense budget. As the budget grows, the active set shrinks in a cascade until the global critical cost extinguishes every lower bound.

C. Critical Costs and Active Class Set

  • A class is active when its OVR gap exceeds the drift margin 2Lφ(C + B), and the active set defines the effective class count.The critical-cost definition assigns a threshold to each class.Source: C. Critical Costs and Active Class Set · p. 2
  • As the budget rises, the active set loses classes one at a time at distinct critical costs, or several together when thresholds are tied.The cascade is measured on real traffic in Fig. 1(a).Source: C. Critical Costs and Active Class Set · p. 2
  • The global critical cost is the endpoint at which every lower bound is extinguished.The per-class critical costs are ordered to define this endpoint.Source: C. Critical Costs and Active Class Set · p. 2

A. k-Class Inevitability Theorem

A lemma converts a Wasserstein-1 defense budget into observation-layer separation. Summing the resulting per-class information contributions yields a positive multi-class leakage bound whenever at least one class is active.

A. k-Class Inevitability Theorem

  • The proof converts the W1 budget into a guaranteed observation-layer separation using Lipschitz robustness, mapping drift, and observation non-degeneracy.A bounded-statistic lemma turns the retained mean gap into a total-variation lower bound.Source: A. k-Class Inevitability Theorem · pp. 2–3
  • For any defense within budget B, the k-class theorem gives a positive MI lower bound whenever the active class set is nonempty.The bound sums the contributions of active classes; inactive terms are nonnegative and may be dropped.Source: A. k-Class Inevitability Theorem · p. 3
  • Each active class contributes independently to the MI sum, which remains Θ(1) as k grows under a uniform prior and common residual distinguishability.At k = 2, the sum recovers the binary bound for every prior.Source: A. k-Class Inevitability Theorem · p. 3

B. Cascade Critical Cost Theorem

Theorem 2 makes the lower bound decline through ordered per-class critical costs, while heterogeneous realized budgets yield class-specific thresholds based on each class and the prior-weighted costs of its complement.

B. Cascade Critical Cost Theorem

  • As the budget crosses ordered critical costs, classes exit the active set until the minimum extinguishing budget removes every lower bound.At tied thresholds, multiple classes can exit together.Source: B. Cascade Critical Cost Theorem · p. 3
  • Between thresholds, the lower bound sums quadratic functions of the remaining classes, joins continuously with a continuous first derivative, and changes curvature at each threshold.The summands vanish quadratically at their respective thresholds.Source: B. Cascade Critical Cost Theorem · p. 3
  • Theorem 1 is the special case in which every class has the same budget.Source: B. Cascade Critical Cost Theorem · p. 3
  • With heterogeneous costs, each class’s threshold uses its own budget and the prior-weighted average cost of the other classes, rather than twice the uniform-budget drift.The per-class threshold is never larger than the uniform threshold based on the maximum class cost, and is strictly smaller when costs differ.Source: B. Cascade Critical Cost Theorem · pp. 3–4

C. Attack Accuracy Corollary

The accuracy corollary converts a valid mutual-information lower bound into a Bayes-optimal k-class accuracy bound, while the per-class guarantee remains useful under prior skew.

C. Attack Accuracy Corollary

  • Acc* is bounded below by the larger of the majority-class prior and 2^I0/k, where I0 is a valid lower bound on I(X; YD).Source: C. Attack Accuracy Corollary · p. 4
  • Any positive I0 makes the corollary’s bound exceed chance accuracy 1/k.This holds whenever at least one class remains active.Source: C. Attack Accuracy Corollary · p. 4
  • For a specific class, the optimal test against all other classes has a prior-free balanced-accuracy guarantee, even when class priors are skewed.The counts keff(B) and kpc_eff give the number of classes for which this guarantee is nontrivial; both decline to zero as defense grows.Source: C. Attack Accuracy Corollary · p. 4

IV. EMPIRICAL VALIDATION

The experiments evaluate the framework on closed-world website traffic and a QUIC/TCP pair, estimating mutual information on a three-dimensional observable and Wasserstein quantities on an eleven-dimensional one.

IV. EMPIRICAL VALIDATION

  • The evaluation covers 95 sites with 200 traces each under three defenses, plus a 100-site, 100-trace-per-stack QUIC/TCP comparison.Walkie-Talkie was excluded because its half-duplex traces occupied only 33 of 125 symbols and its estimate was unstable, with CI [0.67, 1.37].Source: A. Protocol · p. 4
  • Mutual information is estimated on Y(3), comprising inbound ratio, mean IAT, and direction-flip rate; the first three coordinates of Y(11) are exactly Y(3).Y(11) adds packet count, flow duration, IAT spread and percentiles, burst count and length, and cumulative direction.Source: A. Protocol · p. 4
  • MI uses a Miller–Madow-corrected plug-in estimate with five bins per dimension and 200 stratified bootstrap replicates for percentile 95% intervals.Source: A. Protocol · p. 4
  • OVR distinguishability and per-class defense cost are estimated as earth-mover distances on Y(11), with the non-class mixture subsampled to 2,000 traces.The W1 optimizer can differ by class, so the definition allows a family of class-specific statistics with uniform constants.Source: A. Protocol · p. 4
  • The table’s bound concerns I(X;Y(11)), whereas measured MI is on Y(3), so passing the richer-observable test is sufficient but not necessary.The like-for-like comparison in Y(3) is 2.8× less favourable; the empirical test is a stress test, not a certificate, because proxy parameters maximize the bound and estimates lack one-sided finite-sample control.Source: A. Protocol · p. 4

B. Main Verification

Measured mutual information remains positive under every tested defense, while the theory’s gap is shaped by active-class exclusion, the inequality chain, and observable dimensionality.

B. Main Verification

  • Every measured MI has a strictly positive 95% CI lower bound, including settings where the theory gives no bound.FRONT leaves 0.445 bit at mean cost 0.383, WTF-PAD 0.585 at 0.709, and TrafficSliver 0.482 at 0.791.Source: B. Main Verification · p. 5
  • For the compared stacks, i is 1.715 versus 1.629 and the floor is 0.359 versus 0.371; summing over 100 classes averages these differences out.Each stack is normalized by its own percentiles, so the comparison spans two scales.Source: B. Main Verification · p. 5

C. Where the Gap Comes From

  • Under FRONT, seven active classes carry 7.4% of prior mass and yield 0.0762 bit of matched MI (95% CI [0.0720, 0.0807]), making the gap 20.9× rather than 122×.That matched gap is within 1.4× of the undefended 15.0× gap; the apparent degradation comes from including classes the theorem excludes.Source: C. Where the Gap Comes From · p. 5
  • With bound and measurement both in Y(3), the gap is 42.3×; the measured divergence step contributes 1.50×, while collapsing to one Lipschitz statistic accounts for 28.2×.The 28.2× is an underestimate under the stated data-processing comparison, whereas the divergence ratio has no proven direction.Source: C. Where the Gap Comes From · pp. 5–6
  • Estimating in Y(11) rather than Y(3) raises the bound by 2.8× net, turning the same-space 42.3× gap into the table’s 15.0× gap.The richer space lifts the squared OVR gap by 12.7× but also admits a 4.5× larger M^2; this is a bound on a richer observable, not a tighter one on the measured observable.Source: C. Where the Gap Comes From · p. 6
  • For WTF-PAD, only one class remains active and its 2.55 × 10^-5-bit bound corresponds to a matched gap of 757×.It clears its threshold by 0.083 out of an OVR distinguishability of 1.343.Source: C. Where the Gap Comes From · p. 6
  • TrafficSliver has no active class and certifies nothing, although measured MI remains 0.482 bit with a strictly positive confidence interval.The sufficient condition can go silent before measured leakage does as per-class cost approaches the OVR spectrum.Source: C. Where the Gap Comes From · p. 6

D. What the OVR Decomposition Buys

The OVR sum modestly exceeds the strongest pairwise bound, while its structural advantage is class-specific certification. Undefended OVR distinguishability also tracks post-defense per-class leakage, unlike the defended summand itself.

D. What the OVR Decomposition Buys

  • 7.55 × 10^-2 bit for the OVR sum is 1.45× the strongest pairwise convex program’s 5.21 × 10^-2 bit on CW.The disjoint matching gives 4.47 × 10^-2 bit and the single best pair gives 6.35 × 10^-3 bit.Source: D. What the OVR Decomposition Buys · p. 6
  • The pairwise constraints are slack at the OVR optimum, so the pairwise family adds no information beyond OVR floors and yields no per-class certificate or cascade.At the OVR optimum, every pairwise constraint is slack by at least 0.028 in TV.Source: D. What the OVR Decomposition Buys · p. 6

E. Does the Bound Rank Classes Correctly?

  • Undefended OVR distinguishability predicts post-defense leakage with Spearman ρ = 0.76 undefended, 0.62 under FRONT, and 0.77 under WTF-PAD.The reported 95% intervals are [0.64, 0.85], [0.47, 0.74], and [0.65, 0.84], respectively.Source: E. Does the Bound Rank Classes… · p. 6
  • By contrast, the defended summand’s correlation is ρ = 0.25 under FRONT and undefined under WTF-PAD, where no class exceeds the per-class threshold.Only two classes remain above threshold under FRONT.Source: E. Does the Bound Rank Classes… · p. 6
  • Using an 11-D estimate against a 3-D measurement shifts correlations unsystematically; the ordering should be estimated in the adversary’s expected observable space.The reported correlations shift 0.76 → 0.44, 0.62 → 0.75, and 0.77 → 0.56; the spaces agree only at ρ = 0.55.Source: E. Does the Bound Rank Classes… · p. 6

F. Robustness

Robustness checks preserve the positive MI conclusion across tested bin counts and subsamples. In the discussion, the certification procedure is presented as a cost floor and empirical falsification test, with scope limits on observable choice and cost assumptions.

F. Robustness

  • Across bin counts 3–7, CW’s estimated MI stayed positive at 0.571–1.283 bit; replacing W1 with centroid distance costs a factor 1.56.The Miller–Madow correction was 0.025 bit, or 2.1% of the estimate; varying the ¬i subsample changed I0 by under 0.2%.Source: F. Robustness · p. 6

V. DISCUSSION

  • The target cost is a floor, not a recipe: spending less misses the target, while spending more does not guarantee reaching it.After deployment, |Apc| > k0 falsifies the target without training a classifier, but the verdict is an empirical criterion under plug-in estimates.Source: §V · p. 6
  • FRONT’s maximum estimated per-class cost is 1.201, yet step (iii) returns |Apc| = 7, missing every target below k0 = 7.The cost for k0 = 1 is 0.535, nearly twice the 0.284 cost for k0 = 10.Source: §V · pp. 6–7
  • The theorem constrains Lipschitz observables, including deep-fingerprinting embeddings, but the proxy cannot predict deep-attack absolute accuracy; embedding-space W1 estimation faces the curse of dimensionality.The 2.8× gain from the 11-D estimate is specific to these data.Source: §V · p. 7
  • A shared class constant makes C = max_i Ci conservative under heterogeneous Ci; an expected-cost constraint does not imply the per-input W1 bound.The realized-cost corollary covers that setting; no a fortiori argument extends the uniform-budget bound to it.Source: §V · p. 7
  • The k = 95 and k = 100 results verify summation structure, not Θ(1) asymptotics; optimal budget allocation across classes remains open.The zero-gap centroid-class case is absent in these measurements: the smallest OVR gap is 61% of the mean in Y (11) and 52% in Y (3).Source: §V · p. 7

VI. CONCLUSION

The paper extends side-channel leakage inevitability to defended k-class traffic and reports positive measured MI under every tested defense. Its per-class decomposition provides class-specific certificates and critical costs, while empirical comparisons show that the bound remains conservative.

VI. CONCLUSION

  • The work extends inevitability from binary undefended traffic to defended k-class traffic with a summation-form bound, per-class critical costs, a budget corollary, and an accuracy corollary.The per-class budget corollary can remain nonvacuous where the uniform-budget bound is empty.Source: §VI · p. 7
  • The summation form is 1.45× stronger than the best pairwise construction, but its principal gain is a per-class certificate rather than a larger bound.Matching the active classes reduces FRONT’s gap from 122× to 20.9×, compared with 15.0× undefended.Source: §VI · p. 7
  • Every tested defense retains a strictly positive 95% confidence lower bound on measured MI; undefended OVR distinguishability predicts post-defense leakage at Spearman ρ = 0.62–0.77, and the framework transfers unchanged across QUIC and TCP.The bound remains conservative, with the active-class matched FRONT gap at 20.9×.Source: §VI · p. 7
  • Under TrafficSliver, no class is active under the sufficient condition even though 0.482 bit of MI remains measurable.This marks a boundary of the certificate, not zero measured leakage.Source: §VI · p. 7
  • The theory offers two attack-model-free design metrics: k*_eff counts certifiably identifiable classes, while B*_max is a budget floor rather than a sufficient spend.FRONT exceeds B*_max yet leaves seven classes above the per-class criterion.Source: §VI · p. 7
  • The authors identify tightening the Lipschitz-direction aggregation, allocating budgets across classes, and combining the converse with achievability as next steps.The proposed combination would join this converse with the achievability side,.Source: §VI · p. 7
Loading 2609.06322v1…