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

The Prediction Chamber removes names and replaces personnel IDs with SHA-256 hashes before sending the analysis dataset to external researchers. The recipient possesses a dictionary of personnel identifiers and quickly reverses the hash to recover the original ID. Even without such a dictionary, they can link identities using precise location data, shift schedules, and rare events.

Eliminating direct identifiers is typically just a step of pseudonymisation or de-identification, this does not automatically produce truly anonymous data. Whether data remains identifiable depends on the dataset itself, the recipient, available auxiliary information, and the feasibility of a reasonable and practical attack.

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: Re-linking anonymized data 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.

3. What Techniques Address What Problems

Masking

ali***@example.com Still directly references individuals and is suitable for interfaces that display minimal information, this is not 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 applying unkeyed hash functions directly to small, enumerable numbers, attackers could offline guess values. Design key rotation, scope, and cross-dataset linking policies accordingly.

Encryption

Protects static or in-transit data, with decryption authorized only to authorized parties, and the original personal data remains accessible. Deterministic encryption can still reveal patterns of equality.

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, differential queries, and multiple cross-tabulations can potentially leak sensitive information.

4. Why Truncating SHA-256 Is Not Tokenization

The original draft referred to sha256(user_id)[:16] as an "irreversible token." Key issues include:

• 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.

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.

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.

7. The Release Environment Determines Control Strength

Public Release

No control over recipients or future links, typically requiring the strongest measures such as coarse-grained access reduction, query restrictions, or formal privacy guarantees.

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

Internal personnel, log replication, and permission propagation remain threats. Pseudonym mapping should be governed by separate responsibilities, and analysis environments should not inherently provide re-identification pathways.

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 the evolving threat landscape.

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.