14.2 Pseudonymisation, Anonymisation, and Linkage Attacks: Removing Names Is Not Enough

Removing direct identifiers is usually a de-identification or pseudonymisation step, without automatically producing anonymous data. Identifiability depends on the data, recipient, available auxiliary information, and reasonably feasible attacks.

Learning Objectives

• Distinguish between direct identifiers, indirect identifiers, singling out, linkability, and inference;
• Understand the boundaries between masking, tokenization, encryption, generalization, and aggregation;
• Evaluate the risks associated with hashing, lookup tables, and external links;
• Design attack testing and establish ongoing reviews for data releases.

1. Identifying Without Knowing a Name

If a record can reliably distinguish one individual from others or has the potential to impact a specific person (even without knowing their real name) there may still be an identification risk.

Attack vectors include:

• Singling out: Isolating a particular individual’s record from a group;
• Linkability: Connecting multiple records or datasets that belong to the same person;
• Inference: Deducing sensitive attributes from known information;
• Re-identification: Linking de-identified records back to a real-world identity.

Combinations of precise timestamps, locations, age, rare events, and behavioral trajectories are often more dangerous than isolated data points.

2. Pseudonymisation and Anonymisation

Pseudonymisation separates direct identifiers from analytical data, allowing additional information to reassociate the data if needed. For example, a randomly generated token paired with a separately stored mapping table. While this reduces exposure and enables better control over linkage, it still generally falls under personal data protection requirements.

Anonymisation requires that, in a specific deployment context, no individual can reasonably be identified. The risk of identification varies significantly depending on the environment (such as public release, controlled research settings, or internal organizational use) and the nature of the attackers, auxiliary data, and access controls involved.

Do not treat "anonymised" as a one-time label. Changes in publicly available data, computational capabilities, recipient profiles, or data accumulation over time can alter identification risks. These require ongoing review and reassessment.

Identify the applicable framework when using these terms. GDPR Article 4(5) defines pseudonymisation, while Recital 26 considers reasonably likely means of identification; removing names cannot establish anonymity by itself. NIST SP 800-188 provides a technical and governance assessment reference, while legal classification depends on the actual processing context.

3. What Techniques Address What Problems

Masking

ali***@example.com may still identify someone. Masking can reduce interface exposure but does not establish anonymization.

Tokenisation

Replace identifiers with random tokens using a separate mapping table that is encrypted and strictly authorized. Random tokens do not reveal mathematical relationships between original identifiers, but if the mapping table is compromised, identities can be reconstructed.

Keyed Pseudonym

When deterministic joins are required, use MAC/HMAC schemes protected by cryptographic keys and isolate the keys. Avoid unkeyed hashes of small, enumerable identifier sets, which attackers can test offline. Design key rotation, scope, and cross-dataset linking policies accordingly.

Encryption

Encryption protects data at rest or in transit. Authorized decryption still reveals the original personal data, and deterministic encryption can expose equality patterns.

Generalisation / Suppression

Replace age with age ranges, location with regions, or remove rare records to reduce fine-grained linkage potential. However, this diminishes analytical utility and does not guarantee unidentifiability.

Aggregation

Publishing only group-level statistics reduces exposure at the row level. Still, small units, differencing queries, and multiple cross-tabulations can potentially leak sensitive information.

4. Why Truncating SHA-256 Is Not Tokenization

Calling sha256(user_id).hexdigest()[:16] an "irreversible token" ignores several problems:

• The user ID domain may be small and thus susceptible to brute-force enumeration;
• Identical inputs across tables produce identical outputs, increasing linkage risks;
• Truncation increases collision probability;
• There is no key or isolation boundary;
• Removing the original column does not affect other quasi-identifiers;
• The mapping cannot be securely rotated or revoked per subject.

The inability to reverse a hash to its original input does not mean attackers cannot guess the original value. A tokenization scheme must be designed from the ground up based on the attacker model and linkage requirements.

This example matches only 1,000 synthetic candidate identifiers; it does not break SHA-256. It then demonstrates scoped HMAC using a newly generated temporary key:

import hashlib
import hmac
import secrets

candidates = [f"synthetic-user-{i:03d}" for i in range(1000)]
target = "synthetic-user-042"
def short_hash(value):
    return hashlib.sha256(value.encode()).hexdigest()[:16]
lookup = {short_hash(value): value for value in candidates}
assert lookup[short_hash(target)] == target
print(lookup[short_hash(target)])
# synthetic-user-042

key = secrets.token_bytes(32)
def scoped_pseudonym(scope, identifier):
    message = scope.encode() + b"\x00" + identifier.encode()
    return hmac.new(key, message, hashlib.sha256).hexdigest()
assert scoped_pseudonym("study-a", target) == scoped_pseudonym("study-a", target)
assert scoped_pseudonym("study-a", target) != scoped_pseudonym("study-b", target)

