Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data
Preprint
Abstract
Shuffle DP (Differential Privacy) protocols provide high accuracy and privacy by introducing a shuffler who randomly shuffles data in a distributed system. However, most shuffle DP protocols are vulnerable to two attacks: collusion attacks by the data collector and users and data poisoning attacks. A recent study addresses this issue by introducing an augmented shuffle DP protocol, where users do not add noise and the shuffler performs random sampling and dummy data addition. However, it focuses on frequency estimation over categorical data with a small domain and cannot be applied to a large domain due to prohibitively high communication and computational costs. In this paper, we fill this gap by introducing a novel augmented shuffle DP protocol called the FME (Filtering-with-Multiple-Encryption) protocol. Our FME protocol uses a hash function to filter out unpopular items and then accurately calculates frequencies for popular items. To perform this within one round of interaction between users and the shuffler, our protocol carefully communicates within a system using multiple encryption. We also apply our FME protocol to more advanced KV (Key-Value) statistics estimation with an additional technique to reduce bias. For both categorical and KV data, we prove that our protocol provides computational DP, high robustness to the above two attacks, accuracy, and efficiency. We show the effectiveness of our proposals through comparisons with twelve existing protocols.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- LDPGuard: Defenses Against Data Poisoning Attacks to Local Differential Privacy ProtocolsIEEE Transactions on Knowledge and Data Engineering, 2024
- Efficient Defenses Against Output Poisoning Attacks on Local Differential PrivacyIEEE Transactions on Information Forensics and Security, 2023
- Local Differential Privacy Protocol for Making Key–Value Data Robust Against Poisoning Attacks2023
- Key-value data collection and statistical analysis with local differential privacyInformation Sciences, 2023
- Differential Privacy for Government Agencies—Are We There Yet?Journal of the American Statistical Association, 2023
- Efficient Noise Generation Protocols for Differentially Private Multiparty ComputationIEEE Transactions on Dependable and Secure Computing, 2022
- Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling2022
- PrivKVM*: Revisiting Key-Value Statistics Estimation With Local Differential PrivacyIEEE Transactions on Dependable and Secure Computing, 2021
- Preventing Manipulation Attack in Local Differential Privacy Using Verifiable Randomization Mechanism2021
- Universally Utility-maximizing Privacy MechanismsSIAM Journal on Computing, 2012