Chapter 45 — De-identification and privacy-preserving analytics

In one sentence

Anonymization and pseudonymization are legally and technically distinct — only data that is genuinely irreversible falls outside privacy law entirely — and techniques like k-anonymity and differential privacy exist because naive "remove the name" de-identification has repeatedly been reversed on real datasets.

Where we are

Your data-flow map (Ch 41) routes some RESTRICTED data into analytics and BI. Chapter 42 protects it at rest with encryption, which analysts and dashboards generally need to see through — so this chapter is the layer that lets you learn from data in aggregate without exposing individuals.

How it works

Pseudonymization vs anonymization (the legal line, GDPR Recital 26):

   PSEUDONYMIZATION  replace direct identifiers with a pseudonym (a
     token, a hash) but keep the ADDITIONAL INFORMATION that could map it
     back, held separately. STILL PERSONAL DATA under GDPR -- because
     it's re-identifiable "with additional information", even if you
     don't currently intend to use it. Good practice (reduces exposure,
     is a recognised risk-reduction measure), but does NOT take data out
     of scope for erasure requests, breach notification, etc.

   ANONYMIZATION  irreversibly processed such that the data subject is NO
     LONGER IDENTIFIABLE by ANY means reasonably likely to be used
     (considering cost, time, and available technology -- this bar is
     genuinely high and gets HIGHER as more auxiliary data becomes
     public). Only TRUE anonymization is outside GDPR scope entirely.
     Most "anonymized" datasets in practice are actually pseudonymized,
     or worse, naively de-identified and re-identifiable (below).

