Learned Messages as a Side Channel Around Pseudonym Rotation

Connected vehicles hide their identities by signing safety broadcasts with short-lived pseudonyms, which are temporary keys they rotate so that an eavesdropper cannot stitch the broadcasts into a travel history. The scheme is conditional: a trusted authority holds a trapdoor that can unmask a misbehaving vehicle, but nobody else should be able to link broadcasts across a pseudonym change. Cooperative multi-agent reinforcement learning, where agents with limited local views learn to coordinate, often by exchanging learned message vectors, pulls the other way. A policy that coordinates well tends to remember each teammate's history. If its messages carry a stable behavioral fingerprint, then any listener can use those messages to re-link pseudonyms, and the rotation stops protecting anyone.

This note proposes to measure that leak and then close it. The core claim is that learned communication in cooperative agents with partial views creates linkability beyond what physical motion already reveals, and that this excess can be trained down to near chance at a small, quantifiable cost in team performance. Linking would then remain possible only through the authority's trapdoor, which is the property conditional privacy is supposed to guarantee.

Why this gap and not the obvious one

Two directions meet here. Conditional privacy work builds the cryptographic machinery. That includes pseudonym certificates fast enough for the 50 ms safety deadline, as in Comparative evaluation of pseudonym-based anonymisation techniques for CAVs, which reports ECDSA verification of about 32 ms on ARM against 946 ms for a pairing-based identity scheme. It includes pairing-free short-term pseudonyms with Sybil resistance, from SRPP, collaborative pseudonym change, from PCP, and auditable unmasking, from Auditable De-anonymization in V2X Communication. All of this work treats message content as fixed kinematic fields. PCP already notes that physical trajectories and fixed beacon intervals undermine rotation.

Multi-agent learning under partial observability supplies coordination methods that depend on identity. LINDA builds a separate awareness distribution for each named teammate from that teammate's trajectory. QMIX and COMA train per-agent utilities and critics that see the global state during training.

The papers that touch both directions leave this question alone. RACE shares policies and relative distances and calls this privacy-by-design, but it uses no pseudonyms and makes no unlinkability claim. PA-DL pairs differential privacy with smart-contract accountability for supervised federated learning, not for sequential control. Optimal transparency via partial observability defines privacy as a minimum block size in a static aggregative game. ℜ-MACRL filters poisoned messages but assumes fixed identities.

The obvious combination would be to wire an anomaly detector into an authority's revocation trigger, the detection gap that Naskar et al. leave open. I set it aside. It is largely an engineering composition of ℜ-MACRL-style detection with blacklisting. More importantly, it presumes the privacy layer is intact, and the question here is whether learned agents silently break it.

Core Claim

Let a pseudonym epoch be the interval between two pseudonym changes. Define a linking adversary as a classifier that receives the broadcast streams from epoch $e$ and epoch $e+1$ and must match each new pseudonym to its predecessor. The quantity that matters is excess linkability: the adversary's matching accuracy when it sees kinematics plus learned messages, minus its accuracy when it sees kinematics alone. Subtracting the kinematics-only accuracy separates the new leak from the physical tracking problem that PCP-style silent periods already address.

The hypothesis has two parts. First, standard communicative agents show large positive excess linkability, especially when agents differ in type or role. Second, an adversarially trained message encoder can push excess linkability near zero while keeping most of the return.

Research Program

The first step is a rotation wrapper. Wrap existing environments so that every $K$ steps each agent's identifier in all peer-visible channels is replaced by a fresh random pseudonym. The channels are message headers and the agent identifiers in observation entity lists. Optionally, a PCP-style silent period follows each change. Messages are signed with an ECDSA-class scheme, and its measured verification latency is injected as a communication delay so the setup respects the 50 ms budget from Sheik et al. The authority alone keeps the mapping from pseudonym to true identity. This is the trapdoor, and it is used only for the accountability evaluation.

The second step is the leakage audit. On trained policies, fit a linking adversary built from recurrent sequence encoders and a matching head. Fit it twice, once on kinematics only and once on kinematics plus messages, and report excess linkability as a function of $K$, team heterogeneity, and message dimension.

The third step is the mitigation. Each agent's memory of a teammate is scoped to the current epoch and reset when the pseudonym changes. The message head is trained against the linker with a gradient-reversal term:

