Research map / Federated learning and privacy / Differential privacy
Local Pan-privacy for Federated Analytics
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces local pan-privacy for federated telemetry, proves an information-theoretic lower bound showing it is costly for counting devices with events, and gives computationally private protocols using rerandomizable public-key encryption (single- and two-server).
Problem
Federated telemetry collection must keep event occurrences on a device hidden even from an on-device intruder who sees internal state repeatedly (local pan-privacy), while still allowing accurate aggregate statistics.
Approach
Define local pan-privacy under repeated unannounced on-device intrusions; show information-theoretic version forces sqrt(T) extra error for CountNonZero; achieve computational version by keeping on-device state as rerandomizable encryptions (and secret shares in the two-server model), and show public-key encryption is necessary.
Key results
- Information-theoretic local pan-privacy for CountNonZero forces additive error Omega(sqrt(nTe^eps)/(e^eps-1)) versus O(sqrt(n)) for local DP, a sqrt(T) gap when events occur at most once per device.
- Single-server rerandomizable-encryption protocol achieves computational 0-local pan-privacy for CountNonZero and histograms with error matching randomized-response bounds (O(sqrt(n)) local DP; O(sqrt(log(1/delta))/eps) aggregator DP).
- Public-key encryption is shown necessary: an accurate computationally locally pan-private CountNonZero algorithm implies a public-key encryption scheme.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require information-theoretic local pan-privacy instead of local differential privacy | CountNonZero · CountNonZero | additive error: Ω(√n) -> Ω(√nT) | Hurt |
| Use rerandomizable public-key encryption to keep device state encrypted | CountNonZero · CountNonZero | expected error | No clear effect |
| Use encrypted histogram counters with rerandomization | Histogram algorithm · Histogram of event counts | expected error per bucket count | No clear effect |
| Use homomorphic encryption and discrete Gaussian noise rather than deriving the mean from histogram estimates | Mean event count algorithm · Mean event count per device | error scaling: O(k^{\frac 3 2}) -> O(k) | Helped |
Surprising findings
- Information-theoretic local pan-privacy is incompatible with accurate telemetry: error must grow by sqrt(T) over local DP.
- Computational local pan-privacy can be achieved with no utility loss relative to non-pan-private algorithms, using only standard public-key primitives.
Limitations
- Lower bound and conjecture (Omega(T) gap with many 1s) are not fully resolved; the general case is open.
- Two-server model with collusion of one server needs non-interactive zero-knowledge proofs; efficient proofs for other predicates are open.
Experimental setup
Metrics: additive error total variation distance privacy guarantee (epsilon, delta)
Baselines: randomized response without pan-privacy Laplace mechanism local DP RAPPOR
Builds on: pan-privacy Prio randomized response RAPPOR computational differential privacy
Closest papers by meaning
- Collecting Telemetry Data Privately (NeurIPS 2017 · similarity 0.83)
- Mitigating the Privacy–Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy (NeurIPS 2025 · similarity 0.81)
- Distributed Differentially Private Data Analytics via Secure Sketching (ICML 2025 · similarity 0.81)
- Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systems (ICML 2024 · similarity 0.80)
- Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups (NeurIPS 2024 · similarity 0.80)
- Monitoring Violations of Differential Privacy over Time (NeurIPS 2026 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.