IntraShuffler: A Privacy Preserving Framework for Heterogeneous DP Federated Learning

In federated learning, different users often have different privacy needs. Some institutions might require strict noise injection. Others allow for more precise updates to maintain model utility. This creates a landscape of Heterogeneous Differential Privacy (HDP), where each client selects an individual privacy budget ($\epsilon_i$).

The industry standard for managing this is $\epsilon$-aware aggregation. In this setup, a central server re-weights updates based on their declared privacy budgets. This ensures the global model converges efficiently. However, a new paper demonstrates that this very mechanism creates a massive side channel. Even when clients apply local differential privacy (LDP)—adding noise to gradients to mask data—the server can use the known noise scales to denoise the updates. This enables sophisticated inference attacks.

The Problem

The core issue is that gradient updates are not just random vectors. They retain structural patterns induced by non-independent and identically-distributed (non-IID) data. When a client has a large privacy budget (low noise), their updates are highly consistent. An honest-but-curious server can exploit this consistency.

The authors identify that the risk does not stem from a lack of noise. Instead, it comes from the persistence of client-specific gradient structure. Current defenses like the "shuffle-model"—which uses an intermediary to anonymize the source of updates—fail in HDP settings. The server must know the privacy tier ($\epsilon$) of each update for $\epsilon$-aware aggregation. Therefore, message-level anonymization is fundamentally incompatible with the math required for proper weighting.

As shown in, raw LDP gradients appear overlapping and indistinct.

However, a server equipped with a learned denoiser can restore enough structural signal to train a surrogate model. This model can then successfully categorize clients into behavioral groups. For example, it can distinguish between daytime-active and nighttime-active households in electricity usage datasets.

How It Works

The authors propose IntraShuffler, a middleware defense designed to sit between the clients and the server. It avoids the trap of message-level shuffling by moving the defense to the parameter level. The framework follows three main stages, as outlined in :

1. Adaptive Bucketing: IntraShuffler groups clients into "privacy-compatible buckets" based on their declared $\epsilon$. To prevent small groups from being easily deanonymized, the system uses an adaptive merging mechanism. If a privacy group is smaller than a defined minimum population ($n_{min}$), it merges with an adjacent bucket. This choice minimizes "privacy distance" (the difference in $\epsilon$ values).
2. Parameter-Level Shuffling: This is the critical architectural shift. Within each bucket, the framework does not just shuffle the order of the updates. It performs independent random permutations on individual parameter positions across the clients in that bucket. For every parameter index $j$, a unique permutation is sampled among the clients in the bucket.
3. Aggregate Preservation: Shuffling happens within a bucket where every client shares the same aggregation weight $\alpha_k$. This preserves the mathematical integrity of $\epsilon$-aware aggregation. The sum of the shuffled parameters remains identical to the sum of the original parameters (Proposition 1). This allows the server to update the global model without knowing which parameter came from which client.

By breaking the coherence of the gradient vector, IntraShuffler ensures that a single client's update is no longer a recognizable "signature." It becomes a scrambled collection of values drawn from multiple peers.

Numbers

The authors report significant improvements in privacy protection across vision and time-series workloads. Most notably, IntraShuffler reduces surrogate inference accuracy from 0.78 down to 0.33 [Table 2]. This means the server's ability to correctly guess client attributes is drastically diminished. Regarding the structural signal, the paper finds that IntraShuffler reduces gradient recoverability by over 60% .

This is measured via the cosine similarity (a metric for vector alignment) of denoised gradients.

Crucially, the defense does not break the model. In evaluations on the ComStock dataset, the authors find that IntraShuffler maintains model utility comparable to standard Shuffle-DP [Table 3]. It stays within the margin of run-to-run variability across various aggregators. They also highlight that the defense neutralizes the "high-$\epsilon$ vulnerability." This is the tendency for clients with large privacy budgets to be much easier to target [Table 5].

In terms of computational cost, the authors note that the overhead is $O(mD)$. Here, $m$ is the number of clients and $D$ is the total model dimension. This is asymptotically identical to standard server-side aggregation. The primary cost is simply the linear time required to permute the parameter arrays.

What's Missing

While the results are compelling, there are a few gaps that a practitioner should consider:

• Small-Scale Vulnerability: The efficacy of the defense relies heavily on the bucket population. The authors admit that if a system has many clients with highly diverse, unique privacy budgets, the bucketing logic might result in single-client buckets. In this edge case, parameter-level shuffling provides zero protection.
• Complexity of $n_{min}$ Tuning: The parameter $n_{min}$ (minimum bucket population) acts as a knob between anonymity and utility. Finding the optimal balance for a specific production deployment—where client participation is dynamic—is not addressed.
• System Heterogeneity: The paper focuses almost exclusively on privacy heterogeneity. In real-world production, you likely deal with device heterogeneity (varying compute/memory) and data heterogeneity. It is unclear how the adaptive bucketing logic would behave if it had to account for these extra dimensions.

Should You Prototype This

Yes, if you are building HDP-FL systems with high-stakes data.

If your architecture requires $\epsilon$-aware aggregation to maintain convergence, standard shuffling is not enough. IntraShuffler provides a way to disrupt the gradient signatures that enable behavioral inference and cross-round linkage. It is a "drop-in" middleware solution. It does not require rewriting client-side training loops or server-side optimizers. However, if your client pool is extremely small or your privacy budgets are highly fragmented, you won't get the protection you expect. Start by profiling your expected $\epsilon$ distribution. Ensure your buckets will have enough density to matter.

Figures from the paper