8.2 De-identification and Privacy Risks: Pseudonymity, Anonymity, and Differential Privacy

Removing names and email addresses only eliminates direct identifiers. Time, location, occupation, device information, and behavioral patterns can still uniquely point to an individual. The more comprehensive external datasets become, the easier it becomes to re-identify individuals.

Pseudonymization Preserves Linkability

person_id 42 → random pseudonym 7f8c...
mapping table stored independently and strictly authorized

Pseudonymization reduces the risk of direct identification during everyday use, enabling identity rotation and role separation. However, as long as an organization or other party can reassociate identities through the mapping table, stable patterns, or auxiliary data, this generally remains personal-data processing.

Do not treat an ordinary hash without a secret key as email anonymization: attackers can enumerate common or known candidate addresses and compare digests. Public salts do not prevent guessing each record. If stable tokens are required, use controlled keyed constructions, purpose-bound separation, and rotatable mapping services. Sharing the same stable pseudonym across different datasets increases cross-database linkage risks.

Anonymization Is a Conclusion About Reasonable Re-identification Risk

Anonymization is not a single function name; it's a risk assessment derived from the data itself, the way it's published, the attacker's capabilities, and the potential for future auxiliary information. Common attack vectors include:

• Singling out: Combining fields to uniquely identify a single record;
• Linkability: Associating records across datasets to identify the same individual;
• Inference: Inferring sensitive attributes from non-sensitive fields;
• Membership inference: Determining whether a specific individual is present in the dataset.

K-anonymity requires at least k records in each group defined by the chosen quasi-identifiers. Missing or incorrectly chosen quasi-identifiers undermine that conclusion. It does not alone address attribute homogeneity, background knowledge, or differencing across releases. A dataset may appear anonymous in isolation, but when combined with other data, re-identification risks can still emerge.

For example, a release contains two people of the same age and region, both with the same diagnosis. Grouping by age and region satisfies k=2, yet knowing that someone belongs to this group reveals their diagnosis. A sufficient group size does not ensure uncertainty about the sensitive attribute.

Risk mitigation strategies include generalization, binning, suppression of rare combinations, sampling, aggregation, and controlled query environments. Data utility and risk must be evaluated through real-world analytical use cases, rather than by counting deleted columns alone.

Differential Privacy Limits Individual Marginal Impact

Intuitively, adding or removing one person's contribution should not greatly change the output distribution. For every neighboring pair D, D' and output event S, (ε, δ)-differential privacy requires:

$$Pr[M(D)\in S]\le e^{\epsilon }Pr[M(D^{\prime })\in S]+\delta$$

The probability comes from the randomness of mechanism M. ε bounds a multiplicative probability difference; δ provides additive slack. Setting δ=0 gives pure differential privacy. This does not place one universal probability bound on every real-world harm.

Differential privacy is not "just add noise." Implementation requires:

1. Defining adjacent datasets and protected units, such as a row, a user, or a household;
2. Limiting how many times a single entity can contribute and the range of values they can provide;
3. Computing the sensitivity of each query;
4. Selecting a provably private mechanism;
5. Account for composition across queries and consume the privacy budget accordingly;
6. Protecting the privacy budget ledger, original data, and query interface.

Consider an idealized participant count. Each person contributes at most 1, and neighbors differ by adding or removing one participant. Sensitivity is Δf=1, so a Laplace mechanism uses scale b=Δf/ε. With ε=0.5, b=2 and about 95% of noise lies within ±5.99 people. If each person can contribute 10 records without deduplication, the original sensitivity no longer holds. Use reviewed privacy libraries in production: floating-point sampling and other implementation details can undermine the ideal mathematical guarantee.

Ten fresh releases on the same population, each using a pure-DP mechanism with ε=0.5, have a basic sequential-composition bound of ε=5. Repeatedly displaying the same released result is post-processing and consumes no additional budget. Fresh independent noise each day can be averaged down if composition is ignored. ε is not a universal "safe threshold" across products; it must be tailored to the use case, population risk, publication frequency, and acceptable utility.

Aggregated Data Can Also Harm Groups

Even when individuals cannot be identified, statistical results may lead to discrimination, exclusion, or price manipulation against certain small groups. Privacy risk assessments should ask:

Which data actions could cause problems for individuals or groups?
What is the likelihood and severity of those impacts?
What value does the organization derive from processing the data?
Can the use, granularity, access, or retention be modified to reduce risk?

This differs from a purely security threat model: an organization executing data processing may have full authorization, yet the harm still stems from the nature of the data handling itself.

Model and Analysis Environments Require Independent Review

Deleting training data does not automatically remove it from trained models. Models may retain rare samples, and embeddings or feature stores might leak sensitive relationships. It's essential to document dataset lineage, training objectives, versions, access patterns, retention policies, and strategies for retraining or retirement. These should be accompanied by testing for membership inference, model inversion, and output-sensitive information disclosure.

A controlled research environment should employ minimal data views, prohibit raw data exports, enable query auditing, and require output disclosure reviews. Distributing purportedly anonymous downloads to every analyst loses visibility and control over subsequent copying, sharing, and cross-dataset combination.

Risk Assessment Evidence

• What are the direct and quasi-identifiers, and what auxiliary data is externally available?
• Are pseudonym mapping and token keys independently protected and rotatable?
• Are unique combinations, rare cohorts, and multi-release scenarios tested before deployment?
• Is differential privacy clearly defined in terms of protection units, contribution bounds, and budget ledger?
• Do data, features, models, and derived statistics maintain lineage?
• Can access patterns shift from raw data downloads to controlled queries?
• When are risk conclusions re-evaluated due to new data or emerging attack capabilities?

The next chapter puts these constraints into the delivery pipeline so security and privacy checks run with each change.

References

• NIST, De-Identification of Personal Information
• NIST, Privacy Engineering Program
• NIST, SP 800-226: Guidelines for Evaluating Differential Privacy Guarantees