Syllabus Lesson 54 of 156 · Measure privacy, honestly
Measure privacy, honestly

k-anonymity

Why it matters Organisations often share data after "removing names", and call it anonymous. You will see, on synthetic data, how quickly three ordinary facts put the names back. This is how real re-identification has happened, and why the defence in lesson 56 exists.

The gossip test

Someone says: "A woman on our street, born on 3 March 1981, just got a diagnosis." No name was given. But on one street, how many women share that exact birthday? Probably one. The details were the name.

Quasi-identifier: a fact that is not a name but, combined with a few others, points to one person. Postcode (zip code), full birth date and gender are the classic three.

Re-identification: putting names back on data that was released without them, usually by joining it to another list that has names.

A famous study by Latanya Sweeney in 2000 estimated that about 87% of people in the United States could be singled out by zip code, birth date and gender alone. We will see the same effect on made-up data.

The practice data

synthetic_people(2000) builds an invented health table: id, name, zip, birth_date, gender, diagnosis. Nobody in it is real. We "anonymise" it the naive way, by dropping the name. synthetic_public_roll(people) builds an invented public list, like a club register, with names, zip, birth date and gender, but no diagnosis.

Measuring the risk: k

k-anonymity: a table is k-anonymous when every combination of quasi-identifier values is shared by at least k rows. k = 1 means at least one person is alone, and can be found.

To find k: group rows by their quasi-identifier tuple, count each group, and take the smallest count. With ["gender"] alone, k is large. With zip, birth date and gender together, k drops to 1.

The join

For each person on the public roll, build their key (zip, birth_date, gender) and look for it in the released table. Be strict: only count a match when the key appears exactly once in the release and exactly once on the roll. Then you are certain. If two records share the key, you cannot tell which is which; if two people on the roll share it, you cannot tell who is who.

reidentify(released, roll)
# {17: 'Mei Patel', 203: 'Omar Novak', ...}   record id -> name

Once record 17 has a name, its diagnosis has one too. That is the whole attack: two harmless-looking lists, one join.

A common misconception

"Removing names, emails and phone numbers makes data anonymous." It removes the obvious identifiers, but the remaining columns can still single people out. Whether data is anonymous depends on what else is out there to join it with, which is why lesson 56 changes the data itself.

Try it When you pass, change the roll's fraction from 0.6 to 0.2 and run again. The number of matches falls, but the share of roll people you re-identify barely changes. Each person is exposed by their own details, not by how big the list is.

In other languages

JavaScript:

function reidentify(released, roll, cols) {
  const key = r => JSON.stringify(cols.map(c => r[c]));
  const count = list => list.reduce((m, r) => m.set(key(r), (m.get(key(r)) || 0) + 1), new Map());
  const a = count(released), b = count(roll);
  const byKey = new Map(released.map(r => [key(r), r]));
  const found = {};
  for (const p of roll) {
    if (a.get(key(p)) === 1 && b.get(key(p)) === 1) found[byKey.get(key(p)).id] = p.name;
  }
  return found;
}

SQL-style thinking in C# (LINQ):

var matches =
    from r in released
    join p in roll on new { r.Zip, r.BirthDate, r.Gender }
                   equals new { p.Zip, p.BirthDate, p.Gender }
    select new { r.Id, p.Name };
// then keep only keys that occur once on each side

Recap

  • Quasi-identifiers (zip, birth date, gender) can single people out without a name.
  • k is the size of the smallest group sharing the same quasi-identifiers; k = 1 means someone is exposed.
  • Joining a nameless table to a public list with names re-identifies people.
  • Dropping names is not anonymisation. Synthetic data only here; the defence is next.
Your turn

Write quasi_key(row, columns) (tuple of the values), smallest_group(rows, columns) (the size of the smallest group of rows sharing a key: that is k) and reidentify(released, roll, columns=QUASI), returning a dict from released record id to roll name for every roll person whose key appears exactly once in released and exactly once in roll.

Spotted a problem in this lesson? Report it

Code · runs in your browser
Output

        

      

      
      

        Back