Protecting the Fingerprint, Not Just the Example: Two-Level Continual Release Against Cross-Modal Linkage

When a phone or laptop repeatedly sends model updates to a server, each update looks harmless. Over many rounds, though, the updates add up to a portrait of the user's habits: which kinds of photos they take, which topics they write about. An adversary can match that portrait against public data in an entirely different medium, such as linking a person's blog posts to their image-classifier gradients. Privacy tools built for data streams make this worse in a specific way. The standard way to release a stream privately, continual-release differential privacy (adding calibrated random noise so that any single record has provably small effect on everything published over time), mostly protects each individual example. Its most efficient variants use correlated noise that cancels across time, so running sums come out accurate. A user's running sum is exactly where their habits accumulate. The mechanisms that make streaming privacy cheap may therefore make the cross-modal fingerprint sharper the longer the stream runs.

We propose to measure this effect and then fix it cheaply. Each client's per-round update is split into two parts. The first is a low-dimensional "fingerprint" part: the directions in parameter space that carry between-user differences, estimated from public proxy users. That part is released under user-level continual-release privacy, which protects the person's entire history. The rest of the update is released under ordinary example-level continual release. Because the fingerprint part is small, protecting it at the user level costs far less utility than protecting the whole update at the user level. That full user-level protection is the expensive route that has led prior work to abandon differential privacy for this threat altogether.

Core Claim

Cross-modal linkage attacks feed on aggregate, user-level regularities that example-level guarantees do not cover. Selection bias in decentralized learning is one; repeated attendance patterns in sensor logs are another. Our first claim is empirical. Under the correlated-noise continual-release mechanisms people actually deploy, cross-modal linkage accuracy rises with the number of rounds observed and approaches the unprotected attack, even though the formal example-level budget stays fixed. Our second claim is constructive. Let $g_t$ be a client's clipped update at round $t$, and let $P$ be a projection onto a $k$-dimensional public fingerprint subspace with $k$ much smaller than the model size. Releasing $Pg_t$ through a user-level continual counter and $(I-P)g_t$ through an example-level matrix mechanism should push linkage close to chance at a utility cost much smaller than full user-level protection. The resulting guarantee has two levels and is stated honestly. Every example is protected at $\varepsilon_e$. The whole user is protected at $\varepsilon_u$ along the fingerprint subspace. The remainder carries no formal user-level claim, and residual leakage through it is measured empirically rather than assumed away.

What Exists and What Is Missing

The motivating evidence comes from three attack papers. Understanding and Controlling User Linkability in Decentralized Learning shows that client updates encode selection bias. Its cross-modal matcher links Blog Authorship text profiles to OpenImages gradient updates at 0.76 AUC. The authors set differential privacy aside because per-update noise destroyed utility before linkability fell, and turned instead to public-corpus augmentation. They tested only one-shot per-round noise, never streaming mechanisms, and never separated example-level from user-level protection; the gap we target sits in both of those omissions. Nowhere to Hide links Wi-Fi device identifiers to face and voice clusters using binary attendance vectors. It reports that individuals become nearly unique after 25–50 sessions, which is direct evidence that linkage grows with observation time. Privacy Disclosure of Similarity Rank in Speech and Language Processing supplies our second leakage metric: bits of disclosure computed from where the true identity ranks among candidates. Its LibriLong observation that disclosure saturates is a constraint we test, since saturation would weaken our first claim.

The method draws on the continual-release line. (Nearly) Optimal Algorithms for Private Online Learning privatizes running gradient sums with tree aggregation, a binary tree of partial sums in which each record touches only $\log T$ nodes. Private Continual Counting of Unbounded Streams gives a smooth matrix-mechanism counter for streams of unknown length, which suits clients whose participation is open-ended. Continual Release Moment Estimation with Differential Privacy shows that analyzing several streamed statistics jointly beats splitting the budget between them. We reuse that lesson when calibrating the two channels together instead of composing them naively. Privacy Odometers and Filters provides the stopping rule. A privacy filter halts a client's fingerprint channel once its user-level budget is spent, which is valid even when participation is chosen adaptively. None of these papers considers who the adversary is or what they link; all of them optimize accuracy of prefix sums. Our proposal starts from the observation that accurate prefix sums are what the linkage adversary wants.

Privacy Enhanced Multimodal Neural Representations and OCTOPUS define the non-differential-privacy alternatives. The first scrubs protected attributes from audio-text features adversarially. The second separates private from public latent codes. Both act on features rather than on the update stream, and neither gives a guarantee.

Research Program

The threat model follows the linkability paper. An honest-but-curious server sees every client's update stream. It also holds auxiliary profiles in another modality, such as text for image clients, and tries to match each anonymous update stream to a profile. Noise is therefore added on the client, and the server benefits from averaging over $n$ clients.

The first component is an audit. We will run streaming federated training on the OpenImages/Blog Authorship setup under four regimes: no noise; independent per-round Gaussian noise; client-side tree aggregation; and the unbounded matrix-mechanism counter, all at matched example-level budgets. We then retrain the paper's MLP and Siamese cross-modal attackers on the noised streams after 1, 5, 10, 25 and 50 rounds. The output is a linkage curve, AUC and similarity-rank bits against rounds, plotted next to the formal odometer value. That plot directly tests the claim that formal and empirical risk diverge over time.

