Source-linked AI summary
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, Abhradeep Thakurta
TL;DR
The paper studies privacy-preserving repeated collection of evolving user statistics under local differential privacy. It develops an online monitoring algorithm and shows that anonymized, permutation-invariant LDP reports receive stronger central-DP guarantees, with implications for industrial deployments.
Problem
Repeated monitoring of sensitive, evolving user data requires privacy protection, while the benefits of anonymizing LDP reports need formal differential-privacy bounds.
Method
The paper develops an LDP continual-observation algorithm and a privacy-amplification analysis for properly anonymized, permutation-invariant collections of LDP reports.
Results
Anonymity yields much stronger central-DP guarantees for sufficiently private LDP reports, while the online algorithm has privacy cost polylogarithmic in each user’s number of value changes.
Takeaways & Limitations
Anonymized industrial LDP deployments may provide stronger privacy guarantees than previously accounted for, and anonymity can substantially lower worst-case per-user central-DP cost.
Takeaways & Limitations
Stronger bounds for general local randomizers when ε0 > 1 remain an open direction, and extending relevant lower bounds to approximate differential privacy is unresolved.
Abstract
from arXiv · showhide
Sensitive statistics are often collected across sets of users, with repeated collection of reports done over time. For example, trends in users' private preferences or software usage may be monitored via such reports. We study the collection of such statistics in the local differential privacy (LDP) model, and describe an algorithm whose privacy cost is polylogarithmic in the number of changes to a user's value. More fundamentally---by building on anonymity of the users' reports---we also demonstrate how the privacy cost of our LDP algorithm can actually be much lower when viewed in the central model of differential privacy. We show, via a new and general privacy amplification technique, that any permutation-invariant algorithm satisfying $\varepsilon$-local differential privacy will satisfy $(O(\varepsilon \sqrt{\log(1/δ)/n}), δ)$-central differential privacy. By this, we explain how the high noise and $\sqrt{n}$ overhead of LDP protocols is a consequence of them being significantly more private in the central model. As a practical corollary, our results imply that several LDP-based industrial deployments may have much lower privacy cost than their advertised $\varepsilon$ would indicate---at least if reports are anonymized.
1 Introduction
The paper addresses privacy erosion in repeated, correlated LDP monitoring and formalizes how anonymity can strengthen privacy guarantees. It presents longitudinal monitoring with polylogarithmic privacy cost and amplification by shuffling for stronger central-DP bounds.
- 1 Introduction: Repeated and correlated reports can dramatically reduce a user’s effective LDP privacy, while defenses against this erosion can lower accuracy.Monitoring may involve multiple sensitive, correlated attributes collected over time.
- 1 Introduction: Anonymity assumptions require reports to be anonymous at each timestep and unlinkable over time, allowing reports to “hide in the crowd.”The ESA architecture shuffles reports and removes identifying metadata to prevent linking reports to users.
- 1 Introduction: The paper introduces an online LDP monitoring algorithm whose total privacy cost is polylogarithmic in each user’s number of value changes.It supports repeated reports across timesteps for identical, correlated, or independently drawn values.
- 1 Introduction: Random shuffling amplifies privacy: permutation-invariant ε-LDP algorithms obtain stronger central-DP guarantees when reports are anonymized.The amplification technique accounts for uncertainty that prevents reports from one user being singled out or linked together.
- 1 Introduction: For d periods with at most k changes per user, all d frequency statistics can be estimated with error at most O((log d)^2k√n/ε) under LDP.The assumption is natural for software adoption and international travel, and the protocol extends to multi-valued data and strings.
2 Technical Preliminaries and Background
This section defines differential privacy and the distribution-level notation used throughout, then states standard properties and composition results. It also recalls privacy amplification by sampling.
- Differential privacy: Differential privacy compares algorithm outputs on adjacent datasets, typically datasets differing in one individual’s contribution.The definition allows an additive δ relaxation, and privacy may be stated at a specific index.
- Composition: Advanced composition combines k adaptively chosen (ε, δ)-DP algorithms with ε′ = ε√(2k log(1/δ′)) + kε(exp(ε) − 1) and failure probability kδ + δ′.
- Distribution notation: For distributions, (ε, δ)-DP closeness requires the corresponding probability inequalities for every measurable event.
- DP properties: DP closeness is monotone in both ε and δ, satisfies a triangle inequality, and is preserved under mixtures.
- Privacy amplification: Sampling amplification bounds a mixture’s privacy by ε′ = log(q(e^ε − 1) + 1) ≤ q(e^ε − 1) with failure probability qδ.
3 Locally Private Protocol for Longitudinal Data
The protocol adapts tree-based continual-observation aggregation to local differential privacy for longitudinal data with at most k user-state changes. Clients privatize sampled tree information, while the server reconstructs running counts and obtains privacy and utility guarantees.
- Assumptions: The protocol’s error depends only polylogarithmically on the time horizon’s upper bound under the stated horizon and bounded-change assumptions.
- Protocol design: The protocol pushes a binary tree of counters to each client, and the server aggregates the resulting locally private reports.Each change affects only log2 d tree nodes, adapting continual-observation aggregation to the local setting.
- Problem setup: The task estimates each time period’s population running count from n users’ boolean states over a horizon d, assuming each user changes state at most k times.The protocol represents state changes as vectors in {−1, 0, 1}^d with at most k nonzero entries.
- Client algorithm: Each client samples one change and one tree level, applies randomized response to selected nodes, and reports the privatized value with its timing information.Changes other than the sampled change are ignored, reducing the data-dependent contribution being privatized.
- Server algorithm: The server forms an aggregate tree and estimates each marginal by summing a disjoint tree cover of [1, t], then correcting for client-side sampling.
- Privacy: The sequence of d client outputs satisfies ε-local differential privacy.The privacy proof separately analyzes randomized node values and report timing; timing depends on data-independent level sampling.
- Utility: With ε ≤1 and probability at least 2/3, the server outputs estimates satisfying the utility bound stated in Theorem 6.
4 Privacy Amplification via Shuffling
The paper shows that shuffling can amplify the central-model privacy of locally private reports, improving guarantees by roughly a square-root factor in the number of reports. It develops this result through a reduction involving a single swapped element and applies it to anonymized reports and lower bounds for local protocols.
- Amplification by shuffling: ˜Θ(√n) amplification can yield much stronger central DP guarantees than conservative local-model analysis suggests.The improvement comes from applying a random permutation to reports or data elements under the paper’s supported conditions.
- Amplification by shuffling: The generalized local algorithm sequentially selects local randomizers using previous reports as auxiliary inputs.This formulation allows the amplification theorem to cover adaptive sequences of local randomizers.
- Amplification by shuffling: Theorem 7 analyzes uniformly permuted data elements and establishes central-model (ε, δ)-DP for the resulting sequence of local outputs.The theorem applies when each local randomizer is ε0-differentially private for every allowed auxiliary-input value.
- Proof strategy: The proof reduces shuffled analysis to a one-swap algorithm, bounds the swapped element’s influence in each output distribution, and applies advanced composition.Each output distribution is decomposed into a component independent of the protected element and a component produced by its local randomizer.
- Shuffling after local randomization: The amplification requires careful anonymity: shuffling before local randomization may require trusting a shuffler, while identifiable report attributes can eliminate gains after randomization.If reports from large groups are indistinguishable because they use the same local randomizer, response shuffling can provide amplification proportional to the square root of that group’s size.
- Lower bounds for local DP protocols: The result also converts central-model error lower bounds into local-model lower bounds with an Ω(√n) privacy-parameter penalty.The reverse use of Theorem 7 applies to a broad class of local protocols covered by the amplification result.
5 Discussion and Future Work
Anonymity can substantially lower worst-case per-user privacy cost in the central model, but the analysis leaves important gaps relative to practical deployments. In particular, it excludes dynamic populations, traffic-channel effects, and user-level information fragmentation.
- Discussion: Anonymity can dramatically lower the worst-case, per-user privacy cost in the central differential privacy model.The reduction follows from accounting for uncertainty that prevents reports from being singled out or linked.
- Discussion: Industrial LDP deployments may provide stronger privacy guarantees than previously accounted for because telemetry reports are commonly anonymized.The result was motivated by the ESA architecture and PROCHLO implementation.
- Future Work: The formalization assumes a static user population, although practical deployments do not necessarily have one.This creates a gap between the analysis and real-world mechanisms such as ESA.
- Future Work: The analysis assumes most users report at every timestep and omits privacy implications of timing and traffic channels.ESA mitigates traffic channels through batching, randomized thresholding, and elision, but those benefits are not included.
- Future Work: The analysis does not consider users sending multiple anonymous, unlinkable reports for carefully constructed fragments of their sensitive information.The privacy implications of disjoint, overlapping, or equivalent fragments remain formally unresolved in general.