mukul975 Assessing Pseudonymization and Re-Identification Risk
Overview
Pseudonymization (GDPR Article 4(5)) means processing personal data in such a manner that the data can no longer be attributed to a specific data subject without the use of additional information, provided that such additional information is kept separately and is subject to technical and organisational measures to ensure non-attribution. Unlike anonymization (Recital 26), pseudonymized data remains personal data — but it significantly reduces risk and is explicitly recognized as an appropriate safeguard under Articles 25, 32, and 89.
The ENISA report "Pseudonymisation Techniques and Best Practices" (November 2019) provides a comprehensive taxonomy of pseudonymization techniques and their properties. This skill implements a structured assessment framework for selecting appropriate techniques and quantifying residual re-identification risk.
Pseudonymization Techniques Taxonomy
Technique 1: Counter-Based Pseudonyms
| Property | Value |
|---|---|
| Mechanism | Sequential or random counter assigned to each identifier |
| Reversibility | Reversible via lookup table |
| Collision resistance | Guaranteed (bijective mapping) |
| Performance | O(1) lookup |
| Storage overhead | Mapping table size proportional to identifier count |
| Key management | Protect the mapping table as additional information |
Prism Data Systems AG Implementation: Customer IDs are replaced with UUIDv4 pseudonyms at the analytics ingestion boundary. The mapping table is stored in a separate HSM-backed database accessible only to the DPO and the identity resolution service (which requires dual-approval access).
Technique 2: Cryptographic Hashing (HMAC)
| Property | Value |
|---|---|
| Mechanism | HMAC-SHA256 with secret key applied to identifier |
| Reversibility | Not directly reversible; vulnerable to brute-force on low-entropy inputs |
| Collision resistance | Negligible collision probability (256-bit output) |
| Performance | O(1) computation |
| Storage overhead | Fixed 32-byte output per identifier |
| Key management | HMAC key must be protected as additional information |
Risk: Plain SHA-256 hashing (without key) is vulnerable to rainbow table attacks on low-entropy identifiers like email addresses. HMAC with a secret key mitigates this but the key becomes the single point of re-identification.
Prism Data Systems AG Implementation: HMAC-SHA256 with a 256-bit key rotated quarterly is used for pseudonymizing user identifiers in the analytics pipeline. The HMAC key is stored in AWS KMS with access restricted to the pseudonymization service account. Key rotation triggers re-pseudonymization of the active analytics dataset.
Technique 3: Encryption-Based Pseudonymization
| Property | Value |
|---|---|
| Mechanism | AES-256-GCM or format-preserving encryption (FF1/FF3-1) |
| Reversibility | Fully reversible with decryption key |
| Collision resistance | Guaranteed (bijective for same key) |
| Performance | O(1) computation; FPE slower than standard AES |
| Storage overhead | Ciphertext size ≈ plaintext + 16-byte tag (GCM) |
| Key management | Encryption key is the additional information per Art. 4(5) |
Format-Preserving Encryption preserves the format of the original identifier (e.g., encrypting a 10-digit phone number produces another 10-digit number), enabling pseudonymization without schema changes.
Prism Data Systems AG Implementation: FPE (FF3-1 mode) is used for pseudonymizing phone numbers and IBAN fields in the support ticket system. This allows Tier 1 support agents to see structurally valid but pseudonymized identifiers, reducing accidental exposure while maintaining workflow compatibility.
Technique 4: Tokenization
| Property | Value |
|---|---|
| Mechanism | Random token generated and stored in a secure vault; no mathematical relationship to original |
| Reversibility | Reversible only via vault lookup |
| Collision resistance | Guaranteed by vault uniqueness constraint |
| Performance | O(1) vault lookup; network latency for centralized vault |
| Storage overhead | Vault stores original-to-token mapping |
| Key management | Vault access controls replace key management |
Prism Data Systems AG Implementation: Payment card data is tokenized using a PCI DSS-compliant token vault. The vault is operated by the payment processor and is logically separated from Prism's infrastructure. Detokenization requires a PCI-scoped service account with transaction-level authorization.
Technique 5: Synthetic Data Replacement
| Property | Value |
|---|---|
| Mechanism | Replace real identifiers with structurally similar but fictional values |
| Reversibility | Not reversible (one-way replacement) |
| Collision resistance | Depends on generation method; risk of accidental collision with real data |
| Performance | O(1) generation |
| Storage overhead | No mapping table needed (irreversible) |
| Key management | Not applicable |
Use case: Test environments where referential integrity must be maintained but no re-identification path is acceptable.
Technique Comparison Matrix
| Criterion | Counter | HMAC | Encryption | Tokenization | Synthetic |
|---|---|---|---|---|---|
| Reversibility | Lookup table | Brute-force only | Decryption key | Vault lookup | Irreversible |
| Deterministic | Configurable | Yes (same key) | Yes (same key+IV) | Configurable | No |
| Format preserving | No | No | FPE only | Configurable | Yes |
| Linkability (same dataset) | Yes | Yes | Yes | Configurable | No |
| Linkability (cross-dataset) | No | Same key: Yes | Same key: Yes | No | No |
| Brute-force resistance | N/A | Key-dependent | Key-dependent | N/A | N/A |
| Suited for analytics | Yes | Yes | Limited | Yes | Limited |
| Suited for testing | No | No | No | Yes | Yes |
| ENISA recommendation level | Basic | Intermediate | Advanced | Advanced | Specialized |
Re-Identification Risk Assessment Framework
The Motivated Intruder Test
The UK Information Commissioner's Office (ICO) Anonymisation Code of Practice defines the motivated intruder test: would a reasonably competent, motivated person with access to resources such as the internet, public libraries, and public records be able to identify an individual from the pseudonymized data?
Assessment Factors:
| Factor | Low Risk (1) | Medium Risk (3) | High Risk (5) |
|---|---|---|---|
| Population uniqueness | Common attributes, large equivalence classes | Moderate uniqueness, some rare combinations | Highly unique attribute combinations |
| Auxiliary information availability | No public datasets linkable | Some public records overlap | Rich public profiles (social media, registers) |
| Identifier entropy | High entropy (e.g., UUID) | Medium entropy (e.g., hashed email) | Low entropy (e.g., hashed phone number) |
| Dataset richness | Few quasi-identifiers | Moderate quasi-identifiers (5-10) | Many quasi-identifiers (>10) |
| Temporal precision | Yearly or coarser | Monthly | Daily or finer |
| Geographic precision | Country level | Region/city level | Postcode or finer |
| Domain sensitivity | Low sensitivity domain | Moderate sensitivity | Health, financial, political data |
Quantitative Risk Models
Prosecutor Model
The attacker knows a specific individual is in the dataset and attempts to find their record. Risk = 1 / k, where k is the size of the equivalence class containing the target record.
Journalist Model
The attacker does not know if the target is in the dataset but attempts to re-identify any individual for a story. Risk = max(1/k) across all equivalence classes (the smallest group is most vulnerable).
Marketer Model
The attacker attempts to re-identify as many individuals as possible. Risk = (1/n) * Σ(1/k_i) — the average re-identification probability across all records.
Linkage Attack Categories
| Attack Type | Description | Mitigation |
|---|---|---|
| Record linkage | Matching pseudonymized records with identified records in external datasets using quasi-identifiers | Generalize quasi-identifiers, enforce k-anonymity |
| Attribute linkage | Inferring sensitive attributes from group characteristics even without identifying the individual | Enforce l-diversity on sensitive attributes |
| Table linkage | Determining that an individual is present in a sensitive dataset (membership inference) | Apply differential privacy, enforce t-closeness |
| Composition attack | Combining multiple independent pseudonymized releases to narrow equivalence classes | Track cumulative privacy budget, limit releases |
| Temporal linkage | Linking records across time periods using behavioral patterns or trajectory data | Apply temporal generalization, add noise to timestamps |
Risk Scoring Methodology
Step 1: Technique Assessment (0-100)
Score the pseudonymization technique on five properties:
| Property | Weight | Score Range |
|---|---|---|
| Key/mapping security | 30% | 0-100 based on key management maturity |
| Brute-force resistance | 25% | 0-100 based on input entropy and computational cost |
| Cross-dataset unlinkability | 20% | 0-100 based on determinism and key reuse |
| Implementation maturity | 15% | 0-100 based on library validation and audit history |
| Operational resilience | 10% | 0-100 based on key rotation, backup, disaster recovery |
Step 2: Data Environment Assessment (0-100)
Score the data environment on re-identification risk factors:
| Factor | Weight | Score Range |
|---|---|---|
| Population uniqueness | 25% | 0-100 (higher = more unique = higher risk) |
| Auxiliary data availability | 25% | 0-100 (higher = more auxiliary data = higher risk) |
| Quasi-identifier count | 20% | 0-100 based on number and granularity |
| Dataset size | 15% | 0-100 (smaller datasets = higher risk per record) |
| Release frequency | 15% | 0-100 (more frequent releases = higher composition risk) |
Step 3: Residual Risk Score
Residual Risk = Data Environment Risk × (1 - Technique Score / 100)
| Residual Risk Range | Classification | Action Required |
|---|---|---|
| 0-15 | Low | Acceptable. Document and monitor |
| 16-35 | Moderate | Additional controls recommended |
| 36-60 | High | Technique upgrade or data reduction required |
| 61-100 | Very High | Processing should not proceed without anonymization |
Prism Data Systems AG — Assessment Summary
| Data Flow | Technique | Technique Score | Environment Risk | Residual Risk | Classification |
|---|---|---|---|---|---|
| Analytics pipeline | HMAC-SHA256 (keyed) | 78 | 42 | 9.2 | Low |
| Support dashboard | FPE (FF3-1) | 82 | 35 | 6.3 | Low |
| Payment processing | Tokenization (vault) | 91 | 55 | 5.0 | Low |
| Test environments | Synthetic replacement | 95 | 20 | 1.0 | Low |
| Research exports | Counter + k-anonymity | 72 | 58 | 16.2 | Moderate |
| ML training data | HMAC + differential privacy | 85 | 48 | 7.2 | Low |
The research exports flow received a "Moderate" classification due to the combination of rich quasi-identifiers in the exported dataset and the counter-based technique's susceptibility to record linkage. Remediation: apply l-diversity (l≥3) on sensitive attributes and generalize quasi-identifiers to achieve k≥11 before export.
Key Regulatory References
- GDPR Article 4(5) — Definition of pseudonymization
- GDPR Recital 26 — Anonymization vs. pseudonymization distinction
- GDPR Article 25(1) — Pseudonymization as a data protection by design measure
- GDPR Article 32(1)(a) — Pseudonymization as a security measure
- GDPR Article 89(1) — Pseudonymization for research processing safeguards
- ENISA "Pseudonymisation Techniques and Best Practices" (November 2019)
- ICO Anonymisation Code of Practice — Motivated intruder test
- Article 29 Working Party Opinion 05/2014 (WP216) on Anonymisation Techniques
- EDPB Guidelines 4/2019 on Article 25 — Pseudonymization as by-design measure