Abstract
Recently, a number of approaches have been introduced for reporting software statistics with strong privacy guarantees, ranging from local differential privacy (LDP) to the Encode-Shuffle-Analyze (ESA) framework. While ESA formally clarifies how anonymity can amplify privacy without sacrificing utility, practitioners lack clear guidance on its deployment. This paper provides a formal treatment and prescriptive guidelines for privacy-preserving reporting with anonymity. We introduce techniques such as "attribute fragmentation" and "removal LDP" to improve privacy-utility tradeoffs. Through empirical evaluation on large-scale real-world datasets—including high-dimensional spatial data and deep learning benchmarks like MNIST and CIFAR-10—we demonstrate that the ESA framework can achieve high accuracy while maintaining robust local and central differential privacy guarantees.
Introduction: The Privacy Tug-of-War
In the field of differential privacy (DP), there is a persistent tension between utility and trust. Local DP (LDP), utilized by major technology firms, adds noise to data directly on a user's device. This model requires no trust in a central server, but the accumulated noise often destroys data utility, particularly for high-dimensional datasets. Conversely, Central DP adds noise at the server level, preserving high utility but requiring users to trust the server with their raw data.
Recent theoretical breakthroughs suggest that passing LDP reports through an anonymous shuffler—a middleman that strips metadata and mixes reports—can mathematically "amplify" privacy guarantees. This is the core of the ESA framework. However, bridging the gap between this theory and practical deployment requires addressing how data should be encoded and how complex, real-world distributions should be handled.
Methodology and Practical Primitives
We propose a simplified architecture for the ESA framework based on several key primitives designed to optimize the privacy-utility tradeoff:
- Removal LDP: We shift the mathematical definition of LDP from "replacement" (swapping a user's data) to "removal" (the absence of a user's report). This subtle shift effectively doubles the local privacy guarantee without adding further noise.
- Attribute Fragmentation: Instead of sending a single large, noisy report, a user's data is broken into individual attributes (e.g., bits of a one-hot vector). Each attribute is randomized and sent as a separate, unlinkable message to the shuffler.
- Report Fragmentation with Privacy Backstops: To prevent leakage from intercepted messages, users can send multiple randomized fragments. This maintains a strict mathematical cap (a "backstop") on total privacy loss while allowing for higher utility per fragment.
- LDP-SGD: We adapt Stochastic Gradient Descent to work within the ESA framework, enabling the training of deep learning models using shuffled, locally private gradients.
Empirical Evaluation
To prove these methods work on difficult, real-world distributions, we evaluated them against several datasets, including a "Heavy-Hitter" dataset of 200 million browser reports and high-dimensional image proxies for sensitive 2D location data.
Spatial Data Visualization
One of our primary benchmarks was a "Map" dataset consisting of 236 million points based on NYC smartphone location data. This dataset is naturally high-dimensional and serves as a perfect proxy for sensitive spatial data where visual reconstruction can easily highlight noise errors.
Using attribute fragmentation and one-hot encoding, we successfully reconstructed this complex dataset with a strong central privacy guarantee ($\epsilon_c \le 1.0$) and a reasonable local privacy backstop ($\epsilon_\infty \approx 13$).
Machine Learning Performance
The ESA framework successfully trained deep neural networks with strong central privacy and a per-epoch local privacy of $\epsilon \approx 1.9$. The models achieved accuracies of 95% on MNIST, 78% on Fashion-MNIST, and 70% on CIFAR-10, approaching state-of-the-art performance for differentially private models while providing the added benefit of local DP guarantees.
Key Insights for Practitioners
Our research yielded several surprising insights for those deploying privacy-preserving systems:
- One-Hot Encoding vs. Sketching: While many LDP deployments use complex "sketching" (hashing data into smaller buckets) to save bandwidth, we found that sketching adds massive estimation error that ruins utility under anonymity. Simple one-hot encoding, combined with attribute fragmentation, yields vastly superior results.
- Fragmentation is the Secret Weapon: Breaking data into tiny, independently shuffled pieces allows for a higher local $\epsilon$ (less noise per piece) while relying on the shuffler to achieve a very strong central $\epsilon_c$.
- Obsolescence of Crowd IDs: Earlier ESA designs suggested grouping users by data-derived traits (Crowd IDs) before shuffling. We prove that under modern shuffling math, splitting the privacy budget to protect these IDs actually hurts overall performance; it is more effective to shuffle all reports together.
Limitations and Future Work
While the results are promising, some limitations remain. The poor performance of sketch-based LDP in our tests is partly due to a lack of precise mathematical bounds for how sketching interacts with shuffling. Additionally, the central DP accounting for machine learning experiments currently relies on standard advanced composition, which may be loose. Future work could tighten these bounds using Rényi Differential Privacy to further improve the utility of private ML models.
Summary updated