Why naive de-identification fails — the re-identification record:

   Latanya Sweeney (1997): cross-referenced "anonymized" Massachusetts
     hospital discharge records (with ZIP, birth date, sex kept) against
     public voter rolls -> identified the state's GOVERNOR's own medical
     records. Showed 87% of the US population is uniquely identifiable
     by {ZIP code, birth date, sex} alone -- three "harmless" quasi-
     identifiers.
   AOL search-log release (2006): "anonymized" by replacing usernames
     with numeric IDs; journalists identified user "4417749" from the
     CONTENT of her searches alone (she'd searched her own town,
     relatives' names). No cross-referencing needed -- the data itself
     was identifying.
   Netflix Prize dataset (2008, Narayanan & Shmatikov): movie ratings
     with usernames stripped were re-identified by cross-referencing
     timing and rating patterns against PUBLIC IMDb reviews -- showing
     that even sparse, high-dimensional "anonymous" data is often
     uniquely fingerprinting.
   Strava heatmap (2018): aggregated, anonymized fitness-tracker activity
     data revealed the LAYOUT of classified military bases via runners'
     GPS patterns -- a reminder that AGGREGATION isn't automatically safe
     either when the population is small or the pattern itself is
     identifying.

   THE LESSON: removing "obvious" identifiers (name, email, SSN) is not
   anonymization. QUASI-IDENTIFIERS (ZIP, birth date, gender, job title,
   rare combinations of attributes) and even raw CONTENT/BEHAVIOUR can
   re-identify people, especially when combined with other public or
   purchasable datasets.

Formal techniques (each solves a specific weakness of the last):

   K-ANONYMITY (Sweeney)
     generalise/suppress quasi-identifiers so EVERY combination
     of them is shared by at least K records (e.g. group ages into
     10-year bands, ZIP to 3 digits, until any {age-band, ZIP3, gender}
     group has >= K people).
     WEAKNESS: homogeneity attack -- if all K records in a group share the
     SAME sensitive value (e.g. all have the same diagnosis), knowing
     someone is in the group reveals it regardless of anonymity set size.

   L-DIVERSITY
     extends k-anonymity: each group must also have at least L
     "well-represented" distinct values for the sensitive attribute --
     fixes the homogeneity attack.
     WEAKNESS: skewness/similarity attack -- if the L values are all
     similar in a way that still leaks (e.g. "flu" vs "severe flu" vs
     "mild flu" are technically 3 distinct values but all reveal "has
     flu"), or if the overall distribution is heavily skewed, l-diversity
     alone can still leak.

   T-CLOSENESS
     further requires the DISTRIBUTION of the sensitive attribute within
     each group to be close (within threshold t) to its distribution in
     the WHOLE dataset -- so being in a group reveals little beyond what
     you'd already infer from the population at large.
     Together, k-anonymity -> l-diversity -> t-closeness is a progression
     of patches, each closing a specific attack the previous one missed --
     useful for STATIC, RELEASED datasets, but brittle and doesn't compose
     well across multiple releases or queries.

   DIFFERENTIAL PRIVACY (the modern, composable answer)
     a formal, mathematical guarantee: the output of a query/analysis is
     (almost) indistinguishable whether or not ANY SINGLE individual's
     data was included. Achieved by adding calibrated NOISE.
       epsilon (privacy budget/loss): smaller = more privacy, more noise,
         less accuracy. Budget is CONSUMED across queries (composition) --
         you must track cumulative epsilon spent against a dataset, or
         privacy guarantees erode with repeated querying.
       Laplace mechanism: add Laplace-distributed noise scaled to the
         query's SENSITIVITY (how much one record can change the answer)
         and to 1/epsilon -- for numeric queries (counts, sums, averages).
       Gaussian mechanism: similar, for a slightly different formal
         guarantee (epsilon-delta DP), often used at scale.
       Exponential mechanism: for selecting among CATEGORICAL/discrete
         outputs (e.g. "most common answer") while preserving DP.
       GLOBAL DP: a trusted curator holds the raw data and adds noise only
         to QUERY RESULTS (higher accuracy per query, requires trusting
         the curator with raw data).
       LOCAL DP: each user's device adds noise BEFORE sending data
         anywhere (no one, not even you, ever sees raw values) -- lower
         accuracy, much stronger trust model. Real deployments: Google's
         RAPPOR (Chrome telemetry), Apple's use in iOS/macOS analytics.
     Real large-scale deployment: the US Census Bureau adopted
     differential privacy for the 2020 Census release -- the definitive
     proof this scales to a genuinely high-stakes, adversarially-scrutinised
     use case.

   SYNTHETIC DATA
     train a generative model (statistical, or a GAN/diffusion-style
     model) on the real data, then sample NEW, artificial records that
     preserve the real data's statistical properties without being any
     real person's actual record. Useful for dev/test environments and
     some analytics; still requires care -- a poorly-regularised
     generative model can memorise and leak training examples (a known
     failure mode, mitigate by training WITH differential privacy).

Practical guidance, in order of preference:

   1. DON'T COLLECT what you don't need (data minimisation -- the
      cheapest and most durable privacy control, and the first line of
      every privacy framework).
   2. AGGREGATE at the source where possible (counts/sums, not raw
      events) if the use case allows it.
   3. PSEUDONYMIZE as a baseline for anything reaching analytics --
      reduces blast radius even though it's still personal data.
   4. Apply K-ANONYMITY/L-DIVERSITY/T-CLOSENESS for one-off dataset
      RELEASES (a research dataset, a public report) where you control
      exactly what's published once.
   5. Apply DIFFERENTIAL PRIVACY for ONGOING, QUERYABLE analytics systems
      (a dashboard, an internal query tool, anything where the same
      underlying data will be queried repeatedly) -- it's the only
      approach in this list designed for that composition problem.
   6. Treat SMALL POPULATIONS, RARE COMBINATIONS, and RICH
      BEHAVIOURAL/CONTENT DATA (free text, location traces, search
      history) as high re-identification risk regardless of which
      technique you apply -- suppress or aggregate more aggressively.

Worked example

De-identifying SecureShop's analytics warehouse, and catching a skew that k-anonymity alone would have missed.

   The warehouse receives order events for BI dashboards ("average order
   value by region and age band"). The data-flow map (Ch 41) flags this
   as a place RESTRICTED customer PII must NOT arrive in raw form.

   NAIVE (what NOT to do): strip name and email, keep {ZIP, birth date,
   gender, order history}. Per Sweeney's result, {ZIP, birth date, gender}
   alone re-identifies most US customers. FAILS immediately.

   K-ANONYMITY pass: generalise ZIP to 3 digits, birth date to 5-year
   bands, until every {ZIP3, age-band, gender} group has >= 20 (K=20)
   customers. Check: one rural ZIP3 + a rare age band has only 20 people,
   and it turns out ALL 20 bought the same high-value medical-adjacent
   product category -- a HOMOGENEITY attack: knowing someone is in that
   group reveals their purchase category even without picking them out
   individually.

   L-DIVERSITY fix: require each group to have at least L=5 well-
   represented distinct product categories, forcing further generalisation
   (a coarser region, or suppressing the smallest groups entirely) until
   that group either merges with others or is dropped from the release.

   FOR THE ONGOING DASHBOARD (not a one-off release): instead of
   maintaining k-anonymity/l-diversity as data keeps changing (brittle --
   every new order can break a group's diversity), switch the LIVE
   query tool to a DIFFERENTIAL PRIVACY layer (e.g. Tumult Analytics or
   Google's differential-privacy library) in front of the warehouse:
   analysts get answers to "average order value by region and age band"
   with calibrated noise and a tracked epsilon budget per dataset,
   rather than direct SQL access to individually-generalised rows. New
   data flowing in doesn't require re-doing a k-anonymity pass -- the
   noise mechanism handles it per query.

   RESULT: the one-off research export (if SecureShop ever publishes one)
   uses the k-anonymity/l-diversity/t-closeness pipeline appropriate to a
   static release; the ONGOING internal BI tool uses differential privacy,
   appropriate to a repeatedly-queried live system -- matching technique
   to use case as the chapter recommends.

Practice (75 min)

Take a sample dataset (synthetic or public, e.g. an anonymized census extract) with ZIP, birth date, and gender columns. Compute how many records are UNIQUELY identified by that triple — reproduce Sweeney's finding at small scale.
Apply k-anonymity by generalising (broader ZIP prefix, wider age bands) until every group has k>=10; check for a homogeneity attack (does any group share one sensitive value?); apply l-diversity to fix it.
Install an open-source differential-privacy library (Google's differential-privacy, OpenDP, or Tumult Analytics). Run a noised COUNT/AVERAGE query against the dataset at a couple of different epsilon values; observe the accuracy/privacy trade-off directly.
Track a privacy budget across five sequential queries against the same dataset; show cumulative epsilon growing and decide when you'd refuse a sixth query.
Write the one-paragraph decision for your own system: which flows get pseudonymization only, which get a k-anonymity/l-diversity release process, and which need a differential-privacy query layer — tied to your Ch 41 data-flow map.

Common mistakes

Calling pseudonymized data "anonymized." It's still personal data under GDPR if it's re-identifiable with information you (or anyone) hold separately.
"We removed the name and email" as the whole de-identification strategy. Quasi-identifiers and rich content/behavioural data re-identify people; see every case in this chapter's history section.
K-anonymity treated as sufficient on its own. Check for homogeneity; add l-diversity, and t-closeness if the sensitive-attribute distribution is skewed.
Applying a one-off anonymization technique to a continuously-updated, repeatedly-queried system. It decays with every new query/record; differential privacy is built for exactly that composition problem.
Ignoring privacy-budget composition. Ten "safe" small-epsilon queries can add up to a large, unsafe cumulative epsilon. Track spend per dataset.
Assuming synthetic data is automatically safe. An overfit generative model can memorise and regurgitate real training records; train with DP if this is a real risk for your data.

Check yourself

What is the legal difference between pseudonymization and anonymization under GDPR, and why does it matter for compliance?
Give three historical re-identification cases and what each teaches about naive de-identification.
What weakness does l-diversity fix that k-anonymity alone misses, and what does t-closeness fix in turn?
What does the "epsilon" in differential privacy represent, and why must it be tracked across queries rather than per-query?
Global vs local differential privacy — what's the trust-model difference, and give a real-world example of each?
When would you choose k-anonymity/l-diversity over differential privacy, and vice versa?