Linkage Attack Test¶
Re-identification / linkage test — instantiates Reconstruction-Resistant Disclosure Design
Tests whether released records can be joined to outside datasets on shared quasi-identifiers to re-identify individuals or infer their protected attributes.
A dataset stripped of names can still point straight at people through the details it keeps. The Linkage Attack Test checks for that by trying, under controlled conditions before release, to join the outgoing records to datasets an outsider could obtain — public registries, commercial files, social-media posts, a leaked breach — on the fields they share. Those shared fields, the quasi-identifiers (a birth date here, a postcode there, a job title, a rare diagnosis), seldom identify anyone alone but often do in combination. The test's defining move is reaching outside the release: where a differencing attack needs only your own outputs, linkage succeeds or fails on what auxiliary data exists in the world, so the test's real work is assembling a realistic catalogue of that outside data and measuring how much of the release it re-identifies. It is the empirical answer to the question "is de-identified actually un-linkable?"
Example¶
A streaming service releases a large sample of "anonymized" viewing histories — user IDs replaced by random tokens, no names — so researchers can improve recommendations. Before publishing, the team runs a linkage test. Standing in for an outsider, it pairs the release against a public source: the reviews people post under their own names on a public film site, timestamped and specific. A viewer who logged a handful of unusual films in the release, around the same dates they publicly reviewed those same films, matches to exactly one public profile — and now their entire private viewing history, including titles they never posted, is attached to a real name.
The test reports what fraction of the sample re-identifies this way and how few distinctive titles it takes, so the team can coarsen or perturb the histories, or hold the release, before it ever ships. The pattern mirrors the well-documented de-anonymization of a public movie-ratings dataset by linking it to a public review site.[1]
How it works¶
- Assemble the auxiliary register — the specific external datasets a plausible adversary could hold, with their fields and coverage, seeded from the workshop's prior model plus known public, commercial, and breach sources.
- Identify shared quasi-identifiers between the release and each auxiliary dataset.
- Attempt controlled matches — exact or probabilistic — in a sandbox, against your own release.
- Measure the re-identified fraction and confidence, and feed failures to remediation.
It is an in-house audit against your own data, not an operation against a real person; the whole point is to fix the release before anyone can run the join for real.
Tuning parameters¶
The dials that adapt the test to a threat model:
- Auxiliary set — which outside datasets the test assumes the adversary holds, from public-only to a resourced actor with breach data; weaker assumptions pass more releases and protect less.
- Match strictness — exact key joins versus fuzzy, probabilistic matching that tolerates noise and typos; looser matching finds more real links and more false ones.
- Quasi-identifier set — which combinations of fields are treated as linkable; missing one unglamorous field, a rare category or a timestamp, is how linkage tests pass while reality fails.
- Fail threshold — the re-identified fraction or confidence that blocks the release; set it from the harm of a single re-identification, not an average.
When it helps, and when it misleads¶
Its strength is that it turns "we removed the identifiers" into a measured claim, catching the quasi-identifier exposure that field-level redaction structurally misses.[2]
Its honesty is bounded by the auxiliary data you thought to include: a release that passes against today's known datasets can be re-opened tomorrow by one newly published or breached file, so a pass is provisional, never permanent. Its classic misuse is to test against a deliberately thin auxiliary set and certify the comfortable result. The discipline is to assume a well-resourced adversary, include the unglamorous quasi-identifiers, and route every pass to continuous monitoring with an expiry rather than banking it as safe.
How it implements the components¶
The test fills the external-join side of the archetype — the components that model reconstruction from outside data:
auxiliary_information_register— it builds and owns the concrete, join-key-level catalogue of external datasets a realistic adversary could hold; that register is both its main input and a durable artifact.reconstruction_attack_model— it instantiates reconstruction as linkage: the specific join paths and quasi-identifiers by which outside data re-identifies the release.
It consumes the who-knows-what picture from Auxiliary-Prior Review Workshop rather than producing it (adversary_prior_model), and it neither applies the fix (release_transformation_policy — Coarsening and Generalization Policy, Noise or Randomization Release) nor tests the model-only attacks of Membership Inference Probe and Model Inversion Red Team.
Related¶
- Instantiates: Reconstruction-Resistant Disclosure Design — the test is the empirical proof that a release resists re-identification by joining to outside data.
- Consumes: Auxiliary-Prior Review Workshop supplies the adversary-prior picture that seeds the auxiliary register.
- Sibling mechanisms: Auxiliary-Prior Review Workshop · Membership Inference Probe · Differencing Attack Scan · Coarsening and Generalization Policy · Model Inversion Red Team · Noise or Randomization Release · Post-Release Reconstruction Monitor · Privacy Budget Accounting · Query Rate and Overlap Limit · Small-Cell Suppression Rule · Synthetic or Perturbed Data Validation
Editorial Notes¶
Form Classification¶
Form family: Experiment, Test & Rehearsal
Rationale: Linkage Attack Test operates as a bounded trial, probe, simulation, or rehearsal that generates evidence from performance because it tests whether released records can be joined to outside datasets on shared quasi-identifiers to re-identify individuals or infer their protected attributes.
Independent corroboration: The frozen evidence defines Linkage Attack Test as 'Tests whether released records can be joined to outside datasets on shared quasi-identifiers to re-identify individuals or infer their protected attributes', so its operative form is Experiment, Test & Rehearsal.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Specialized
Rationale: Linkage attacks and re-identification testing arise from computer security and data-privacy research.
Related originating lineages:
- Data Science & Analytics — Record linkage on quasi-identifiers supplies the practical attack method.
- Security Studies & Intelligence Analysis — Adversarial threat modeling materially shapes the test's attacker-oriented posture.
- Statistics & Experimental Design — Statistical disclosure limitation and re-identification risk models materially shape quasi-identifier linkage tests.
- Ethics of Technology & AI Governance — Re-identification testing is a core privacy-engineering and responsible-data-governance practice.
Review resolution: Light authoritative research supports computer_science as the primary provenance: Linkage attacks and re-identification testing arise from computer security and data-privacy research. NIST's de-identification report reviews computer-science research showing that released data can be re-identified by linkage. The competing reviewed lineage (tech_ethics_ai_governance) and other formative traditions remain explicit alternates rather than being erased or confused with downstream applicability. origin_mode=cross_disciplinary_synthesis records the relationship among those origin traditions, while domain_reach=specialized separately records how broadly the generalized mechanism can be applied.
Review outcome: Researched adjudication after independent review; high confidence.
Sources consulted:
- https://www.nist.gov/publications/de-identification-personal-information — NIST's de-identification report reviews computer-science research showing that released data can be re-identified by linkage.
Notes¶
A linkage pass has a shelf life. Re-identifiability rises monotonically as the world publishes more data, so results should carry the date and auxiliary set they were valid against, and be re-run when the landscape shifts — the standing job of Emergent Prior Monitor.
References¶
[1] Linking a "de-identified" movie-ratings release to public reviews to re-identify subscribers is the Netflix Prize de-anonymization (Narayanan and Shmatikov, 2008); the same quasi-identifier logic underlies re-identification of ostensibly anonymous health records by joining them to public registries. registry ↩
[2] Narayanan, Arvind; Shmatikov, Vitaly. "Robust De-anonymization of Large Sparse Datasets". 2008 IEEE Symposium on Security and Privacy, 111–125 (2008). Measures de-anonymization success and shows that sparse attribute combinations and auxiliary data can re-identify records after direct identifiers are removed. registry ↩