The second component builds the fingerprint subspace. We estimate $P$ from public proxy users built by splitting public corpora into synthetic "users" with skewed label mixtures, taking the top-$k$ directions of between-user variance in their updates. We expect much of the selection-bias signal to sit in last-layer and class-bias coordinates, which suggests $k$ on the order of the number of classes. We will vary $k$ and test whether a subspace estimated on proxies transfers to real users.

The third component is the two-level release and its accounting. Each client clips $Pg_t$ to norm $c_f$ and feeds it to the unbounded counter at user-level sensitivity, with a filter capping total participation. In parallel it feeds $(I-P)g_t$ to an example-level matrix mechanism. We will choose $c_f$ and the two noise scales jointly to maximize validation accuracy under a fixed pair $(\varepsilon_e, \varepsilon_u)$, following the joint-calibration logic of the moment-estimation paper.

Baselines

The naive reference point is non-private streaming training. It sets the attack ceiling, which we expect to reproduce the reported 0.76 cross-modal AUC from Understanding and Controlling User Linkability, and the accuracy ceiling. The second reference is example-level continual release with client-side tree aggregation, as in (Nearly) Optimal Algorithms, and with the unbounded counter of Private Continual Counting. This is what a practitioner would deploy today, and our audit predicts it leaves linkage nearly intact.

The strongest privacy competitor is full user-level continual release on the entire update. It gives the strongest guarantee and would, by construction, suppress linkage, so the comparison is about utility. The file reports that standard DP in non-IID federated learning reaches only 30–51% CelebA accuracy against OCTOPUS's ~87% (OCTOPUS), which suggests the cost is large. We found no result on Lacuna for user-level tree-aggregated release under a cross-modal linkage attack, so we will measure it ourselves.

The strongest empirical-privacy competitor is mm-aug from the same linkability paper. It reports up to 95% reduction in attack effectiveness with negligible task loss, and that is the number to beat or match. All methods share the same clients, rounds, model, and attacker-retraining protocol, and each receives an equal hyperparameter search budget.

The key ablation isolates the subspace. It keeps the two-level structure and the same $k$ and noise, but uses a random $k$-dimensional projection, and separately an oracle subspace estimated on the real users. "Beating" the field means two things. Against example-level release, the method must reach linkage AUC within 0.05 of chance at no worse accuracy. Against full user-level release, at matched $\varepsilon_u$ and similar linkage, it must achieve clearly higher accuracy.

Why not just…?

Why not just use full user-level differential privacy and accept the cost? It is the principled answer, and if its accuracy at useful $\varepsilon_u$ turns out close to ours, our method is unnecessary. The evidence in the file suggests it is not: the linkability authors abandoned DP over utility, and OCTOPUS reports 30–51% accuracy for DP in non-IID federated learning. Those results used one-shot or per-round noise, however, so we run tree-aggregated user-level release directly as a baseline. The comparison settles the question either way.

Why not just use mm-aug or adversarial scrubbing? mm-aug is a real threat on its home benchmark, given its reported 95% reduction. It needs task-matched public corpora and gives no guarantee against attackers it was not tuned for. Gradient-reversal scrubbing (Privacy Enhanced Multimodal Neural Representations) still left MuSE membership attacks at 0.60, and it operates on features, not on the update stream. We will evaluate both against an adaptive attacker retrained on defended updates and with mismatched public corpora. If mm-aug holds up there at equal accuracy, our advantage is only the guarantee, and we will say so.

Why not just protect the label histogram and skip the learned subspace? This simpler variant may be enough if selection bias lives almost entirely in class frequencies. The random-subspace and $k$-sweep ablations, plus a label-coordinates-only arm, test it directly. If the label-only arm matches, we adopt it as the method.

Why not rely on saturation, given that disclosure plateaus over long observation? The similarity-rank paper does report saturation, but the plateau for speaker embeddings is ~9.97 bits, and attendance-based linkage in Nowhere to Hide grew with sessions. Our linkage curves measure whether update-stream fingerprints saturate or keep growing.

Proposed Experiments and Decisive Checks

The primary benchmark is streaming federated image classification on OpenImages, attacked with Blog Authorship profiles, with PIPA as a second image domain. A speech-and-text arm uses MSP-Podcast clients training an emotion model, which offers more speakers than IEMOCAP. That arm reports similarity-rank disclosure in bits, computed with the beta-binomial estimator against Fisher/VoxCeleb-style speaker candidates. Metrics are linkage AUC, top-1 re-identification, disclosure bits, joint identity-and-attribute inference, and task accuracy (UAR for emotion), each plotted against rounds and against the two privacy levels.

Three results would be decisive. First, the audit must show linkage under example-level continual release rising with rounds, with the correlated-noise mechanism rising faster than independent noise. If the curve stays flat near chance, the premise fails and the cheaper example-level mechanisms suffice. Second, the two-level release must bring AUC near chance while holding accuracy well above full user-level release. If residual leakage through $(I-P)g_t$ keeps AUC near the unprotected value at every practical $k$, the low-dimensional fingerprint hypothesis is false. Third, as a robustness check, an attacker who uses only the timing of client participation must remain defeated. Participation timing is the federated analogue of the attendance vectors in Nowhere to Hide. The filter-capped participation schedule is meant to block this channel, and failure here would show the guarantee needs a third, participation-level component.