Sixteen hexadecimal characters contain only 64 bits. HMAC preserves equality within a scope and does not hide other quasi-identifiers. Anyone holding the key or able to query the mapping service in bulk can still test candidate IDs. Production needs controlled key storage, versioning, and access; temporary-key code is not a key service. Scope and ID here exclude null bytes; general inputs need unambiguous encoding. See Python hmac.

5. Boundaries of Models like k-anonymity

k-anonymity aims to ensure that every combination of quasi-identifiers appears in at least k records. It can help identify unique combinations, but:

• When sensitive values are identical within a group, attribute disclosure can still occur;
• An attacker’s background knowledge can still narrow down the search space;
• High-dimensional data forces extensive generalization;
• It does not address repeated releases or composite queries;
• There is no universally applicable value of k that fits all scenarios.

Extensions like l-diversity and t-closeness alleviate some of these issues, but they still rely on quasi-identifiers and assumptions about attacker knowledge. Evaluation must be tailored to specific recipients and dissemination methods.

These three rows represent distinct synthetic people. The age-band/region equivalence class satisfies k=3, but has only one disciplinary-flag value:

from collections import defaultdict

rows = [
    {"age_band": "30-39", "region": "north", "disciplinary_flag": True},
    {"age_band": "30-39", "region": "north", "disciplinary_flag": True},
    {"age_band": "30-39", "region": "north", "disciplinary_flag": True},
]
groups = defaultdict(list)
for row in rows:
    groups[(row["age_band"], row["region"])].append(row["disciplinary_flag"])
print([(len(values), len(set(values))) for values in groups.values()])
# [(3, 1)]

An attacker who knows someone belongs to this class can infer the flag without identifying the person’s exact row. Three matching quasi-identifiers do not imply a one-in-three disclosure probability.

6. Synthetic Data Might Also Remember Individuals

Synthetic data can reduce direct replication, but generative models may still memorize training samples, especially rare records or conditional queries that could leak sensitive information. Validation should include:

• Nearest neighbors and duplicates relative to training records;
• Membership and attribute inference risks;
• Rare groups and extreme values;
• Downstream utility and group bias;
• Whether the generation method provides provable privacy guarantees.

"Synthetic" describes the generation method, not the privacy level.

Passing nearest-neighbor or membership tests only means the tested attacks did not succeed; it is not a mathematical privacy proof. For DP generation, verify the actual training mechanism, contribution bounds, and budget. Public release also makes complete recall of copies difficult, so document recall limits honestly.

7. The Release Environment Determines Control Strength

Public Release

Once data can be downloaded publicly, recipients and later linkage are outside the publisher’s control. Reduce detail or apply a validated privacy mechanism before release. If query limits are necessary, retain the data behind a controlled interface; those limits cannot govern copies already downloaded.

Controlled Sharing

Can be combined with contracts, identity verification, isolated environments, output validation, link prohibition, auditing, and erasure proofs. Organizational controls reduce risk, but cannot replace technical minimization.

Internal Use

Insiders, copied logs, and expanding permissions remain threats. Separate control of pseudonym mappings from analytical access, and do not provide re-identification paths by default.

8. Re-identification Risk Assessment

1. Clearly define the published data, recipients, and permitted uses
2. List direct and indirect identifiers and inferable attributes
3. Inventory accessible auxiliary data and potential attack capabilities
4. Test singling out, linkability, and inference attacks
5. Apply transformations and organizational controls
6. Reassess utility, group impact, and residual risk
7. Independently review and document the data release decision
8. Monitor environmental changes, revocations, and expiration dates

Controlled re-identification testing requires explicit authorization and a secure environment; do not expose real data to unauthorized "red team" attempts.

Common Misconceptions

• Deleting a name means anonymity: Trajectories and quasi-identifiers can still be used to re-identify individuals.
• Hashing is irreversible, so it's secure: Enumerated inputs can be attacked using dictionary-based methods.
• Internal data doesn’t require anonymization risk assessment: Internal systems often have broader linking capabilities.
• Synthetic data inherently contains no personal information: Models may replicate or leak training samples.

Exercise

1. List examples of singling out, linkability, and inference attacks against a trajectory table.
2. Compare the linkage and keying risks associated with unkeyed hash functions, HMAC, and random tokens.
3. Construct a homogeneity attack against a k-anonymous table.
4. Design controls for both public release and controlled research environments, and explain the differences between them.

Summary

De-identification is a risk mitigation process, not a permanent labeling action achieved by simply removing a few columns. Whether a technique is effective must be evaluated in context, considering the recipient, auxiliary information, the purpose of the linkage, and changes in feasible attacks.

The next lesson introduces a different approach: differential privacy does not attempt to hide the appearance of individual rows. Instead, it limits the impact of any single person's addition or removal on the distribution of the published data.