Inevitability of Encrypted Traffic Side-Channel Leakage in the Multi-Class Setting
TL;DR
A summation-form MI lower bound over all active classes, a cascade critical cost theorem and a per-class budget corollary, nonzero where the uniform-budget bound vanishes, and an accuracy corollary.
Abstract
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.