Lune

S&P2025Top-tier venue

Augmented Shuffle Protocols for Accurate and Robust Frequency Estimation Under Differential Privacy

Takao Murakami, Yuichi Sei, Reo Eriguchi

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 ε\varepsilon is small. Second, the actual value of ε\varepsilon 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 ∊-DP. We show the effectiveness of our protocols through theoretical analysis and comprehensive experiments.

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.

5 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data cites Manipulation Attacks in Local Differential Privacy
  • Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data cites Locally Differentially Private Protocols for Frequency Estimation
  • Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data cites Data Poisoning Attacks to Local Differential Privacy Protocols
  • High-Accuracy, Poisoning-Resilient Frequency Estimation in the Shuffle Model cites Manipulation Attacks in Local Differential Privacy
  • High-Accuracy, Poisoning-Resilient Frequency Estimation in the Shuffle Model cites Data Poisoning Attacks to Local Differential Privacy Protocols
  • Fully Oblivious Differential Privacy for Frequency Estimation in the Augmented Shuffle Model with Trusted Processors cites Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data
  • 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 FLAME: Differentially Private Federated Learning in the Shuffle Model
  • 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
  • Robust Single-Message Shuffle Differential Privacy Protocol for Accurate Distribution Estimation cites Manipulation Attacks in Local Differential Privacy
  • Robust Single-Message Shuffle Differential Privacy Protocol for Accurate Distribution Estimation cites Locally Differentially Private Protocols for Frequency Estimation
  • Robust Single-Message Shuffle Differential Privacy Protocol for Accurate Distribution Estimation cites Data Poisoning Attacks to Local Differential Privacy Protocols
  • Doppio: Communication-Efficient and Secure Multi-Party Shuffle Differential Privacy cites Manipulation Attacks in Local Differential Privacy
  • Doppio: Communication-Efficient and Secure Multi-Party Shuffle Differential Privacy cites Data Poisoning Attacks to Local Differential Privacy Protocols
  • Data Poisoning Attacks to Local Differential Privacy Protocols cites Locally Differentially Private Protocols for Frequency Estimation
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value DataTakao Murakami, Yuichi Sei, Reo EriguchiNDSS 2026 · 1 citation
  2. High-Accuracy, Poisoning-Resilient Frequency Estimation in the Shuffle ModelShaoqiang Wu, Jingyu Jia, Yikuan Zhu, Xinhao Li et al.USENIX Security 2026
  3. Fully Oblivious Differential Privacy for Frequency Estimation in the Augmented Shuffle Model with Trusted ProcessorsTakao Murakami, Yuichi Sei, Reo EriguchiUSENIX Security 2026
  4. Robust Single-Message Shuffle Differential Privacy Protocol for Accurate Distribution EstimationXiaoguang Li, Hanyi Wang, Yaowei Huang, Jungang Yang et al.ICDE 2026
  5. Doppio: Communication-Efficient and Secure Multi-Party Shuffle Differential PrivacyWentao Dong, Yang Cao, Cong Wang, Wei-Bin LeeVLDB 2026

Builds on20

  1. Locally Differentially Private Protocols for Frequency EstimationTianhao Wang, Jeremiah Blocki, Ninghui Li, Somesh JhaUSENIX Security 2017 · 629 citations
  2. Manipulation Attacks in Local Differential PrivacyAlbert Cheu, Adam D. Smith, Jonathan R. UllmanS&P 2021 · 122 citations
  3. FLAME: Differentially Private Federated Learning in the Shuffle ModelRuixuan Liu, Yang Cao, Hong Chen, Ruoyang Guo et al.AAAI 2021 · 117 citations
  4. Data Poisoning Attacks to Local Differential Privacy ProtocolsXiaoyu Cao, Jinyuan Jia, Neil Zhenqiang GongUSENIX Security 2021 · 100 citations
  5. Privacy Amplification via Random Check-InsBorja Balle, Peter Kairouz, Brendan McMahan, Om Dipakbhai Thakkar et al.NeurIPS 2020 · 86 citations

Related papers

  1. Defense against Poisoning Attacks under Shuffle-DPSiyi Wang, Qiyao Luo, Yihua Hu, Lixu Wang et al.SIGMOD 2026 · 1 citation
  2. A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing UtilityE. Chen, Yang Cao, Yifei GeAAAI 2024 · 16 citations
  3. Counting Subgraphs under Shuffle Differential PrivacyJuanru Fang, Ke YiCCS 2025
  4. Private Summation in the Multi-Message Shuffle ModelBorja Balle, James Bell, Adrià Gascón, Kobbi NissimCCS 2020 · 52 citations
  5. Shuffle Private Linear Contextual BanditsSayak Ray Chowdhury, Xingyu ZhouICML 2022 · 29 citations
Dusk over the sea between two cliffs drawn in fine vertical lines