$$ \max_{\pi}\; J(\pi) \;-\; \lambda \,\big[\,\mathrm{Acc}_{\text{link}}(m, x) - \mathrm{Acc}_{\text{link}}(x)\,\big] $$

Here $J(\pi)$ is team return, $m$ is the message stream, $x$ is the kinematic stream, $\mathrm{Acc}_{\text{link}}$ is the accuracy of the adversary trained against the current messages (approximated in training by its cross-entropy), and $\lambda$ sets the trade-off. Sweeping $\lambda$ traces a frontier of return against excess linkability.

The fourth step checks accountability. The authority's trapdoor must still let it link a deliberately misbehaving agent across epochs. This shows the mitigation hides identity from peers without blinding the party that is entitled to unmask.

Baselines

The naive privacy reference is pseudonym rotation with epoch-scoped memory reset and an ordinary learned message head. This is what a practitioner would deploy by default, and it tells us whether the adversarial term adds anything over simply forgetting.

Two reference points bound the problem. The no-privacy upper bound uses fixed identities and full teammate memory. On Traffic Junction, the uncompromised communicative setting in ℜ-MACRL reports a 99.9% success rate, so a fair reimplementation should land near that figure. On SMAC, SIDE reports a 71% median win ratio on 27m_vs_30m, which we use as the identity-aware reference. The no-communication floor uses only local sensors. For it, CH-MARL reports 2.33% unseen-layout success against 12.03% with messages, and RACE reports 65% more collisions for a sensor-only baseline.

The strongest competitor on the privacy axis is Gaussian noise on messages, applied in the style of PA-DL's differential-privacy clipping and calibrated so its excess linkability matches ours. All methods share architecture, environment steps, seeds (at least five), and hyperparameter search budget. The linking adversary is retrained from scratch against each final policy with identical capacity.

Beating these baselines means two things. Our method should reach significantly lower excess linkability than the naive reset baseline. At matched linkability, it should also reach significantly higher return than the noise baseline.

Two ablations isolate the key ingredient. One removes the adversarial term but keeps memory reset. The other keeps the adversary but scores it on total rather than excess linkability, which shows whether subtracting the kinematics-only accuracy changes what is learned.

Why not just…?

Why not just reset memory at each pseudonym change and stop there? This is the most serious threat. If learned messages carry no persistent fingerprint, resetting is enough and the adversary is unnecessary. Resetting clears the receiver's memory but does nothing to the sender, whose messages can still encode stable features such as unit type, role, or policy style. Whether such features appear is exactly what the leakage audit measures. If excess linkability under reset is already near zero, I will report that as the main finding: a negative result that tells deployers memory reset suffices. I will not push the mitigation.

Why not just add differential-privacy noise to messages? The optimal-transparency paper argues that additive noise distorts equilibria and harms coordination. PA-DL also shows that noise alone provides no accountability. Noise is still the fair competitor, so the noise baseline at matched linkability settles the question directly.

Why not just stop communicating? RACE and CH-MARL both report large performance losses without communication, at 65% more collisions and 2.33% versus 12.03% success respectively. The floor baseline quantifies how much of that loss our method recovers while staying unlinkable.

Why not just rely on PCP-style silent periods? Silent periods target the physical tracking channel. Excess linkability is defined to be exactly the leak that remains once kinematic tracking is accounted for, so silent periods are part of every condition and do not address the message channel.

Proposed Experiments

The environments are Traffic Junction and Predator-Prey from ℜ-MACRL, the closest analogues to vehicle beaconing, plus SMAC maps with heterogeneous units where fingerprinting should be strongest. No reported excess-linkability result exists on Lacuna for any of these, so the audit itself is new.

The study has two decisive checks. The first is whether the naive reset baseline shows excess linkability clearly above chance on heterogeneous SMAC and Traffic Junction. Without that leak, the mitigation is moot. The second is whether the return-versus-linkability frontier of our method dominates the noise baseline's frontier across the $\lambda$ sweep, while the authority's trapdoor still links misbehaving agents with near-perfect accuracy.

Secondary measurements cover sensitivity to rotation interval $K$, the effect of the injected ECDSA verification delay on collision rate, and whether a linker larger than the one used in training still fails, which guards against overfitting to a weak adversary.