Beyond Epsilon: A Principled QIF Framework for Local Differential Privacy

• URL: http://arxiv.org/abs/2605.26465v1
• Date: Tue, 26 May 2026 02:20:11 GMT
• Title: Beyond Epsilon: A Principled QIF Framework for Local Differential Privacy
• Abstract summary: Local Differential Privacy (LDP) has become the de facto standard for privacy-preserving data collection in large-scale systems.<n>We propose a framework for analyzing LDP frequency estimation protocols through the lens of Quantitative Information Flow (QIF)
• Score: 8.07472341548849
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• An introduction to local differential privacy protocols using block designs [1.360738859820932]
  Local differential privacy (or LDP) protocols utilise the randomised encoding of outcomes of an experiment using a transition probability matrix (TPM)<n>Several authors have observed that balanced incomplete block designs (BIBDs) provide nice examples of TPMs for LDP protocols.<n>We show that the optimal estimators for BIBD-based TPMs are precisely those obtained from the Moore-Penrose inverse of the corresponding TPM.
  arXiv  Detail & Related papers  (2026-02-02T19:58:58Z)
• When Focus Enhances Utility: Target Range LDP Frequency Estimation and Unknown Item Discovery [7.746385592375338]
  Local Differential Privacy protocols have been successfully deployed in real-world scenarios by tech companies like Google, Apple, and Microsoft.<n>We propose a Generalized Count Mean Sketch protocol that captures many existing frequency estimation protocols.<n>We present a novel protocol for collecting data within unknown domain, as our frequency estimation protocols only work effectively with known data domain.
  arXiv  Detail & Related papers  (2024-12-23T05:50:11Z)
• Differentially Private Random Feature Model [47.35176457481132]
  We produce a differentially private random feature model for privacy-preserving kernel machines.<n>We show that our method preserves privacy and derive a generalization error bound for the method.
  arXiv  Detail & Related papers  (2024-12-06T05:31:08Z)
• Benchmarking Secure Sampling Protocols for Differential Privacy [3.0325535716232404]
  Two well-known models of Differential Privacy (DP) are the central model and the local model. Recently, many studies have proposed to achieve DP with Secure Multi-party Computation (MPC) in distributed settings.
  arXiv  Detail & Related papers  (2024-09-16T19:04:47Z)
• Convergent Differential Privacy Analysis for General Federated Learning: the $f$-DP Perspective [57.35402286842029]
  Federated learning (FL) is an efficient collaborative training paradigm with a focus on local privacy. differential privacy (DP) is a classical approach to capture and ensure the reliability of private protections.
  arXiv  Detail & Related papers  (2024-08-28T08:22:21Z)
• How Private are DP-SGD Implementations? [61.19794019914523]
  We show that there can be a substantial gap between the privacy analysis when using the two types of batch sampling. Our result shows that there can be a substantial gap between the privacy analysis when using the two types of batch sampling.
  arXiv  Detail & Related papers  (2024-03-26T13:02:43Z)
• Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy [51.11280118806893]
  We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. We study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP) More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms.
  arXiv  Detail & Related papers  (2023-02-19T16:58:53Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions [49.726408540784334]
  Key question in PLD-based accounting is how to approximate any (potentially continuous) PLD with a PLD over any specified discrete support. We show that our pessimistic estimate is the best possible among all pessimistic estimates.
  arXiv  Detail & Related papers  (2022-07-10T04:25:02Z)
• Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guarantees [123.0401978870009]
  We propose Byzantine-robust federated learning protocols with nearly optimal statistical rates. We benchmark against competing protocols and show the empirical superiority of the proposed protocols. Our protocols with bucketing can be naturally combined with privacy-guaranteeing procedures to introduce security against a semi-honest server.
  arXiv  Detail & Related papers  (2022-05-24T04:03:07Z)
• One-bit Submission for Locally Private Quasi-MLE: Its Asymptotic Normality and Limitation [3.050919759387985]
  Local differential privacy(LDP) is an information-theoretic privacy definition suitable for statistical surveys that involve an untrusted data curator. The existing method to build LDP QMLE is difficult to implement for a large-scale survey system in the real world due to long waiting time, expensive communication cost, and the boundedness assumption of derivative of a log-likelihood function. We provided an alternative LDP protocol without those issues, which is potentially much easily deployable to a large-scale survey.
  arXiv  Detail & Related papers  (2022-02-15T05:04:59Z)
• Antipodes of Label Differential Privacy: PATE and ALIBI [2.2761657094500682]
  We consider the privacy-preserving machine learning (ML) setting where the trained model must satisfy differential privacy (DP) We propose two novel approaches based on, respectively, the Laplace mechanism and the PATE framework. We show how to achieve very strong privacy levels in some regimes, with our adaptation of the PATE framework.
  arXiv  Detail & Related papers  (2021-06-07T08:14:32Z)
• User-Level Privacy-Preserving Federated Learning: Analysis and Performance Optimization [77.43075255745389]
  Federated learning (FL) is capable of preserving private data from mobile terminals (MTs) while training the data into useful models. From a viewpoint of information theory, it is still possible for a curious server to infer private information from the shared models uploaded by MTs. We propose a user-level differential privacy (UDP) algorithm by adding artificial noise to the shared models before uploading them to servers.
  arXiv  Detail & Related papers  (2020-02-29T10:13:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.