k-Anonymity

Imagine a hospital wants to share patient records with researchers. It strips out names and social-security numbers — the obvious identifiers. But the dataset still contains age, ZIP code, and sex. In a landmark 1997 study, Latanya Sweeney showed that those three fields alone could re-identify 87% of the US population from public voter rolls.

The insight behind k-anonymity (formalized by Sweeney and Pierangela Samarati in 1998) is elegantly simple: before releasing a table, generalize the quasi-identifiers — the fields that are not identifiers on their own but become one in combination — until every row is shared by at least k people. With $k = 3$, knowing someone's age, ZIP, and sex narrows the field to at least three records, so you cannot point to a single person.

The transformation tools are generalization (replace a specific value with a broader category, e.g., age 34 → age range 30–39) and suppression (remove a row or value entirely when it cannot be merged). The goal is to minimize information loss while guaranteeing that no equivalence class — a group sharing the same generalized quasi-identifiers — drops below $k$ members.

That trade-off between utility and privacy turns out to be computationally hard, and understanding why is a journey straight into P vs NP.

Below is a small patient table with three quasi-identifiers: Age, ZIP, and Sex. The sensitive column (Condition) must never be used to re-identify anyone. Use the slider to set k, then press Generalize to watch the table transform until every group of rows with the same quasi-identifiers has at least k members.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label for="kSlider">{{lbl_k}} <strong id="kVal">2</strong></label>
  <input type="range" id="kSlider" min="1" max="5" value="2" />
  <button id="btnGeneralize" type="button">{{btn_generalize}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status"></div>
<div class="table-wrap">
  <table id="dataTable">
    <thead>
      <tr>
        <th>{{col_age}}</th>
        <th>{{col_zip}}</th>
        <th>{{col_sex}}</th>
        <th class="sensitive">{{col_condition}}</th>
      </tr>
    </thead>
    <tbody id="tableBody"></tbody>
  </table>
</div>
<div class="legend">
  <span class="legend-item suppressed-swatch"></span> {{legend_suppressed}}
  &nbsp;&nbsp;
  <span class="legend-item generalized-swatch"></span> {{legend_generalized}}
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-weight: 600; white-space: nowrap; }
input[type=range] { width: 120px; cursor: pointer; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; margin-bottom: .4rem; }
.status.ok { color: #0a7d33; }
.status.warn { color: #b36200; }
.table-wrap { overflow-x: auto; }
table { border-collapse: collapse; width: 100%; }
th, td { border: 1px solid #cdd9e3; padding: .32rem .6rem; text-align: left; white-space: nowrap; }
th { background: #e8eef3; font-weight: 700; font-size: .82rem; }
th.sensitive { background: #f5e6c8; }
td.sensitive { background: #fdf6e8; }
tr.suppressed td { background: #fce4e4; color: #888; text-decoration: line-through; }
td.gen { background: #ddefff; font-style: italic; }
.legend { display: flex; align-items: center; font-size: .8rem; color: #555; margin-top: .5rem; flex-wrap: wrap; gap: .3rem; }
.legend-item { display: inline-block; width: 14px; height: 14px; border-radius: 3px; vertical-align: middle; }
.suppressed-swatch { background: #fce4e4; border: 1px solid #c92f3c; }
.generalized-swatch { background: #ddefff; border: 1px solid #5a9fd4; }

// Code not found

Notice that raising k forces broader generalizations — ages collapse into wider ranges, ZIP codes lose digits. The table stays useful at $k = 2$, but at $k = 4$ several rows may need to be suppressed entirely. The computer only tried a greedy approach here; finding the optimal generalization that minimizes information loss while guaranteeing $k$-anonymity is a problem no algorithm can solve efficiently for all inputs — it's NP-hard.

At first glance, k-anonymity looks like a clean optimization problem: generalize quasi-identifiers to minimize distortion while keeping every equivalence class at size $\geq k$. How hard can searching a few generalization lattices be?

Very hard, as it turns out:

• Generalization lattices are exponential. Each attribute has a hierarchy of generalizations (e.g., exact age → decade → all ages). With $d$ attributes each having $h$ levels, the search space is $h^{d}$ combinations per row, and interactions between attributes multiply the difficulty.
• NP-hardness was proved in 2004. Andrew Meyerson and Ryan Williams showed that even the simplest version — suppress the minimum number of rows so the remainder is $k$-anonymous — is NP-hard. The reduction is from set cover.
• Suppression alone is NP-hard. If you allow only suppression (no generalization), optimal k-anonymity is still NP-hard for $k \geq 3$. This means there is no polynomial-time algorithm that always finds the minimum-suppression solution (unless P = NP).
• Generalization with suppression is also NP-hard. Allowing the richer generalization operation does not make the problem easier; the search space only grows.

In practice, researchers use heuristics: Datafly, Incognito, Mondrian, and others sacrifice optimality for speed, often guided by an information-loss metric like the normalized certainty penalty. The gap between the greedy solution and the true optimum can be large, and no polynomial-time algorithm is known to close it.

k-anonymity is not a theoretical curiosity — it shaped how governments and health systems release data:

• Healthcare: HIPAA's Safe Harbor rule requires suppressing or generalizing 18 categories of identifiers before sharing patient data. k-anonymity provides a formal framework for doing so, and US health agencies use it for public-use files.
• Census microdata: national statistical offices release individual-level records with quasi-identifiers suppressed or top-coded so that no cell drops below a threshold — precisely k-anonymity in practice.
• Location privacy: publishing GPS traces without allowing re-identification requires that every trajectory pattern appear in at least $k$ users, a spatial generalization of the same idea.
• Beyond k-anonymity: the model has well-known weaknesses — homogeneity attacks (all $k$ records share the same sensitive value, so knowing someone is in the group reveals their diagnosis) and background-knowledge attacks. These led to stronger models: $\ell$-diversity, $t$-closeness, and ultimately differential privacy, which provides a mathematical guarantee against any auxiliary-information attack.

The computational hardness of optimal k-anonymity means real systems always make privacy-utility trade-offs under uncertainty — a reminder that privacy is not just a policy question but a computational one.

k-anonymity captures a beautifully human intuition: safety in numbers, anonymity by indistinguishability. Sweeney and Samarati turned it into a rigorous demand — no equivalence class smaller than $k$ — and that demand turned out to carry genuine computational weight.

Finding the optimal transformation is NP-hard. The heuristics deployed in practice are fast but imperfect, and the gap between what they deliver and the true optimum is unknowable without solving a problem that may take exponential time. Every real deployment of k-anonymity is, at its core, an approximation of an intractable problem.

So the next time you download a "de-identified" dataset, remember that someone — or some heuristic — made a hard call about where to draw the generalization boundary. The line between useful and private passes right through the heart of P vs NP.