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

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

Speakers: Takao Murakami

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=qfeEA-me3uw

Overview

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.

Background

▶ Watch: Shuffle DP overview and its two security issues (0:00)

The shuffle model of differential privacy extends the local model by introducing a shuffler between users and the data collector. Users add noise to their data, the shuffler randomly shuffles the noisy data, and the data collector decrypts the shuffled data. The random shuffling amplifies privacy, meaning the effective epsilon is much smaller than the local epsilon, allowing significantly less noise to be added while maintaining the same privacy guarantee.

However, existing shuffle DP protocols face two critical security issues:

Data Poisoning Attacks: Malicious users can send fake data to manipulate statistics. This is especially damaging when epsilon is close to zero, because normal users add significant noise while malicious users can send precise fake data -- creating a large gap in influence between honest and malicious participants.

Collusion Attacks: When users collude with the data collector by sharing their pre-shuffling noisy data, the shuffling effect is reduced or eliminated. Even with 10% of users colluding, the effective epsilon can increase dramatically from 1 to 7.2, destroying the privacy guarantee. This is practical because attackers can inject many fake accounts into real systems.

The researchers' prior work at S&P 2025 introduced the LNF protocol, which moves noise addition to the shuffler side (users send unnoised data, the shuffler adds noise through random sampling and dummy injection). This provides robustness against both attack types but has communication and computation costs linear in the domain size D, making it impractical for large domains.

Key Findings

▶ Watch: FME protocol: multiple encryption meets differential privacy (4:00)

Multiple Encryption for DP: The FME protocol is the first to use multiple encryption (similar to onion routing) in the differential privacy literature. Each data item is encrypted three times using public keys of the data collector, shuffler, and data collector, enabling a filtering step that reduces the domain size without requiring a second round of user interaction.

Domain Size Reduction: By using hash functions to reduce the domain from D to B (where B is much smaller than D), FME can filter and select popular items at the hash level, then decrypt and process only the relevant items. This reduces computational complexity from linear in D to square root of D.

One-Round User Interaction: A naive approach would require two rounds of user communication (first to filter by hash, then to collect actual values). FME eliminates the second round by having users send both hash values and multiply-encrypted input values in a single round. The shuffler and data collector then communicate between themselves to perform filtering, with the multiple encryption ensuring that shuffled values at each step are completely different, preventing linkability attacks.

Performance Results: For 1 billion items, FME reduces communication from 100 terabytes to 260 gigabytes and runtime from three years to one day. Since most practical applications have domain sizes below 1 billion (Amazon has approximately 600 million items), FME handles virtually all real-world scenarios within one day.

Key-Value Data Extension: FME is extended to handle key-value data (where each user has key-value pairs and the goal is estimating frequency and mean for each item). A critical insight is performing filtering at the key level rather than the key-value pair level to avoid introducing large bias in mean value estimates.

Technical Deep Dive

▶ Watch: Domain size reduction via hash filtering (8:00)

The FME protocol operates as follows:

Step 1 (User Side): Each user sends both a hash value H(xi) and the input value xi to the shuffler. The input value is encrypted three times using the public keys of the data collector, shuffler, and data collector (in that order) -- creating an onion-like encryption structure.

Step 2 (Shuffler): Performs augmented shuffling (random sampling, dummy addition, and shuffling) on the hash values and corresponding encrypted input values. Sends shuffled hash values and encrypted data to the data collector.

Step 3 (Data Collector): Decrypts the outermost encryption layer and performs filtering -- selecting popular items based on hash values and replacing unselected items with "bot" (null). Sends selected items and still-encrypted values back to the shuffler.

Step 4 (Shuffler): Performs another augmented shuffling round, decrypts its encryption layer, and sends the data back to the data collector.

Step 5 (Data Collector): Decrypts the final encryption layer and calculates the frequency distribution.

The multiple encryption ensures that the data appears completely different at steps 3, 5, and 7, preventing any linkability between the filtering step and the final output. The protocol provides a computational version of differential privacy (as opposed to information-theoretic DP).

The LNF base protocol uses random sampling (with probability beta) and dummy addition (sampling dummy counts from an asymmetric geometric distribution providing DP) on the shuffler side. This is robust because malicious users cannot affect the noise (which is added by the shuffler, not users) and cannot benefit from sharing their data with the collector (since the data is noise-free before shuffling).

Demo / Proof of Concept

▶ Watch: Key idea: one-round user interaction with onion encryption (10:00)

Experimental results on the census dataset demonstrated:

• FME significantly outperforms existing shuffle DP protocols (shown as the red line) in both frequency estimation MSE and key-value statistics estimation MSE
• Communication cost and runtime improvements are dramatic: square root of D versus linear in D
• Robustness against both poisoning and collusion attacks is maintained at the same level as LNF
• The protocol handles domains up to 1 billion items within one day of computation

Defensive Implications

▶ Watch: Results: three years to one day for billion-item domains (14:00)

FME addresses practical deployment barriers for robust shuffle differential privacy:

Poisoning Resistance at Scale: For organizations collecting privacy-preserving statistics from large user bases, the vulnerability to data poisoning attacks (where malicious users inject fake data to skew results) is a real operational concern. FME provides robustness against this attack without the prohibitive computational costs of prior solutions.

Collusion Resistance: The demonstration that 10% of colluding users can increase effective epsilon from 1 to 7.2 should alarm any organization relying on shuffle DP. FME's noise-on-shuffler approach prevents this attack class entirely.

Trust Model Consideration: FME assumes the shuffler and data collector are semi-honest and do not collude with each other. If they do, pre-shuffling data can be revealed. The researchers suggest implementing the shuffler using Trusted Execution Environments (TEEs) to address this trust assumption.

Key Takeaways

• Existing shuffle DP protocols are vulnerable to data poisoning (malicious users sending fake data) and collusion attacks (users sharing data with the collector to reduce shuffling effect)
• 10% user collusion can increase effective epsilon from 1 to 7.2, devastating privacy guarantees
• FME is the first protocol to use multiple encryption (onion routing-style) in differential privacy, enabling one-round user interaction with robust filtering
• Computational cost is reduced from three years to one day for billion-item domains by reducing complexity from linear to square root of D
• Key-value data filtering must be performed at the key level, not key-value pair level, to avoid bias in mean estimates
• The shuffler-data collector non-collusion assumption can be addressed with Trusted Execution Environments

About the Speaker(s)

Takao Murakami is a researcher at ISM (Institute of Statistical Mathematics) in Japan, working with collaborators on privacy-preserving data analysis. This work builds on the team's prior LNF protocol presented at S&P 2025, extending robustness guarantees to large-domain data through the novel application of multiple encryption techniques from anonymous communication to differential privacy.