Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data

No ratings

Presented at NDSS 2026 by

Takao Murakami

Yuichi Sei

Reo Eriguchi

www.ndss-symposium.org

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.