De-identification Models such as k-Anonymity

De-identification Models such as k-Anonymity (CDPSE – Privacy Engineering)

Overview
De-identification models are formal, measurable techniques used to transform personal data so that individuals cannot reasonably be re-identified, while the data stays useful for analytics, research, testing or sharing. For the ISACA CDPSE exam, this topic sits within Privacy Engineering, the domain about building privacy into data, systems and architecture. You are expected to know the main models, which threat each one addresses, their limitations, and how they fit into a risk-based privacy program.

Why It Is Important
1. Removing names is not enough. Research by Latanya Sweeney showed that about 87% of the US population can be uniquely identified using only ZIP code, date of birth and gender. These indirect identifiers are called quasi-identifiers. Simply deleting names gives a false sense of safety.
2. Regulatory alignment. Several laws treat de-identified data differently from personal data:
• GDPR distinguishes truly anonymous data, which is out of scope, from pseudonymised data, which is still personal data.
• HIPAA defines Safe Harbor and Expert Determination methods.
• CCPA/CPRA defines "deidentified" information.
Formal models help demonstrate that the anonymization is defensible.
3. Data minimization and privacy by design. De-identification lets organizations get value from data while reducing risk and breach impact.
4. Balancing utility and privacy. Stronger privacy usually reduces data utility. Measurable models let privacy engineers make a documented trade-off instead of guessing.
5. Third-party sharing and secondary use. Data released to researchers, vendors or the public must withstand linkage attacks that combine it with external datasets.

What It Is: Key Concepts and Terminology
• Direct identifiers: attributes that identify a person on their own, such as name, SSN, email or phone number. These are usually removed or replaced with pseudonyms.
• Quasi-identifiers (QIs): attributes that identify someone when combined or linked with other data, such as ZIP code, birth date, gender, occupation or ethnicity.
• Sensitive attributes: the information you want to protect, such as diagnosis, salary or religion.
• Equivalence class: a group of records that share identical values for all quasi-identifiers.
• Re-identification risk: the probability that a record can be linked back to an individual.
• Pseudonymization vs. anonymization:
– Pseudonymization replaces identifiers with tokens. It is reversible with additional information, so the data remains personal data.
– Anonymization is irreversible: individuals are no longer identifiable by any means reasonably likely to be used.

The Main De-identification Models

1. k-Anonymity (Samarati and Sweeney, 1998)
• Definition: a dataset is k-anonymous if every record is indistinguishable from at least k-1 other records on its quasi-identifiers. Every equivalence class therefore has at least k records.
• Protects against: identity disclosure and record linkage. The chance of singling out a person by linking QIs is at most 1/k.
• Example with k=3:
– Before: (ZIP 02138, Age 34, Female, Flu)
– After: (ZIP 021**, Age 30-39, Female, Flu)
– At least two other records now share "021**, 30-39, Female."
• Weaknesses:
– Homogeneity attack: if all k records share the same sensitive value (for example, all have cancer), the attacker learns the diagnosis without knowing which row is the target.
– Background knowledge attack: outside knowledge can rule out some values.
– Performs poorly on high-dimensional data, the "curse of dimensionality."

2. l-Diversity (Machanavajjhala et al., 2006)
• Definition: each equivalence class must contain at least l "well-represented" distinct values for each sensitive attribute.
• Protects against: attribute disclosure, specifically the homogeneity and background knowledge attacks that defeat k-anonymity.
• Weaknesses:
– Skewness attack: a class may be diverse but still far more concentrated than the overall population.
– Similarity attack: the distinct values may be semantically similar, such as gastric ulcer, gastritis and stomach cancer, which all reveal a stomach problem.

3. t-Closeness (Li et al., 2007)
• Definition: the distribution of a sensitive attribute in each equivalence class must be within a distance t of its distribution in the whole dataset, typically measured with Earth Mover's Distance.
• Protects against: skewness and similarity attacks. It limits how much an attacker learns beyond what the overall population already reveals.
• Weakness: it can severely reduce data utility.

4. Differential Privacy (DP) (Dwork, 2006)
• Definition: a mathematical guarantee that the output of an analysis is nearly the same whether or not any single individual's data is included. It is controlled by the privacy budget epsilon (ε): a smaller ε means stronger privacy but less accuracy.
• How it works: calibrated random noise, such as Laplace or Gaussian noise, is added to query results or to the data itself (local DP).
• Strengths:
– Resistant to linkage and background knowledge attacks regardless of what the attacker knows.
– Composable, so cumulative privacy loss can be tracked.
• Used by: the US Census Bureau (2020 Census), Apple and Google.
• Weakness: results are less accurate, and the budget is consumed across repeated queries.

Related models:
• δ-presence protects against membership disclosure, that is, revealing whether a person is in the dataset at all.
• km-anonymity applies to transactional data.
• Synthetic data generates artificial records that preserve statistical properties.

