Augmented Shuffle Protocols for Accurate and Robust Frequency Estimation under Differential Privacy
Preprint
Abstract
The shuffle model of DP (Differential Privacy) provides high utility by introducing a shuffler that randomly shuffles noisy data sent from users. However, recent studies show that existing shuffle protocols suffer from the following two major drawbacks. First, they are vulnerable to local data poisoning attacks, which manipulate the statistics about input data by sending crafted data, especially when the privacy budget epsilon is small. Second, the actual value of epsilon is increased by collusion attacks by the data collector and users. In this paper, we address these two issues by thoroughly exploring the potential of the augmented shuffle model, which allows the shuffler to perform additional operations, such as random sampling and dummy data addition. Specifically, we propose a generalized framework for local-noise-free protocols in which users send (encrypted) input data to the shuffler without adding noise. We show that this generalized protocol provides DP and is robust to the above two attacks if a simpler mechanism that performs the same process on binary input data provides DP. Based on this framework, we propose three concrete protocols providing DP and robustness against the two attacks. Our first protocol generates the number of dummy values for each item from a binomial distribution and provides higher utility than several state-of-the-art existing shuffle protocols. Our second protocol significantly improves the utility of our first protocol by introducing a novel dummy-count distribution: asymmetric two-sided geometric distribution. Our third protocol is a special case of our second protocol and provides pure epsilon-DP. We show the effectiveness of our protocols through theoretical analysis and comprehensive experiments.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- LDPGuard: Defenses Against Data Poisoning Attacks to Local Differential Privacy ProtocolsIEEE Transactions on Knowledge and Data Engineering, 2024
- Privacy Enhancement Via Dummy Points in the Shuffle ModelIEEE Transactions on Dependable and Secure Computing, 2023
- Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling2022
- On the Power of Multiple Anonymous Messages: Frequency Estimation and Selection in the Shuffle Model of Differential Privacy2021
- Differential Privacy: From Theory to PracticeSynthesis Lectures on Information Security, Privacy, and Trust, 2016
- Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data DictionariesProceedings on Privacy Enhancing Technologies, 2016
- Participatory Cultural Mapping Based on Collective Behavior Data in Location-Based Social NetworksACM Transactions on Intelligent Systems and Technology, 2016
- The Algorithmic Foundations of Differential PrivacyFoundations and Trends® in Theoretical Computer Science, 2014
- Sensor enabled wearable RFID technology for mitigating the risk of falls near beds2013