k-anonymity: hiding each record among at least k

k-anonymity is a privacy rule for released data: each person’s record must be indistinguishable from at least k minus 1 other records on the attributes someone could use to identify them. Latanya Sweeney’s 2002 paper states that “a release provides k-anonymity protection if the information for each person contained in the release cannot be distinguished from at least k-1 individuals whose information also appears in the release.” It defends against simple linkage, but known attacks can still defeat it.

Definition

Sweeney’s definition, quoted above, rests on the idea of a quasi-identifier: a set of attributes that are not names but can be combined with outside data to identify people, such as ZIP code, birth date, and sex.⁠¹ Sweeney credits the term to Dalenius and defines the k-anonymity requirement as a constraint on the released table: for every combination of quasi-identifier values that appears, at least k records share it.⁠¹ If k is 5, any person matched on those attributes is one of at least five.

Origin and history

k-anonymity grew out of a demonstration that “anonymous” data was not. Sweeney describes how the Massachusetts Group Insurance Commission collected patient data for “approximately 135,000 state employees and their families,” and, “because the data were believed to be anonymous,” gave a copy to researchers and sold one to industry.⁠¹ She writes: “For twenty dollars I purchased the voter registration list for Cambridge Massachusetts,” which included name, address, ZIP code, birth date, and gender, and which could be linked to the medical data.⁠¹ Governor William Weld’s records were in the data; “six people had his particular birth date; only three of them were men; and, he was the only one in his 5-digit ZIP code”.⁠¹

Sweeney also cites a finding that “87% (216 million of 248 million) of the population in the United States had reported characteristics that likely made them unique based only on {5-digit ZIP, gender, date of birth}”.⁠¹ NIST SP 800-226 retells the same case as the classic example of a linking attack.⁠²

The voter-list detail matters for civic technology: public election records were the outside data that made re-identification possible.

How k-anonymity is applied

A data holder applies k-anonymity by choosing the quasi-identifiers, choosing k, and then transforming the table until the requirement holds. Two operations do most of the work:

• Generalization: replacing precise values with ranges (age 34 becomes 30 to 39; a ZIP code becomes its first three digits).
• Suppression: removing records or values that remain unique.

Sweeney’s paper also describes attacks that can work against releases that satisfy k-anonymity “unless accompanying policies are respected,” such as matching across differently sorted or repeated releases.⁠¹ A further weakness follows from the definition itself. Hypothetical example: if all five records sharing a person’s age range and ZIP prefix show the same answer to a sensitive question, the table is 5-anonymous, yet anyone who knows the person is in it learns their answer. NIST contrasts such informal protections with differential privacy, which it describes as “resistant to all privacy attacks, even attacks not yet invented”.⁠² See Differential privacy.

Common confusions and neighboring terms

• k-anonymity vs. minimum group size. A minimum cell size for aggregates (for example, suppress counts below 10) applies the same intuition to tables of totals.
• k-anonymity vs. differential privacy. k-anonymity is a property of one released table under assumptions about the attacker’s knowledge; differential privacy bounds what any release reveals regardless of outside data.
• k-anonymity vs. de-identification. Removing names is de-identification; k-anonymity is a specific, testable standard for it.
• k-anonymity vs. secrecy. Ballot secrecy is a legal and procedural protection for votes; k-anonymity is a data release technique.

How My Vote Forward uses the term

My Vote Forward releases only aggregates, never record-level data, so k-anonymity in Sweeney’s sense would not be applied to a table of individual answers. Its logic informs the framework’s requirement that a documented privacy design set minimum group sizes before any real aggregate is released, as stated in Published releases and Privacy. The Weld case is a reminder that public data such as voter lists can be the key that unlocks other data, so any privacy review has to assume an attacker holds them.

Unresolved questions

• What value of k, or what minimum group size, is appropriate when a district has only a few hundred participants?
• Which attributes should be treated as quasi-identifiers in civic data, given how much is public in voter files?
• Should small-group rules be combined with differential privacy, or does one make the other unnecessary?