Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data
Takao Murakami, Yuichi Sei, Reo Eriguchi
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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Fully Oblivious Differential Privacy for Frequency Estimation in the Augmented Shuffle Model with Trusted Processors cites Manipulation Attacks in Local Differential Privacy
- Fully Oblivious Differential Privacy for Frequency Estimation in the Augmented Shuffle Model with Trusted Processors cites Locally Differentially Private Protocols for Frequency Estimation
- Fully Oblivious Differential Privacy for Frequency Estimation in the Augmented Shuffle Model with Trusted Processors cites Data Poisoning Attacks to Local Differential Privacy Protocols
- Locally Differentially Private Protocols for Frequency Estimation cites Heavy Hitter Estimation over Set-Valued Data with Local Differential Privacy
- Data Poisoning Attacks to Local Differential Privacy Protocols cites Locally Differentially Private Protocols for Frequency Estimation
- Data Poisoning Attacks to Local Differential Privacy Protocols cites PrivKV: Key-Value Data Collection with Local Differential Privacy
- Data Poisoning Attacks to Local Differential Privacy Protocols cites Heavy Hitter Estimation over Set-Valued Data with Local Differential Privacy
Cited by top-tier papers1
Builds on22
- Locally Differentially Private Protocols for Frequency EstimationTianhao Wang, Jeremiah Blocki, Ninghui Li, Somesh JhaUSENIX Security 2017 · 629 citations
- Heavy Hitter Estimation over Set-Valued Data with Local Differential PrivacyZhan Qin, Yin Yang, Ting Yu, Issa Khalil et al.CCS 2016 · 344 citations
- PrivKV: Key-Value Data Collection with Local Differential PrivacyQingqing Ye, Haibo Hu, Xiaofeng Meng, Huadi ZhengS&P 2019 · 178 citations
- Manipulation Attacks in Local Differential PrivacyAlbert Cheu, Adam D. Smith, Jonathan R. UllmanS&P 2021 · 122 citations
- Data Poisoning Attacks to Local Differential Privacy ProtocolsXiaoyu Cao, Jinyuan Jia, Neil Zhenqiang GongUSENIX Security 2021 · 100 citations
Related papers
- Augmented Shuffle Protocols for Accurate and Robust Frequency Estimation Under Differential PrivacyTakao Murakami, Yuichi Sei, Reo EriguchiS&P 2025
- High-Accuracy, Poisoning-Resilient Frequency Estimation in the Shuffle ModelShaoqiang Wu, Jingyu Jia, Yikuan Zhu, Xinhao Li et al.USENIX Security 2026
- Defense against Poisoning Attacks under Shuffle-DPSiyi Wang, Qiyao Luo, Yihua Hu, Lixu Wang et al.SIGMOD 2026 · 1 citation
- Poisoning Attacks to Local Differential Privacy Protocols for Key-Value DataYongji Wu, Xiaoyu Cao, Jinyuan Jia, Neil Zhenqiang GongUSENIX Security 2022
- Data Poisoning Attacks to Locally Differentially Private Frequent Itemset Mining ProtocolsWei Tong, Haoyu Chen, Jiacheng Niu, Sheng ZhongCCS 2024 · 2 citations