How It Works: Techniques Used to Achieve the Models
• Generalization: replace values with broader categories, such as age 34 becoming 30-39, or ZIP 02138 becoming 021**. A generalization hierarchy defines the levels.
• Suppression: remove outlier records or specific cell values that would create small equivalence classes.
• Masking and redaction: hide all or part of a value.
• Perturbation and noise addition: alter values slightly, as in differential privacy.
• Data swapping: exchange values between records.
• Aggregation: release only summary statistics, often with minimum cell sizes.
• Tokenization and hashing: replace direct identifiers. Note that this is pseudonymization, not anonymization. Unsalted hashes of small value sets can be reversed.
• Top and bottom coding: cap extreme values, such as "age 90+" or "income above $250k."

A Typical De-identification Process
1. Define the purpose, data recipients and release model (public, controlled or internal).
2. Inventory and classify attributes as direct identifiers, quasi-identifiers, sensitive or non-sensitive.
3. Remove or pseudonymize direct identifiers.
4. Assess re-identification risk. Consider the threat model: prosecutor, journalist or marketer attacker.
5. Select the model and parameters (k, l, t or ε) based on risk tolerance and context.
6. Apply the transformations: generalization, suppression and noise.
7. Measure residual risk and data utility. Iterate if needed.
8. Document the decisions and apply controls: data use agreements, access controls and prohibition of re-identification attempts.
9. Monitor and reassess periodically, because new external datasets and techniques increase risk over time.

Choosing Parameters
• A higher k gives stronger protection but less utility.
• Values of k between 5 and 11 are common in health data. Some agencies use minimum cell sizes of 10 or 11.
• Public releases need stricter parameters than controlled, contract-bound releases.

Exam Tips: Answering Questions on De-identification Models such as k-Anonymity

1. Know which attack each model solves.
• k-anonymity addresses identity disclosure and linkage.
• l-diversity addresses the homogeneity attack and attribute disclosure.
• t-closeness addresses skewness and similarity attacks.
• Differential privacy offers mathematical guarantees independent of background knowledge.
If a question describes "all records in a group have the same diagnosis," the answer points to l-diversity as the fix.

2. Understand the meaning of k.
• Each record is indistinguishable from at least k-1 others.
• The maximum re-identification probability is 1/k.
• Watch for distractors such as "k records are removed" or "k attributes are masked."

3. Pseudonymization is not anonymization.
• Tokenized or hashed data that can be re-linked with a key is still personal data under GDPR.
• Exam questions frequently test this distinction.

4. Removing direct identifiers alone is insufficient.
• When an answer choice says "remove names and SSNs," look for a better option that addresses quasi-identifiers or re-identification risk assessment.

5. Think risk-based and context-based.
• CDPSE favors answers that start with assessing re-identification risk, the purpose, the data recipients and the threat model before applying a technique.
• The best answer is often "perform a re-identification risk assessment" or "determine the intended use."

6. Remember the utility trade-off.
• More generalization means more privacy but less utility.
• If a question asks for the primary drawback of increasing k or decreasing ε, the answer is reduced data utility or accuracy.

7. Technical and administrative controls work together.
• De-identification should be combined with contracts or data use agreements prohibiting re-identification, access controls, and periodic reassessment.
• Answers that pair technical and governance controls are often correct.

8. Recognize the techniques by name.
• Generalization: ranges and truncation.
• Suppression: removal of values or records.
• Perturbation: adding noise.
• Know which ones underpin k-anonymity (generalization and suppression) and which underpins differential privacy (noise).

9. Remember that de-identification is not permanent.
• New auxiliary datasets increase linkage risk, so de-identified datasets must be reassessed over time.
• Questions may ask what to do after a new public dataset is released. The answer is to reassess re-identification risk.

10. Know where differential privacy fits best.
• It suits repeated statistical queries and large-scale aggregate releases.
• Expect keywords such as "privacy budget," "epsilon," "noise," and "guarantee regardless of attacker knowledge."

11. Use elimination.
• Discard answers that claim absolute or zero risk, or that treat encryption as de-identification. Encryption protects confidentiality, but the data remains identifiable to key holders.
• Also discard answers that ignore data utility entirely.

Sample Question Walkthrough
Q: A hospital released a 5-anonymous dataset. An analyst discovered that, in one equivalence class, all patients had HIV. Which model would BEST address this issue?
A) Increase k to 10
B) Apply l-diversity
C) Hash patient IDs
D) Encrypt the dataset

Answer: B.
• This is a homogeneity attack, a form of attribute disclosure.
• l-diversity requires diverse sensitive values within each class.
• Increasing k does not guarantee diversity.
• Hashing and encryption do not address the problem.

Quick Memory Aid
• k = "Konfusion": you are hidden in a crowd of k.
• l = "Lots of values": the crowd has varied secrets.
• t = "Typical distribution": the crowd's secrets look like the overall population's.
• ε = "Everyone or not, same answer": your presence barely changes the output.

Summary
De-identification models give privacy engineers measurable ways to reduce re-identification risk. k-anonymity hides individuals in groups. l-diversity and t-closeness protect sensitive attributes within those groups. Differential privacy provides strong mathematical guarantees through noise. For the CDPSE exam, focus on:
• which attack each model mitigates
• the difference between pseudonymization and anonymization
• the privacy–utility trade-off
• the need for risk assessment, governance controls and ongoing reassessment