Augmented Shuffle Differential Privacy Protocols for Large-Domain Categorical and Key-Value Data
Takao Murakami
Network and Distributed System Security (NDSS) Symposium 2026 · Day 1 · Privacy & Measurement
Shuffle differential privacy offers significantly better accuracy than local differential privacy by using a shuffler to anonymize the source of noisy data. However, existing shuffle DP protocols are vulnerable to **data poisoning attacks** and **collusion attacks**, and prior robust solutions like the **LNF (Local Noise-Free) protocol** suffer from prohibitive costs -- requiring approximately **three years of computation** when the domain size reaches 1 billion items. This talk introduces the **FME (Filtering with Multiple Encryption) protocol**, which is the first to apply **multiple encryption (onion routing-style)** to differential privacy. FME reduces the computational cost from three years to **one day** for billion-item domains while maintaining the robustness guarantees against poisoning and collusion that LNF provides.
AI review
A cryptographic protocol that makes robust shuffle differential privacy practical for billion-item domains by applying multiple encryption (onion routing) to reduce computational cost from three years to one day. The collusion attack finding (10% malicious users raising epsilon from 1 to 7.2) is the most interesting security insight. However, this is fundamentally a privacy engineering paper with no offensive or defensive security applications.