Separating Local & Shuffled Differential Privacy via Histograms
Not on the map. Why?
Abstract (arXiv)
Recent work in differential privacy has highlighted the shuffled model as a promising avenue to compute accurate statistics while keeping raw data in users' hands. We present a protocol in this model that estimates histograms with error independent of the domain size. This implies an arbitrarily large gap in sample complexity between the shuffled and local models. On the other hand, the models are equivalent when we impose the constraints of pure differential privacy and single-message randomizers.
Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). First posted on arXiv 15 Nov 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 8; 2022: 5; 2023: 1; 2024: 0; 2025: 2.
16 papers.
Sort:
- 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 128
- 2022The Fundamental Price of Secure Aggregation in Differentially Private Federated Learningcited by 39
- 2022Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacycited by 29
- 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimationcited by 22
- 2021Locally Private k-Means in One Roundcited by 19
- 2021Shuffle Private Stochastic Convex Optimizationcited by 17
- 2021On the Renyi Differential Privacy of the Shuffle Modelcited by 16
- 2021Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregationcited by 10
- 2021User-Level Private Learning via Correlated Samplingcited by 9
- 2022Network Shuffling: Privacy Amplification via Random Walkscited by 6
- 2022Algorithms with More Granular Differential Privacy Guaranteescited by 4
- 2022FedPerm: Private and Robust Federated Learning by Parameter Permutationcited by 3
4 more
- 2025Learning from End User Data with Shuffled Differential Privacy over Kernel Densitiescited by 3
- 2021The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Modelcited by 1
- 2025How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computationscited by 1
- 2021A Shuffling Framework for Local Differential Privacycited by 0
- 2025How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computations2 Jul 2025
- 2025Learning from End User Data with Shuffled Differential Privacy over Kernel Densities19 Feb 2025
- 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation4 Apr 2023
- 2022Algorithms with More Granular Differential Privacy Guarantees8 Sep 2022
- 2022FedPerm: Private and Robust Federated Learning by Parameter Permutation16 Aug 2022
- 2022Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy9 Aug 2022
- 2022Network Shuffling: Privacy Amplification via Random Walks8 Apr 2022
- 2022The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning7 Mar 2022
- 2021Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation3 Nov 2021
- 2021User-Level Private Learning via Correlated Sampling21 Oct 2021
- 2021Shuffle Private Stochastic Convex Optimization17 Jun 2021
- 2021A Shuffling Framework for Local Differential Privacy11 Jun 2021
4 more
- 2021On the Renyi Differential Privacy of the Shuffle Model11 May 2021
- 2021Locally Private k-Means in One Round20 Apr 2021
- 2021The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model29 Mar 2021
- 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation12 Feb 2021
- 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 128
- 2022The Fundamental Price of Secure Aggregation in Differentially Private Federated Learningcited by 39
- 2022Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacycited by 29
- 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimationcited by 22
- 2021Locally Private k-Means in One Roundcited by 19
- 2021Shuffle Private Stochastic Convex Optimizationcited by 17
- 2021On the Renyi Differential Privacy of the Shuffle Modelcited by 16
- 2021Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregationcited by 10
- 2021User-Level Private Learning via Correlated Samplingcited by 9
- 2022Network Shuffling: Privacy Amplification via Random Walkscited by 6
- 2022Algorithms with More Granular Differential Privacy Guaranteescited by 4
- 2022FedPerm: Private and Robust Federated Learning by Parameter Permutationcited by 3
12 most cited of 16 All 16 (JSON)
- 2025How to Securely Shuffle? A survey about Secure Shufflers for privacy-preserving computations2 Jul 2025
- 2025Learning from End User Data with Shuffled Differential Privacy over Kernel Densities19 Feb 2025
- 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation4 Apr 2023
- 2022Algorithms with More Granular Differential Privacy Guarantees8 Sep 2022
- 2022FedPerm: Private and Robust Federated Learning by Parameter Permutation16 Aug 2022
- 2022Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy9 Aug 2022
- 2022Network Shuffling: Privacy Amplification via Random Walks8 Apr 2022
- 2022The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning7 Mar 2022
- 2021Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation3 Nov 2021
- 2021User-Level Private Learning via Correlated Sampling21 Oct 2021
- 2021Shuffle Private Stochastic Convex Optimization17 Jun 2021
- 2021A Shuffling Framework for Local Differential Privacy11 Jun 2021
12 newest of 16 All 16 (JSON)