Beyond Epsilon: A Principled QIF Framework for Local Differential Privacy

Title: Beyond Epsilon: A Principled QIF Framework for Local Differential Privacy

Problem Statement
Local Differential Privacy (LDP) has become the standard for privacy-preserving data collection in large-scale systems, particularly for frequency estimation. However, the current landscape for comparing LDP protocols relies heavily on two limited approaches:

1. The $\epsilon$ parameter: This bounds worst-case distinguishability but fails to capture the actual information leakage under realistic inference attacks (e.g., data reconstruction or re-identification). Two protocols satisfying the same $\epsilon$-LDP guarantee may exhibit significantly different leakage behaviors.
2. Utility-driven analysis: Protocols are ranked based on estimation error (e.g., Mean Squared Error) for a fixed $\epsilon$. This view is metric-dependent and does not provide a principled ordering of privacy strength independent of the specific utility function.

Consequently, there is a lack of a systematic, adversary-independent method to determine when one LDP protocol is intrinsically more private than another.

Methodology
The authors propose a framework based on Quantitative Information Flow (QIF) to analyze LDP frequency estimation protocols. The core methodology involves:

• Channel Modeling: Representing LDP mechanisms as probabilistic information-theoretic channels defined by row-stochastic channel matrices ($C_{x,y} = \Pr[Y=y|X=x]$).
• Refinement Relations (Blackwell Ordering): Utilizing the concept of channel refinement ($B \sqsubseteq A$) to establish a partial order. Protocol $A$ refines $B$ if $A$ leaks no more information than $B$ to any average-case adversary, regardless of their prior knowledge or specific gain function. This is equivalent to $A$ being a "garbling" of $B$ (i.e., $B \cdot W = A$ for some channel $W$).
• Connection to $f$-Differential Privacy: Leveraging the equivalence between QIF refinement and the ordering of trade-off functions in $f$-DP (derived from the Neyman-Pearson lemma) to compare mechanisms, particularly for binary channels.
• Vulnerability Measures: Analyzing protocols using Bayes capacity (maximum average-case leakage) and linking data reconstruction attacks directly to Bayes vulnerability under a uniform prior.

The authors apply this framework to seven state-of-the-art protocols: Generalized Randomized Response (GRR), Subset Selection (SS), Binary Local Hashing (BLH), Optimized Local Hashing (OLH), Symmetric Unary Encoding (SUE), Optimized Unary Encoding (OUE), and Thresholding with Histogram Encoding (THE).

Key Contributions

1. Unified QIF Framework: The paper provides a metric-independent framework for comparing LDP protocols via channel matrices and refinement relations, enabling comparisons across diverse adversaries and utility functions.
2. Bridging LDP and QIF: The authors formally demonstrate that data reconstruction attacks studied in prior literature coincide with standard QIF notions of Bayes vulnerability. Specifically, the expected success rate of such attacks corresponds to the Bayes capacity of the LDP channel.
3. Correction of Local Hashing Analysis: The paper identifies and corrects an error in the expected data reconstruction attack analysis for Local Hashing (LH) protocols (specifically BLH and OLH) reported in previous work [8]. The authors derive the correct Bayes risk via averaged vulnerability, providing a formula that matches experimental evaluations for all domain sizes, unlike the previous approximation which failed for small domains.
4. Refinement Analysis: The study establishes refinement relations between protocols, uncovering that:
   • GRR, SUE, OUE, and THE families form "refinement families" where privacy monotonicity holds with respect to $\epsilon$.
   • OUE and SUE are incomparable (neither refines the other) in the bitwise setting.
   • THE refines SUE for all $\theta$, but the relationship between THE and OUE depends on the threshold $\theta$ and $\epsilon$.
   • Protocols previously deemed "optimal" based on error metrics are sometimes strictly dominated by or incomparable to other protocols when viewed through the lens of information leakage.

Results

• Experimental Validation: Using the Kosarak dataset, the authors experimentally corroborated the theoretical refinement relationships. For instance, they confirmed that when the threshold $\theta$ in THE satisfies specific conditions relative to $\epsilon$, OUE leaks more information than THE; otherwise, the relationship is non-refined.
• Bayes Capacity Convergence: The analysis of Bayes capacities revealed distinct convergence behaviors as $\epsilon$ increases:
  • GRR, SS, and THE converge to $k$ (the domain size).
  • SUE converges to a value slightly higher than $k$.
  • BLH converges to 2 (due to its binary output).
  • OLH and OUE converge to approximately $k/2$.
• Correction of LH Formulas: The new formula for the Adversarial Success Rate (ASR) of Local Hashing (Eq. 26) was shown to match experimental results for all $k$ and $\epsilon$, whereas the previous formula (Eq. 25) deviated significantly for small domain sizes.

Significance
The paper claims to bridge the gap between the LDP and formal methods communities. By moving beyond the single parameter $\epsilon$ and utility-specific metrics, the proposed QIF-based approach enables "principled, adversary-aware reasoning" about locally private systems. It reveals that classifications based solely on estimation error can be misleading, as they may overlook cases where a protocol is strictly dominated by another in terms of privacy leakage. The framework offers a more robust and comprehensive method for evaluating protocol superiority, ensuring that privacy guarantees are understood not just as worst-case bounds, but as precise measures of information flow against diverse threat models.