Source-linked AI summary
Local Differential Privacy and Its Applications: A Comprehensive Survey
Mengmeng Yang, Lingjuan Lyu, Jun Zhao, Tianqing Zhu, Kwok-Yan Lam
TL;DR
Private data collection requires protection without relying on a trusted curator. This survey organizes LDP research across query answering, private learning, applications, and deployment, finding a broad but still developing field with practical constraints and open potential.
Problem
User data are increasingly collected for analysis while remaining private and sensitive, creating a need for privacy preservation without relying solely on trusted data curators.
Method
The survey structures LDP research into statistical queries and private learning, reviews methods and trade-offs, and examines deployment, applications, gaps, and future directions.
Results
The survey synthesizes methods for frequency, mean, and range queries, private learning categories, practical deployment, and applications across multiple domains.
Takeaways & Limitations
LDP provides stronger protection by perturbing data locally, while current practice remains concentrated on count and average functions and broader applications remain open.
Takeaways & Limitations
Practical deployment is limited by uncertainty in selecting the privacy level and by privacy loss from continuous data collection.
Abstract
from arXiv · showhide
With the fast development of Information Technology, a tremendous amount of data have been generated and collected for research and analysis purposes. As an increasing number of users are growing concerned about their personal information, privacy preservation has become an urgent problem to be solved and has attracted significant attention. Local differential privacy (LDP), as a strong privacy tool, has been widely deployed in the real world in recent years. It breaks the shackles of the trusted third party, and allows users to perturb their data locally, thus providing much stronger privacy protection. This survey provides a comprehensive and structured overview of the local differential privacy technology. We summarise and analyze state-of-the-art research in LDP and compare a range of methods in the context of answering a variety of queries and training different machine learning models. We discuss the practical deployment of local differential privacy and explore its application in various domains. Furthermore, we point out several research gaps, and discuss promising future research directions.
1 INTRODUCTION
The survey motivates LDP as a response to the difficulty of trusting data curators and reviews its technologies, applications, deployment, and research directions. It organizes LDP around statistical queries and private machine learning.
- Motivation and approach: Traditional centralized differential privacy assumes a trusted curator that collects original data before releasing perturbed aggregates.The survey contrasts this assumption with LDP’s local perturbation framework.
- Motivation and approach: LDP perturbs user data before it leaves the device, so curators receive perturbed rather than raw data.This prevents privacy disclosure to an untrusted curator and reduces the burden of securing raw data.
- Challenges and scope: LDP adds substantial noise and gives each user only a local view of the data, reducing utility and limiting application scope.These challenges help explain why LDP has been less studied than centralized differential privacy.
- Survey scope: The survey identifies statistical queries and private learning as two research directions based on how perturbation mechanisms depend on the task.It covers queries such as frequency, mean, and range; models such as linear regression and SVM; and applications including federated learning and location privacy.
- Survey scope: The paper presents a structured review of preliminaries, query and machine-learning techniques, applications, research gaps, directions, and conclusions.The sections proceed from preliminaries through techniques and applications to research gaps and future directions.
2 PRELIMINARIES
The preliminaries define LDP as local randomized perturbation followed by aggregation and estimation, while introducing randomized-response, noise-based, composition, and multi-stage mechanisms. These mechanisms trade privacy protection for statistical accuracy and rely on aggregation across many participants.
- LDP framework: LDP hides a user’s true value by perturbing it locally, after which an aggregator estimates the underlying statistics.The mechanism is a randomized algorithm that outputs a perturbed value while aiming to preserve statistical accuracy.
- Randomized response: Randomized response reports a binary truth with probability e^ϵ/(e^ϵ+1) and the opposite value with probability 1/(e^ϵ+1).Generalized randomized response extends the approach from binary attributes to a domain with d possible values.
- Noise mechanisms: Laplace and Gaussian mechanisms add noise to continuous numerical data, with clipping or truncation used to bound sensitivity.The mechanisms are defined for functions over datasets, and sensitivity is explicitly identified as a relevant parameter.
- Composition: Sequential composition combines m independent mechanisms by allocating privacy budget across them, yielding an overall ϵ-local privacy guarantee.The aggregator can apply a series of mechanisms while distributing the privacy budget among them.
- Data aggregation under LDP: Most LDP data aggregation follows four stages: encoding, perturbation, aggregation, and estimation.Encoding adapts values to the mechanism; estimation targets unbiased results and may use post-processing to improve accuracy.
- Data aggregation under LDP: Because an individual perturbed value is randomized, LDP applications depend on aggregates such as averages across many participants.The aggregation process is illustrated as the common workflow for LDP algorithms.
3 STATISTICAL QUERY WITH LDP
Statistical queries under LDP primarily address frequency, mean, and range, with frequency estimation receiving the most mature treatment. Methods trade off dimensionality, communication cost, privacy, and statistical accuracy, while set-valued mining retains open challenges around candidate-set reduction and encoding.
- Statistical queries under LDP mainly focus on frequency, mean, and range, with perturbation mechanisms tailored to the query type.
- Frequency estimation: Frequency estimation targets discrete data and includes general frequency estimation, heavy hitters identification, set-value frequency estimation, and joint distribution estimation.
- Frequency estimation: Frequency oracles pair user-side perturbation with aggregator-side estimation to estimate item frequencies and support more complicated queries and applications.
- Frequency estimation: RR and GRR suit lower-dimensional data, whereas OUE reduces statistical variance for high-dimensional data at higher communication cost; these methods also form building blocks for others.
- Frequency estimation: Hashing reduces communication cost and statistical variance for large domains but introduces collisions, motivating Bloom Filter, Count Mean Sketch, and related methods.
- Frequency estimation: Subset selection performs well in the intermediate privacy region, log 2 ≤ϵ ≤log(d −1), compared with GRR, but has relatively high communication cost when ϵ is small.
- Set-value data: Frequency estimation remains challenged by high-dimensional data and communication constraints, while frequent itemset mining additionally requires reducing candidate-set size and improving input encoding.
1 V ar is the variance of a single cell in the full contingency table
The survey reviews LDP methods for joint distributions, numerical means, key-value statistics, and range queries, emphasizing the trade-offs among accuracy, variance, computation, and communication. Across these tasks, methods address scalability or utility through query-specific perturbation, sampling, hierarchical decomposition, or transformed representations.
- Joint distribution estimation: Lasso regression-based estimation improves efficiency but does not improve estimation accuracy, while its predictor matrix includes all attribute combinations.For d-dimensional data, the matrix size grows with the product of the Bloom-filter lengths of the attributes.
- Joint distribution estimation: Fourier-transform methods save communication cost and reduce variance for small k, but require O(d^k) coefficients when k is large and support only binary data.The number of k-way coefficients must be predefined.
- Joint distribution estimation: Subset marginal selection can release any-way marginal tables without calculating the full marginal and can handle non-binary attributes, but introduces noise, sampling, and construction errors.Sampling error arises because each estimate uses only the users assigned to that marginal.
- General mean value estimation: For numerical means, extreme-value perturbation provides unbiased estimation, while distribution perturbation models outputs continuously over an expanded domain.The survey distinguishes extreme-value and distribution perturbation as the two main randomization types for general mean estimation.
- General mean value estimation: Piecewise Mechanism achieves much smaller variance than Duchi et al.’s solution, especially when epsilon is large; Harmony reduces communication cost while reaching similar variance.Harmony reports one randomly selected attribute instead of all attribute values.
- Key-value and range query estimation: Key-value statistics must preserve key-value correlation and generate fake values with minimal impact, while hierarchical range methods bound query variance by a polylogarithm of range length.Range queries can use at most 2h coefficients when summing counts across decomposed intervals.
4 PRIVATE LEARNING WITH LDP
Private learning with LDP incorporates local perturbation into supervised, unsupervised, and optimization-based learning, while addressing dimensionality, accuracy, and privacy-consumption challenges. The survey organizes methods by learning task and discusses ERM protocols, perturbation strategies, and remaining limitations.
- Learning paradigms: Private learning with LDP trains machine-learning models by incorporating perturbation mechanisms into supervised or unsupervised algorithms.The survey also considers learning as an optimization problem.
- Supervised learning: Naive Bayes under LDP addresses high dimensionality by partitioning users into groups that report attribute-label pairs.The methods also aim to preserve correlations between attributes and labels.
- Supervised learning: Partitioning users can reduce statistical accuracy because groups sharing the same attribute-label pair become small as dimensionality increases.The survey also notes that closely related methods may lack demonstrated advantages over one another.
- Unsupervised learning: LDP clustering requires users to report perturbed records and assigned centers iteratively, creating noise and privacy-consumption challenges.Methods use hashing, reduced interaction rounds, and perturbation of the closest center to improve privacy or efficiency.
- Unsupervised learning: Small cluster populations produce high-variance center estimates, while reducing privacy consumption across distributed clustering rounds remains unresolved.The survey identifies both population size and repeated interaction as continuing accuracy or privacy concerns.
- Private ERM: ERM selects a hypothesis parameter minimizing empirical risk, with private utility evaluated through risk bounds or sample complexity.Convex loss assumptions make ERM a convex optimization problem; local protocols may be interactive or non-interactive and use input, gradient, or objective perturbation.
- Private ERM: Local ERM research covers interactive and non-interactive convex optimization, including sparsity-constrained problems and high-dimensional settings.Reported analyses include bounds depending logarithmically on d and alternatives based on Gaussian width, loss functions, or log d.
5.1 Applications in practice
LDP has been deployed in browsers, operating systems, mobile suggestions, and database systems through mechanisms such as randomized response, memoization, sketches, and Laplace noise. Practical deployment remains concentrated in simple statistics and faces unresolved privacy–utility and continual-collection issues.
- Browser deployment: Google deployed RAPPOR in Chrome as the first internet-scale LDP deployment, using hashed bit vectors, randomized response, Bloom filters, and cohorts.Bloom filters and cohorts add redundancy to address collisions and improve the false positive rate.
- Continual collection: Memoization provides longitudinal privacy when user values remain unchanged or change in an uncorrelated fashion.Its protection is therefore conditional on the temporal behavior of the reported value.
- Operating-system deployment: Apple uses Count Mean Sketch and Hadamard transformation to encode variable-sized activity data while sending only one randomly sampled bit.The approach was deployed in macOS Sierra and iOS 10 for QuickType and emoji suggestions.
- Operating-system deployment: Microsoft’s Windows 10 deployment combines RAPPOR-like LDP with memoization and α-point rounding for continual app-usage collection.The rounding mechanism allows slight data changes within a discretized segment to share a memorized response.
- Database deployment: SAP HANA applies local Laplace noise to database records before queries and uses seeded reproducibility and privacy-parameter selection.The system recalculates privacy views to detect changes that could violate the current privacy definition.
- Deployment challenges: Current practical LDP deployment is mainly limited to count and average functions, with privacy-level selection and continuous collection remaining difficult.The survey gives a general ε range of [0.1 ∼10] and notes that sequential composition weakens privacy over repeated queries.
5.2 Applications in various domain
LDP applications span federated and reinforcement learning, graph publication, location statistics, and recommendation systems. Across these domains, the survey emphasizes stronger privacy alongside challenges in accuracy, communication, structural information, and application scope.
- Federated learning: Federated learning combines local training with server-side parameter aggregation, but differential attacks and model inversion can expose participation or private data.LDP-based methods add calibrated noise, with some work extending protection from records to users.
- Federated learning: Strong user-level privacy in federated learning can show no significant accuracy decrease with a large enough dataset, but may require more iterations and resources.Communication efficiency and mobile-device power limitations remain practical concerns.
- Reinforcement learning: LDP reinforcement-learning methods perturb distributed gradients or rewards using Laplace noise, random projection, or Bernoulli responses.The survey describes applications to A3C, multi-armed bandits, and upper-confidence-bound algorithms.
- Reinforcement learning: Reinforcement-learning applications of LDP remain at an early stage, requiring further study of their functionality and effects.The survey identifies this as a domain with substantial unresolved research needs.
- Graph publication: Graph publication under LDP is limited by simple statistics and each user’s local view, making edge-level and global structural information difficult to obtain.User grouping and node-to-group connectivity are proposed to extract more structure from local reports.
- Location privacy: Location-data LDP mainly supports population statistics, while nearby recommendations and spatial task assignments remain underexplored.Tree-based methods use noisy counts and user-selected safe regions to construct more detailed location representations.
- Recommendation systems: Recommendation systems face sparse ratings and privacy leakage from continual observation, while randomized dimensionality-reduction methods may improve recommendation accuracy.The survey cites Johnson–Lindenstrauss transformation as an example that outperformed a centralized non-privacy method in one study.
5.3 Summary
The survey concludes that LDP research remains concentrated on simple statistics, while applications increasingly extend to preferences, crowdsourcing, PCA, low-power systems, deep inference, NLP, and hypothesis testing. It identifies substantial room for future expansion.
- Current scope: LDP research mainly focuses on frequency estimation, mean computation, and applications based on these simple statistics.The survey attributes limited study partly to intrinsic constraints of the local model.
- Emerging applications: Additional work studies preference ranking, sparse-crowdsourcing truth inference, private PCA, ultra-low-power systems, hidden representations, NLP, and hypothesis testing.These examples broaden the application areas beyond basic statistical queries.
- Future directions: LDP retains substantial unexplored potential, and the surveyed research provides a starting point for extending its future applications.The conclusion frames expansion of the application landscape as an open direction.
6 RESEARCH GAPS AND RESEARCH DIRECTION
The survey identifies unresolved LDP challenges involving utility, query flexibility, changing data, privacy relaxation, and small populations, then outlines research directions addressing these constraints.
- Research gaps: LDP substantially reduces statistical accuracy, especially for high-dimensional data and statistics spanning multiple attributes.Existing solutions commonly use partitioning, hashing, matrix transformation, or attribute sampling, but sampling reduces utility.
- Research gaps: LDP mechanisms are usually designed for predefined queries, limiting accurate estimation when aggregators need multiple query types.The survey identifies query-independent accurate estimation as a major challenge under local protection.
- Research gaps: Continuous statistics remain insufficiently studied under LDP because memoization does not work well for frequent or substantial data changes.The survey notes that users’ data and corresponding statistics may need periodic recomputation.
- Research directions: Privacy relaxations such as block-structured and metric-based LDP aim to provide different protection levels for items with different sensitivities.The survey calls for definitions, randomized algorithms, and sample-complexity analyses covering more data types and scenarios.
- Privacy amplification: Shuffling can amplify privacy to (ϵa, δ)-DP with ϵa = O(ϵb/√n), but collusion between the shuffler and server can eliminate this advantage.Distributed differential privacy and cryptographic approaches are discussed as possible responses to this limitation.
- Solutions for small population: ϵ-local differential privacy reduces effective sample size from n to 4ϵ^2n, making small-population applications difficult.Hybrid privacy strategies may reduce noise, but can increase computational and communication costs or involve truthful reporting by some users.
7 CONCLUSION
The paper surveys LDP as a privacy model that perturbs data before it leaves users’ devices, covering its literature, methods, applications, deployment, and future directions. It concludes that LDP remains incomplete and offers substantial potential for further research.
- Conclusion: LDP protects privacy without requiring the data curator to be trusted by perturbing data before it leaves users’ devices.This distinguishes localized protection from the trusted-curator assumption in centralized differential privacy.
- Conclusion: The survey organizes LDP research into statistical queries and private learning, covering frequency, mean, range, and multiple learning categories.Private learning is classified into supervised learning, unsupervised learning, and private learning in ERM.
- Conclusion: The paper compares existing query-answering methods, analyzes private-learning research, and discusses applications, practical deployment, and future research directions.Its coverage is intended to support further research based on the current state of LDP.
- Conclusion: LDP research is incomplete, with substantial unknown potential, and the survey is intended as a starting point for exploring future challenges.The conclusion characterizes the field as emerging and presents the literature overview as an entry point for new work.