What is the formal definition of k-anonymity, and what is an equivalence class?

k-anonymity means an individual cannot be distinguished from at least k-1 others based on the quasi-identifiers; an equivalence class is a group of records sharing identical QID values.

* Equivalence classes satisfying 2-anonymity. — HTriedman (WMF), CC BY-SA 4.0, via Wikimedia Commons. *

The mechanism: manipulate records so they form groups of at least size k, all sharing the same quasi-identifier values. Each such group is an equivalence class. If every class has ≥ k members, then for any record an attacker matches, there are at least k indistinguishable candidates — so they can't pin the sensitive value to one person via the QIDs.

Two tools achieve it:

• Generalization — replace an exact value with a range/category (Age 28 → [20–30]).
• Suppression — replace a value with a wildcard * to hide it entirely (Name / ZIP / rating → *).

Tip: "k" is literally the crowd size you're hiding in. k=3 means at least two look-alikes for every record.

Go deeper:

• k-anonymity (Wikipedia) — formal "indistinguishable from k-1 others" definition.
• k-Anonymity (Sweeney, 2002) — the source definition and equivalence classes.