Search papers, labs, and topics across Lattice.
This paper introduces a Quantitative Information Flow (QIF) framework for analyzing Local Differential Privacy (LDP) frequency estimation protocols, addressing the limitations of relying solely on the 蔚 parameter for privacy comparisons. By modeling LDP mechanisms as probabilistic channels and using refinement (Blackwell ordering), the framework enables principled classifications of protocols based on their resistance to diverse attacker models. The analysis reveals that some protocols previously considered "optimal" are actually incomparable or dominated by others, offering a more nuanced understanding of their privacy guarantees.
Forget epsilon-only comparisons: a QIF lens reveals that some "optimal" LDP protocols are actually weaker than you thought.
Local Differential Privacy (LDP) has become the de facto standard for privacy-preserving data collection in large-scale systems, in particular for the purpose of estimating frequencies. However, the current research landscape lacks a systematic and principled way to compare LDP protocols. The parameter $\varepsilon$ of LDP is considered the measure of privacy, but it only bounds worst-case distinguishability. Other comparisons rely on utility-driven analyses, where mechanisms are ranked based on their ability to preserve data utility for a given privacy budget $\varepsilon$. Both such kinds of comparisons fail to account for the strength of protocols against diverse attacker models. In this paper, we propose a framework for analyzing LDP frequency estimation protocols through the lens of Quantitative Information Flow (QIF). By modeling LDP mechanisms as probabilistic channels, we leverage the concept of refinement (Blackwell ordering) to establish more principled classifications. This approach allows us to determine when one protocol is intrinsically superior to another for all possible adversaries, and to discuss the implications for utility. In particular, our analysis uncovers cases where protocols previously deemed"optimal"are, in fact, incomparable with, or strictly dominated by, other protocols. We provide a formal QIF-based treatment of seven state-of-the-art protocols, including Generalized Randomized Response (GRR), local hashing variants (BLH, OLH), unary encoding schemes (SUE, OUE), and Thresholding with Histogram Encoding (THE). This perspective bridges the gap between the LDP and formal methods communities and enables principled, adversary-aware reasoning about locally private systems.
