k-Anonymity

A dataset satisfies k-anonymity if each record is indistinguishable from at least k-1 other records with respect to a set of quasi-identifiers (QIDs). Quasi-identifiers are attributes like ZIP code, birth date, and gender that, when combined, can uniquely identify individuals. The value of k represents the minimum size of an equivalence class—a group of records sharing identical QID values. For example, in a 5-anonymous dataset, every combination of ZIP code, age, and gender must appear at least five times, ensuring an attacker cannot link a record to fewer than five individuals.

Quasi-identifiers are attributes that do not directly identify an individual but can be linked with external data to do so. Proper QID selection is critical:

• Explicit identifiers (name, SSN, email) must be removed or masked before publication
• Quasi-identifiers (ZIP code, age, race) must be generalized or suppressed
• Sensitive attributes (diagnosis, salary) are the protected values that remain in the dataset A landmark study found that 87% of the U.S. population is uniquely identifiable using only ZIP code, gender, and date of birth—making these classic quasi-identifiers.

Generalization replaces specific QID values with broader, less precise categories to create larger equivalence classes. This is achieved through domain generalization hierarchies:

• ZIP code 02138 → 0213* → 021** → 02***
• Age 27 → [25-30] → [20-40] → Adult
• Date of birth → Year only → Decade The higher the generalization level, the larger the equivalence class, but also the greater the information loss. Finding the optimal balance between privacy (k) and data utility is the central optimization problem in k-anonymity.

Suppression removes or masks outlier records that cannot be grouped into a sufficiently large equivalence class. Two common approaches:

• Tuple suppression: Entire records are removed from the published dataset if they are too unique
• Cell suppression: Individual cell values are replaced with a placeholder (e.g., '*') while retaining the rest of the record Suppression is often combined with generalization in algorithms like Datafly and Incognito, which iteratively generalize attributes and suppress remaining outliers until the k-anonymity threshold is met across all equivalence classes.

A critical limitation: k-anonymity does not protect against attacks on sensitive attribute diversity. If all records in an equivalence class share the same sensitive value, an attacker who knows a target is in that class learns the sensitive attribute with certainty—even if k is large. This is the homogeneity attack. For example, if all five individuals in a 5-anonymous group have the diagnosis 'HIV-positive,' knowing a target belongs to that group reveals their diagnosis. This weakness motivated the development of l-diversity, which requires diversity of sensitive values within each equivalence class.

Even with diverse sensitive values, k-anonymity is vulnerable to background knowledge attacks. If an attacker possesses external information that narrows the possible sensitive values for a target, re-identification becomes possible. For instance, if an equivalence class contains diagnoses of 'HIV-positive' and 'Flu,' and the attacker knows the target did not have the flu, the diagnosis is revealed. This led to the development of t-closeness, which requires the distribution of sensitive values in each equivalence class to closely mirror the overall dataset distribution, limiting what background knowledge can infer.

A set of non-sensitive attributes that, when combined, can uniquely identify an individual within a dataset. In a retail context, a combination of ZIP code, date of birth, and gender often serves as a quasi-identifier. k-Anonymity works by ensuring that every combination of quasi-identifier values appears at least k times in the released dataset, preventing linkage attacks that cross-reference these attributes with external public records like voter registries.

A core suppression technique that replaces specific attribute values with broader, less precise categories to achieve k-Anonymity.

• Numerical: Replacing exact age '27' with an interval '25-30'
• Hierarchical: Replacing a specific ZIP '94105' with a city-level 'San Francisco'
• Domain Generalization: Abstracting a product SKU to a product category The depth of generalization is controlled by a domain generalization hierarchy, balancing data utility against the required privacy threshold k.

The complementary technique to generalization where entire records or specific cell values are removed entirely from the dataset. Suppression is applied when generalization alone cannot achieve the desired k threshold without rendering the data meaningless. In identity graphs, outlier users with rare combinations of device types and browser fingerprints are often suppressed rather than over-generalized, preventing the release of a cohort that is too small to guarantee anonymity.

An extension of k-Anonymity that addresses the homogeneity attack. A k-anonymous group is l-diverse if it contains at least l well-represented distinct values for the sensitive attribute. For example, if all k users in a cohort share the same 'purchase category: high-end electronics,' an attacker who knows a target is in that cohort still learns their sensitive purchase behavior. l-Diversity ensures sensitive attribute variability within each anonymous group.

A further refinement that addresses the skewness attack possible under l-Diversity. t-Closeness requires that the distribution of a sensitive attribute within any k-anonymous group is within a threshold t of its global distribution across the entire dataset. If the global distribution of 'loyalty tier' is 70% Silver and 30% Gold, a t-close group must mirror this ratio. This prevents an attacker from gaining statistical knowledge about a target's likely sensitive value.

A mathematically rigorous alternative to k-Anonymity that provides a provable guarantee against re-identification. Instead of grouping records, differential privacy injects calibrated statistical noise into query results. A mechanism M satisfies ε-differential privacy if the probability of any output is nearly identical whether or not any single individual's record is included in the dataset. This is the standard used by the US Census Bureau and Apple for large-scale data collection, offering a stronger guarantee than syntactic anonymity models.