Extremal Mechanisms for Local Differential Privacy

Abstract

Local differential privacy has recently surfaced as a strong measure of privacy in contexts where personal information remains private even from data analysts. Working in a setting where both the data providers and data analysts want to maximize the utility of statistical analyses performed on the released data, we study the fundamental trade-off between local differential privacy and utility. This trade-off is formulated as a constrained optimization problem: maximize utility subject to local differential privacy constraints. We introduce a combinatorial family of extremal privatization mechanisms, which we call staircase mechanisms, and show that it contains the optimal privatization mechanisms for a broad class of information theoretic utilities such as mutual information and $f$-divergences. We further prove that for any utility function and any privacy level, solving the privacy-utility maximization problem is equivalent to solving a finite-dimensional linear program, the outcome of which is the optimal staircase mechanism. However, solving this linear program can be computationally expensive since it has a number of variables that is exponential in the size of the alphabet the data lives in. To account for this, we show that two simple privatization mechanisms, the binary and randomized response mechanisms, are universally optimal in the low and high privacy regimes, and well approximate the intermediate regime.

52 pages, 10 figures in JMLR 2015

References in corpus (4)

• Privacy and Statistical Risk: Formalisms and Minimax Bounds
• Convergence Rates for Differentially Private Statistical Estimation
• The Optimal Mechanism in Differential Privacy: Multidimensional Setting
• Differentially Private Multi-party Computation: Optimality of Non-Interactive Randomized Response

Cited by in corpus (53)

• HybridAlpha: An Efficient Approach for Privacy-Preserving Federated Learning
• LoPub: High-Dimensional Crowdsourced Data Publication with Local Differential Privacy
• Privacy Preserving Face Recognition Utilizing Differential Privacy
• From Distributed Machine Learning To Federated Learning: In The View Of Data Privacy And Security
• A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis
• LDP-IDS: Local Differential Privacy for Infinite Data Streams
• Efficient Data Perturbation for Privacy Preserving and Accurate Data Stream Mining
• An Efficient and Scalable Privacy Preserving Algorithm for Big Data and Data Streams
• Local Differential Privacy and Its Applications: A Comprehensive Survey
• Towards Communication-efficient and Attack-Resistant Federated Edge Learning for Industrial Internet of Things
• Collecting and Analyzing Multidimensional Data with Local Differential Privacy
• Socially Responsible AI Algorithms: Issues, Purposes, and Challenges
• Privacy-Utility Tradeoffs in Routing Cryptocurrency over Payment Channel Networks
• Practical Vertical Federated Learning with Unsupervised Representation Learning
• Fair Learning with Private Demographic Data
• BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model
• Permute-and-Flip: A new mechanism for differentially private selection
• SPEED: Secure, PrivatE, and Efficient Deep learning
• On the Lift, Related Privacy Measures, and Applications to Privacy-Utility Tradeoffs
• PPaaS: Privacy Preservation as a Service
• Conditional Analysis for Key-Value Data with Local Differential Privacy
• Secure and Utility-Aware Data Collection with Condensed Local Differential Privacy
• Development and Analysis of Deterministic Privacy-Preserving Policies Using Non-Stochastic Information Theory
• Information-theoretic metrics for Local Differential Privacy protocols
• A Federated Learning Framework for Non-Intrusive Load Monitoring
• Federated Heavy Hitters Discovery with Differential Privacy
• Locally Differentially Private Naive Bayes Classification
• Distributed Clustering in the Anonymized Space with Local Differential Privacy
• Privacy-Preserving News Recommendation Model Learning
• Input Perturbation: A New Paradigm between Central and Local Differential Privacy
• FedSel: Federated SGD under Local Differential Privacy with Top-k Dimension Selection
• Aggregating Votes with Local Differential Privacy: Usefulness, Soundness vs. Indistinguishability
• Data Poisoning Attacks to Local Differential Privacy Protocols
• Context-Aware Local Differential Privacy
• Data Sanitisation Protocols for the Privacy Funnel with Differential Privacy Guarantees
• The Privacy Funnel from the viewpoint of Local Differential Privacy
• Minimax Rates of Estimating Approximate Differential Privacy
• Practical Privacy Preserving POI Recommendation
• Answering Count Queries for Genomic Data with Perfect Privacy
• Context-aware Data Aggregation with Localized Information Privacy
• Local Information Privacy and Its Application to Privacy-Preserving Data Aggregation
• Local Differential Privacy in Decentralized Optimization
• Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming
• Locally private online change point detection
• BiSample: Bidirectional Sampling for Handling Missing Data with Local Differential Privacy
• Information-Theoretic Privacy with General Distortion Constraints
• Privacy-Preserving Distributed Processing: Metrics, Bounds, and Algorithms
• Differential Privacy in Blockchain Technology: A Futuristic Approach
• Preventing Manipulation Attack in Local Differential Privacy using Verifiable Randomization Mechanism
• Achieving Dalenius' Goal of Data Privacy with Practical Assumptions
• Improving Frequency Estimation under Local Differential Privacy
• Differentially Private Multivariate Statistics with an Application to Contingency Table Analysis
• Privacy with Estimation Guarantees