Quasi-Identifier (QID)

A single quasi-identifier is rarely identifying on its own. The privacy risk emerges from the intersection of multiple attributes. An adversary links QIDs across datasets using a linkage key formed by concatenating attributes like ZIP code, gender, and date of birth. This is the foundational principle behind re-identification attacks demonstrated by Sweeney and others, where over 87% of the U.S. population becomes unique using only three attributes.

An attribute's status as a quasi-identifier is not intrinsic; it depends entirely on the availability of external datasets. A diagnosis code might be a QID in a small town with a public health registry but not in a large anonymized metropolitan dataset. This requires privacy engineers to perform adversarial modeling against known auxiliary data sources like voter rolls, property records, and social media profiles.

The identifying power of a QID is inversely proportional to its granularity. A full date of birth is far more identifying than a birth year. De-identification techniques like generalization and suppression systematically reduce granularity to create equivalence classes of size k. The goal is to ensure each record is indistinguishable from at least k-1 others, directly addressing the singling-out risk.

Unlike passwords or tokens, most quasi-identifiers are immutable or slowly changing over a lifetime. Date of birth, place of birth, and ethnicity are permanent. This temporal persistence means a de-identified dataset released today remains vulnerable to future re-identification as new auxiliary datasets become available. Privacy budgets must account for this long-term risk horizon.

In privacy models like k-anonymity and l-diversity, a strict logical separation exists between QIDs and sensitive attributes. QIDs are the attributes available to an adversary for linkage, while sensitive attributes like medical conditions or salaries are what the adversary seeks to discover. This distinction is critical: protecting QIDs prevents re-identification, while protecting sensitive attributes prevents attribute disclosure within an identified equivalence class.

Even when individual QIDs are generalized, the joint distribution of attributes can create a unique fingerprint. A combination of rare attributes—even in broad categories—can single out an individual. This is the attack vector addressed by t-closeness, which requires the distribution of sensitive values within any equivalence class to mirror the overall dataset distribution, preventing skewness attacks that exploit statistical outliers.

A foundational privacy model that ensures each record in a dataset is indistinguishable from at least k-1 other records with respect to the set of quasi-identifiers. This is achieved through generalization (replacing specific values with ranges) and suppression (removing outlier records). The primary goal is to prevent singling out an individual, though it does not inherently protect against attribute disclosure if all k records share the same sensitive value.

A direct extension of k-anonymity designed to patch the homogeneity attack. It requires that each k-anonymous equivalence class contains at least l 'well-represented' values for the sensitive attribute. Variants include:

• Distinct l-diversity: Ensures at least l distinct sensitive values per group.
• Entropy l-diversity: Requires the entropy of the sensitive attribute distribution to meet a minimum threshold.
• Recursive (c,l)-diversity: Ensures the most frequent value does not dominate the group.

A privacy model that refines l-diversity by addressing skewness attacks. It mandates that the distribution of a sensitive attribute within any quasi-identifier equivalence class must not differ from its global distribution in the entire dataset by more than a threshold t. The distance between distributions is typically measured using the Earth Mover's Distance (EMD). This prevents an attacker from learning that a specific group has a statistically anomalous prevalence of a sensitive trait.

A structured taxonomy used to transform specific quasi-identifier values into broader, less precise categories to achieve k-anonymity. For example:

• Age: 37 → Age Range: 30-40 → Age Category: Adult
• ZIP Code: 90210 → 9021* → 902** → 90*** The hierarchy defines a Domain Generalization Graph, allowing algorithms to find the optimal balance between privacy (higher generalization) and data utility (lower generalization).

A disclosure control technique involving the complete removal of an entire column or attribute from a dataset. This is applied when a quasi-identifier poses an unacceptably high re-identification risk and cannot be sufficiently protected through generalization alone, or when the attribute is not essential for the intended analysis. In contrast, cell suppression selectively hides only specific values in tabular data to prevent exact inference of sensitive contributions.

The calculated probability that an adversary can successfully link de-identified records back to specific individuals by matching quasi-identifiers with auxiliary datasets (e.g., voter rolls, public social media). Key metrics include:

• Prosecutor Risk: The probability of re-identifying a specific target individual.
• Journalist Risk: The probability that any record in the released dataset can be re-identified.
• Marketer Risk: The proportion of records that can be matched to an external file with high confidence.