Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation

Abstract

Recently, a number of approaches and techniques have been introduced for reporting software statistics with strong privacy guarantees. These range from abstract algorithms to comprehensive systems with varying assumptions and built upon local differential privacy mechanisms and anonymity. Based on the Encode-Shuffle-Analyze (ESA) framework, notable results formally clarified large improvements in privacy guarantees without loss of utility by making reports anonymous. However, these results either comprise of systems with seemingly disparate mechanisms and attack models, or formal statements with little guidance to practitioners. Addressing this, we provide a formal treatment and offer prescriptive guidelines for privacy-preserving reporting with anonymity. We revisit the ESA framework with a simple, abstract model of attackers as well as assumptions covering it and other proposed systems of anonymity. In light of new formal privacy bounds, we examine the limitations of sketch-based encodings and ESA mechanisms such as data-dependent crowds. We also demonstrate how the ESA notion of fragmentation (reporting data aspects in separate, unlinkable messages) improves privacy/utility tradeoffs both in terms of local and central differential-privacy guarantees. Finally, to help practitioners understand the applicability and limitations of privacy-preserving reporting, we report on a large number of empirical experiments. We use real-world datasets with heavy-tailed or near-flat distributions, which pose the greatest difficulty for our techniques; in particular, we focus on data drawn from images that can be easily visualized in a way that highlights reconstruction errors. Showing the promise of the approach, and of independent interest, we also report on experiments using anonymous, privacy-preserving reporting to train high-accuracy deep neural networks on standard tasks---MNIST and CIFAR-10.

References in corpus (7)

• Deep Learning with Differential Privacy
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12
• Prio: Private, Robust, and Scalable Computation of Aggregate Statistics
• Privacy Accounting and Quality Control in the Sage Differentially Private ML Platform
• Differentially Private Summation with Multi-Message Shuffling
• That which we call private

Cited by in corpus (23)

• A Field Guide to Federated Optimization
• How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
• Federated Learning with Buffered Asynchronous Aggregation
• Breaking the Communication-Privacy-Accuracy Trilemma
• Improving the utility of locally differentially private protocols for longitudinal and multidimensional frequency estimates
• Random Sampling Plus Fake Data: Multidimensional Frequency Estimates With Local Differential Privacy
• On the Power of Multiple Anonymous Messages
• Practical and Private (Deep) Learning without Sampling or Shuffling
• Layer-wise Characterization of Latent Information Leakage in Federated Learning
• Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
• SoK: Machine Learning Governance
• The Privacy Funnel from the viewpoint of Local Differential Privacy
• Data Sanitisation Protocols for the Privacy Funnel with Differential Privacy Guarantees
• Improved Differentially Private Decentralized Source Separation for fMRI Data
• Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning
• Lossless Compression of Efficient Private Local Randomizers
• Differential privacy with partial knowledge
• On Large-Cohort Training for Federated Learning
• Local Differential Privacy for Regret Minimization in Reinforcement Learning
• Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses
• Improving Utility and Security of the Shuffler-based Differential Privacy
• Privacy-Preserving Bandits
• Flexible Accuracy for Differential Privacy