In federated learning, many phones or hospitals train one model by sending gradient updates to a server instead of raw data. Those updates leak: an attacker can often rebuild the training images from them. A popular middle ground between trusting the server and trusting no one is the shuffle model. Each client adds a small amount of noise locally, then a separate relay mixes all clients' messages into an anonymous, unordered pile before the server sees them. Hiding each message among $n$ others lets clients add far less noise for the same formal privacy guarantee. Because model gradients are huge, practical shuffle protocols cut each update into many small messages: sampled coordinates, top-$k$ entries, or compressed seeds. Current systems are judged only by accuracy and a proven privacy number $\epsilon$. Nobody has checked what an attacker can actually rebuild from the pile of fragments. This matters most at the moderate-to-large $\epsilon$ values (around 1 to 10) that deployed systems report, where the formal guarantee is too weak to rule out reconstruction.
We propose to measure leakage in these fragmented shuffle protocols with a two-stage attack. The attacker first re-stitches anonymous fragments back into per-client groups, using the correlations real gradients have across coordinates. It then runs standard gradient-inversion attacks on each reassembled group. The main quantity we report is beyond-sum leakage: how much better images can be rebuilt from the full pile of messages than from the noisy average the protocol is meant to release. If that gap is large for some message formats and near zero for others at the same $\epsilon$, then the way a protocol splits its messages is a privacy parameter in its own right. We then design and cost a message format that drives the gap to zero.
Core Claim
At a fixed formal $\epsilon$, how much a multi-message shuffle protocol leaks in practice depends on how it formats its messages. Formats whose fragments carry per-client structure leak measurably more reconstructable information than the noisy aggregate alone. Examples are coordinate indices tied to a client's top-$k$ selection, or several fragments that jointly encode one client's vector. Formats whose fragments are exchangeable across clients leak essentially nothing beyond the aggregate, meaning a fragment's distribution does not reveal which client sent it. This is not a claim that the shuffle-DP proofs are wrong. A valid proof bounds what any attacker, including ours, can gain from the multiset. The claim concerns two things. The first is how much of a large $\epsilon$ budget is realized in practice. The second is whether implementations match the protocols that were analyzed, including details such as dummy padding and index privacy.
The motivating evidence comes from both sides of the literature. On the shuffle side, Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages proves that central-level accuracy needs roughly $d$ messages per user. That result pushes protocols toward fragmentation, whether by coordinate-wise one-dimensional randomizers or by spreading the vector with Kashin's representation. FLAME uses dimension subsampling, dummy padding, and top-$k$ with "index privacy". Camel sends a random-generator seed plus a sign bit per message. None of these three evaluate inversion attacks. On the attack side, two prior results suggest that partial and aggregated gradients remain dangerous. Gradient Inversion with Generative Image Prior reconstructs images even with 99% of gradient values removed. The Cocktail Party Attack unmixes aggregated fully connected gradients for batches of up to 1,024, provided the layer is at least as wide as the batch. A pile of sparse, locally noised fragments sits between these two threat settings and has not been studied.
Research Program
The attack. The honest-but-curious server receives the shuffled multiset of fragments. It has a public proxy dataset of the same kind FL-TOP assumes, which it uses to learn a model of joint gradient statistics under the current global weights. Re-stitching is a clustering or assignment problem. The server partitions the fragments into $n$ groups so as to maximize each group's likelihood under the learned gradient model. It exploits any structure the format exposes: which coordinates appear together, value correlations within a layer, message counts, and sign patterns. We measure stitching accuracy as the fraction of fragments assigned to the correct client, computed against ground truth that only the experimenter holds.
Each reassembled group is then treated as that client's noisy, partial gradient and attacked in three ways:
- Deep Leakage from Gradients (DLG), which matches the gradients of a dummy input to the observed ones.
- GIAS from Gradient Inversion with Generative Image Prior, which searches the latent space of a generative model.
- The Cocktail Party Attack, applied where the width condition holds.
Following Evaluating Gradient Inversion Attacks and Defenses in Federated Learning and Do Gradient Inversion Attacks Make Federated Learning Unsafe?, we keep batch-normalization statistics local and labels unknown, so that no attack gains from those leaks.
The measurement. For each protocol we run the same inversion attacks on two inputs. One is the protocol's decoded noisy aggregate, which is the intended output. The other is the re-stitched groups. Beyond-sum leakage is the difference in reconstruction quality between the two, measured in PSNR, SSIM, and LPIPS. We trace this gap as a function of formal $\epsilon$, messages per user, and bits per message. The result is a three-way frontier across communication, formal privacy, and empirical reconstructability, rather than the usual two-way accuracy-versus-$\epsilon$ curve.
The fix. We build an exchangeable message format and measure how much it costs in communication. Each client applies a random rotation drawn fresh each round from a public seed, then a Kashin-style spreading step, so that every coordinate is small. It then emits one-dimensional shuffle-randomized reports for a fixed, publicly chosen set of coordinates. No per-client index selection occurs, and every client sends the same number of messages. The goal is that a single fragment's distribution is nearly independent of its sender, which should push re-stitching toward chance. This is roughly the regime analyzed in the vector mean estimation work. It trades communication for exchangeability, and we measure that trade in bits per client. As the per-coordinate randomizer we also test the Blanket-Mixed Gaussian mechanism from Shuffling-Aware Optimization for Private Vector Mean Estimation. That mechanism was proven optimal on synthetic unit-ball vectors but never tried on real gradients.
Baselines
Naive references. The first is non-private FedAvg under the same inversion attacks. It fixes the top of the leakage scale; Mixed Quantization reports 55.3 dB DLG PSNR on undefended CIFAR-10. The second is local-DP federated learning with no shuffling, which fixes the high-noise, low-utility end. Every protocol is run on the same client split, the same model, and the same number of rounds.
Strongest existing shuffle methods. These are FLAME's SS-Topk and SS-Double, and Camel's NoisyGradCmpr. They are the published shuffle-model federated learning systems that most aggressively reduce communication, so they are exactly the designs whose fragments might be stitchable.
- For FLAME, the reported target is SS-Topk on MNIST logistic regression ($d=7{,}850$, $n=1{,}000$) at $\epsilon=0.24$, within 1.48% of non-private federated learning (FLAME).
- For Camel, the reported target is 84.83% MNIST accuracy at $\epsilon=10$ (Camel).
- We reproduce both configurations before running any new ones. We give every method the same accounting method and the same hyperparameter search budget, with 20 configurations tuned on a held-out validation client set.
Trusted-aggregation reference. This is central DP with secure aggregation and a fixed top-$K$ subspace, as in FL-TOP. That paper reports 0.81 Fashion-MNIST accuracy at a 0.5% compression ratio (FL-TOP). The server there sees only a noisy sum, so this reference has zero beyond-sum leakage by construction.
Ablation of the key ingredient. We compare the exchangeable format with and without its two components, the per-round random rotation and the fixed public coordinate set. This isolates what drives stitching accuracy down.
What counts as success. The exchangeable format succeeds if it meets two conditions at matched formal $\epsilon$. First, its beyond-sum leakage must be statistically indistinguishable from zero across 5 seeds. Second, its accuracy must stay within 2 points of the reproduced FLAME and Camel numbers. We also report its bit cost. The measurement claim succeeds if at least one existing protocol shows a clearly positive beyond-sum gap, defined as an LPIPS difference whose confidence interval excludes zero.
Why not just…?
Why not just attack the decoded aggregate, as the Cocktail Party Attack already does? Because the server in a shuffle protocol receives the whole multiset, not only its sum. For formats like top-$k$ with indices or seed-based compression, the multiset can carry per-client structure that the sum lacks. Aggregate-only attacks therefore measure the wrong object. Attacking the aggregate is not discarded, though: it is exactly the reference arm of our beyond-sum measurement. If re-stitching never beats it on any protocol, the study still settles the question and is itself a publishable negative result.
Why not just audit with membership-inference canaries instead of reconstruction? Canary audits estimate how tight $\epsilon$ is, but they do not tell practitioners whether identifiable images can be recovered at $\epsilon=10$, which is the harm that motivates gradient-leakage work. We will run a canary audit alongside the reconstruction attacks as a secondary check. If the two methods rank the protocols differently, that disagreement is informative in itself.
Why not just drop the shuffler and use secure aggregation with central DP, as FL-TOP does? This is a genuine threat. It removes beyond-sum leakage by construction and reports strong utility. It does, however, assume a different trust setup: cryptographic aggregation, and a public proxy set for choosing which weights to update. Camel's own design shows that making the shuffle robust to a malicious server already requires three honest-majority servers. We include this approach as a baseline on accuracy, bits per client, and leakage. If it dominates all three at matched $\epsilon$, we will report that shuffle-model federated learning buys only a different trust model, not better privacy.
Proposed Experiments
The first setting reproduces FLAME exactly: MNIST, logistic regression, $n=1{,}000$ clients. We sweep $\epsilon$ from 0.24 to 10 and messages per user from one up to on the order of $d$. The second setting uses Fashion-MNIST and CIFAR-10 with LeNet-5 and a small ConvNet, matching the models used in Mixed Quantization and DCS². The third is a stress test on TinyImageNet with ResNet18 and local batch-normalization statistics, where reported numbers show that inversion struggles even without any defense.
We report five quantities: stitching accuracy against the chance rate of $1/n$, PSNR, SSIM, and LPIPS against the undefended CIFAR-10 LPIPS of 0.45 from Evaluating Gradient Inversion Attacks and Defenses, test accuracy, and bits per client per round.
Three checks decide the outcome:
- Is there a measurable gap? Stitching accuracy for SS-Topk or Camel must rise clearly above $1/n$, and the resulting gradient-matching reconstructions must beat aggregate-only reconstructions at the same $\epsilon$.
- Does the gap close? The exchangeable format must bring stitching back to chance, and the price must be a stated, measured increase in communication.
- Does leakage depend only on $\epsilon$? If every protocol at matched $\epsilon$ shows the same reconstruction quality, the core claim is false. In that case we conclude that message format does not matter empirically, which is also useful guidance for system designers.
No reported result was found on Lacuna for gradient inversion against any shuffle-model federated learning protocol. All leakage numbers for those protocols will therefore be new measurements.
References
- Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
- FLAME: Differentially Private Federated Learning in the Shuffle Model
- Camel: Communication-Efficient and Maliciously Secure Federated Learning in the Shuffle Model of Differential Privacy
- Gradient Inversion with Generative Image Prior
- Cocktail Party Attack: Breaking Aggregation-Based Privacy in Federated Learning Using Independent Component Analysis
- Constrained differentially private federated learning for low-bandwidth devices
- Deep Leakage from Gradients
- Evaluating Gradient Inversion Attacks and Defenses in Federated Learning
- Do Gradient Inversion Attacks Make Federated Learning Unsafe?
- Shuffling-Aware Optimization for Private Vector Mean Estimation
- Mixed Quantization Enabled Federated Learning to Tackle Gradient Inversion Attacks