Which privacy methods survive at scale

The syntactic era

The first generation of privacy methods worked on the shape of the table. k-anonymity required every record to be indistinguishable from at least k−1 others on the fields that could identify you. l-diversity added that each such group must contain a spread of sensitive values, because a group of ten people who all have the same diagnosis protects nobody. t-closeness tightened it again.

Each of these is a repair of the one before, and the pattern is the tell. They are syntactic: they constrain what the published table looks like, not what an attacker can deduce from it. Bring outside knowledge and the guarantee dissolves, which is exactly what the Netflix and hospital re-identifications did.

Hiding rules rather than records

My own starting point was a neighbouring problem. If you mine a transaction database for association rules — people who buy this also buy that — some of those rules are commercially or personally sensitive, and you want to publish the database without them being derivable. The technique is to perturb transactions just enough to push the sensitive rules below the support threshold while disturbing everything else as little as possible.

That is a search problem with a clear objective, which is why my 2012 paper approaches it with particle swarm optimisation and attribute reduction. It is honest, useful work with a limitation that took me years to fully appreciate: like k-anonymity, it protects against the attacker you modelled, and says nothing about the one you did not.

What scale broke

Three properties of big data broke the syntactic methods at once. Volume made the grouping and generalisation steps expensive enough to be impractical. Variety meant the data arrived as text, images and streams rather than neat tables with identifiable quasi-identifier columns. Velocity meant a release was not a one-off event you could reason about, but a continuous publication where every increment leaks a little more.

Distributed processing added a fourth problem that is easy to miss: once your data lives across a cluster, privacy is no longer a property of one release but of a pipeline, with intermediate results sitting on disks that nobody audits.

The survey I wrote for the Springer handbook on this is the most cited thing I have written, which I take as evidence that a lot of people arrived at the same confusion at the same time.

What the old methods are still for

None of this makes generalisation and suppression worthless. They are cheap, they are explainable to a committee, and when the release is a one-off table for a known internal audience they are often proportionate. Differential privacy is not free, and using it on a small dataset where the noise swamps the signal is worse than using nothing and restricting access instead.

The distinction worth carrying is between hiding identifiers and bounding disclosure. The first is a matter of how the data looks. The second is a claim about what anyone can learn, and it is the only one that survives an attacker you did not anticipate.

What to read next

Outside work, not mine. Each title links to a Google Scholar search, which will find you whichever version is open access.

2000

Privacy-Preserving Data MiningRakesh Agrawal and Ramakrishnan SrikantThe paper that opened the field. Worth reading to see how the question was framed before the guarantees existed.

2007

l-Diversity: Privacy Beyond k-AnonymityAshwin Machanavajjhala, Daniel Kifer, Johannes Gehrke and Muthuramakrishnan VenkitasubramaniamThe clearest example of the repair-and-repair-again pattern, and it explains its own predecessor well.