# A Shuffling Framework for Local Differential Privacy

arXiv: https://arxiv.org/abs/2106.06603 · HTML: https://mlsanity.com/paper/2106.06603/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 59 references that are in the map.
- First posted on arXiv 11 Jun 2021.

## Builds on (most cited first, 17 of 17)

- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [Attribute Privacy: Framework and Mechanisms](https://mlsanity.com/paper/2009.04013/) (2020)
- [Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries](https://mlsanity.com/paper/1503.01214/) (2015)
- [Pufferfish Privacy Mechanisms for Correlated Data](https://mlsanity.com/paper/1603.03977/) (2016)
- [Separating Local & Shuffled Differential Privacy via Histograms](https://mlsanity.com/paper/1911.06879/) (2019)
- [Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies](https://mlsanity.com/paper/1312.3913/) (2013)
- [Inferential Privacy Guarantees for Differentially Private Mechanisms](https://mlsanity.com/paper/1603.01508/) (2016)
- [Profile-Based Privacy for Locally Private Computations](https://mlsanity.com/paper/1903.09084/) (2019)
- [Differential Privacy as a Causal Property](https://mlsanity.com/paper/1710.05899/) (2017)
- [Towards Extending Noiseless Privacy -- Dependent Data and More Practical Approach](https://mlsanity.com/paper/1605.07956/) (2016)

## Abstract (arXiv)

ldp deployments are vulnerable to inference attacks as an adversary can link the noisy responses to their identity and subsequently, auxiliary information using the order of the data. An alternative model, shuffle DP, prevents this by shuffling the noisy responses uniformly at random. However, this limits the data learnability -- only symmetric functions (input order agnostic) can be learned. In this paper, we strike a balance and show that systematic shuffling of the noisy responses can thwart specific inference attacks while retaining some meaningful data learnability. To this end, we propose a novel privacy guarantee, d-sigma-privacy, that captures the privacy of the order of a data sequence. d-sigma-privacy allows tuning the granularity at which the ordinal information is maintained, which formalizes the degree the resistance to inference attacks trading it off with data learnability. Additionally, we propose a novel shuffling mechanism that can achieve name-privacy and demonstrate the practicality of our mechanism via evaluation on real-world datasets.