A fast memory refresh for combinatorics, sparsity and de-anonymisation.
S speaker notes · Esc overview · F fullscreen · ?debug outlines overfull slides · red STOP slides are student work time
Age, location, date, ratings or graph structure that becomes identifying after linkage.
Medical condition, preference or relationship the release was meant not to expose.
Lecture 2's informal definition: a sharing mechanism \(f_D\) that lets an unauthorised party learn sensitive information about any individual, which could not have been learnt without access to \(f_D\).
How many subsets of size \(K\) from a set of size \(N\) can you choose?
Consider a record that consists of three attributes:
How many unique records can there be?
For each: ordered or unordered? Repetition or no repetition? Name the object before you name a formula.
Choosing \(K\) items from \(N\) types: does order matter, and may an item repeat?
| Orderedsequence | Unorderedset or multiset | |
|---|---|---|
| No repetition | \(\dfrac{N!}{(N-K)!}\) | \(\dbinom{N}{K}\)Q1 |
| Repetition allowed | \(N^{K}\) | \(\dbinom{N+K-1}{K}\)Q3 |
That product rule is a separate move from the table—it builds the \(N\) that the table then draws from. Q2 builds \(N\); Q3 draws from it.
And before calling a ratio a probability: state which outcomes are equally likely.
“Choose Alice, Bob” and “choose Bob, Alice” are the same subset—so divide the \(N!/(N-K)!\) ordered picks by the \(K!\) orders of each subset.
Let \(r\) be a record with a fixed age, location and medical condition.
How many distinct datasets of 200 records can there be where \(r\) is part of the dataset?
Write the expression only. No factorials need to be evaluated.
One required record + 199 freely chosen records
There are 1600 record types. After removing the required copy of \(r\), choose a multiset of 199 records from those 1600 types.
A 271-digit number. The observable universe holds roughly \(10^{80}\) atoms — so there are about \(10^{190}\) times more possible datasets than there are atoms to write them on.
Two ways to get this wrong:
There is a very large number of possible databases for the record types described in Questions 2–3.
Why should someone still worry about the privacy of their medical condition if a dataset of 200 records—including theirs—were released, and their age and location were known, for example from Facebook?
Known to attacker: age and location.
Unknown: medical condition.
Released: all three attributes, without names.
The released dataset contains 200 records. An attacker already knows the person's age and location, but not their medical condition. State the attack in words before writing anything down.
RELEASED MEDICAL DATA
| Age | State | Condition |
|---|---|---|
| 25 | VIC | 0 |
| 29 | VIC | 1 |
| 42 | NSW | 0 |
PUBLIC / SOCIAL DATA
| Name | Age | State |
|---|---|---|
| Alice | 25 | VIC |
| Cathy | 29 | VIC |
| Fred | 42 | NSW |
Lecture 1's example: a Massachusetts insurance release kept visit date, diagnosis, procedure, medication — plus ZIP, birth date and sex. The public voter roll carried name and address plus the same three. The overlap is the quasi-identifier: it re-identified the state Governor, linking his name to his diagnosis, and it uniquely identifies 87% of the US population.
The condition is unknown, so marginalise it away: keep age and location only.
So “there are astronomically many possible datasets” does not imply that this person blends in. The global sample space is huge; the local neighbourhood is not.
The attacker knows the quasi-identifier, so they can only look at the released rows that match it. Three things can be behind that door.
| Age | State | Condition |
|---|---|---|
| 29 | VIC | 1 |
Unique quasi-identifier.
The condition is read straight off.
| Age | State | Condition |
|---|---|---|
| 29 | VIC | 1 |
| 29 | VIC | 1 |
| 29 | VIC | 1 |
Not unique — and it makes no difference.
Every candidate carries the same secret.
| Age | State | Condition |
|---|---|---|
| 29 | VIC | 1 |
| 29 | VIC | 0 |
| 29 | VIC | 0 |
If the three candidates are equally likely, the posterior is \(\tfrac13\) — leakage only insofar as that differs from the attacker's prior.
\(N\) users \(\times\) \(M\) items. A filled cell is a rating the user actually gave (\(+\) liked, \(-\) disliked); a blank cell is null, not a zero opinion. Real releases have thousands to millions of columns and a handful of filled cells per row.
Names and account IDs are stripped before release. The rows are still there, one per person.
Anything the adversary has from outside the normal release process: other public data and social media, a business's own customer database, or something personally observed—an overheard conversation, a witnessed event.
\(\supp(r_1)=\{1,5\}\)
\(\supp(r_2)=\{1,2,5\}\)
A one-hot record is the extreme case: exactly one non-zero attribute, so \(|\supp(r)|=1\). Questions 5 and 6 both live here.
The numerator is a sum of per-attribute similarities—each in \([0,1]\), not necessarily 0 or 1. That matters in Q6.
Check yourself on the lecture's third record \(r_3=[0,1,1,1,1]\): \(\Sim(r_1,r_3)=\tfrac15\) and \(\Sim(r_2,r_3)=\tfrac25\).
In words: at most a fraction \(\delta\) of records have any other record more than \(\epsilon\)-similar to them.
Pick a record at random; the chance that its nearest neighbour is closer than \(\epsilon\) is at most \(\delta\).
Lecture 2 and the Netflix paper write the same event more compactly — see the speaker notes if you are comparing with your lecture slides.
SPARSITY AND THE “LONG TAIL” — REDRAWN FROM LECTURE 2
Consider the definition of dataset sparsity \((\epsilon,\delta)\) from Lecture 2 and two datasets, where \(N \gg M\):
Suppose every record has exactly one non-zero attribute, chosen uniformly. Which dataset is likely to have the higher sparsity parameter \(\epsilon\) for a fixed \(\delta\)?
So \(s(r)=\max_{r'\neq r}\Sim(r,r')\) is 1 exactly when some other row collides with \(r\), and 0 otherwise.
Every row is one-hot with a uniformly chosen column. Answer in two parts.
Distance here is dissimilarity: \(d=1-\Sim\). So the dashed circle has radius \(1-\epsilon\) — raise the similarity threshold \(\epsilon\) and it shrinks.
2 of 14 records have a neighbour inside the ring \(\Rightarrow\) this dataset passes at \(\delta \approx 0.14\)
12 of 14 records have a neighbour inside the ring \(\Rightarrow\) at the same \(\epsilon\) it needs \(\delta \approx 0.86\)
Both panels use the same radius \(1-\epsilon\), so the same \(\epsilon\). Only the crowding — and therefore \(\delta\) — differs.
Many collisions: identical rows are likely.
Few collisions: records are usually unique.
Almost everyone has a twin, so \(p\le\delta\) fails unless \(\delta\approx1\). Only the threshold that zeroes the probability survives. \(\Rightarrow\ \boldsymbol{\epsilon=1}\)
Hardly anyone has a twin, so \(p\le\delta\) already holds for any sensible \(\delta\) — even the strictest threshold passes. \(\Rightarrow\ \boldsymbol{\epsilon=0}\)
Same convention: distance is dissimilarity \(d=1-\Sim\), so the ring has radius \(1-\epsilon\). One-hot rows leave only two distances — \(0\) (same column) or \(1\) (nothing shared).
\(N=12\) rows into \(M=3\) columns. Every row shares its column with three others: 12 of 12 records have a twin inside the ring.
\(M=3\) rows into \(N=12\) columns. Each row lands in a column of its own, nine stay empty: 0 of 3 records have anyone inside the ring.
\(p=1-(1-\tfrac1M)^{N-1}\approx 1\) for every \(\epsilon<1\): twins sit at distance \(0\), so no positive radius excludes them. To reach \(\delta=0.1\) the ring must close to radius \(0\).
\(p\approx\tfrac{M-1}{N}\approx 0\le\delta\) already. Even the widest ring, radius \(1-\epsilon=1\), catches nobody: every other row sits at distance exactly \(1\).
Goal: given \(\aux=\Aux(r)\), find the other attributes of \(r\). The lecture writes \(\Score(r',\aux)\) and the tutorial writes \(\Score(\aux,r)\) — same function, arguments swapped.
THE RELEASE — FIVE RECORDS, FIVE FILMS, NO NAMES
| A | B | C | D | E | |
|---|---|---|---|---|---|
| \(r'_1\) | 3 | 4 | 1 | 3 | 5 |
| \(r'_2\) | 5 | 5 | 2 | 2 | 1 |
| \(r'_3\) | 1 | 2 | 4 | 3 | 4 |
| \(r'_4\) | 4 | 3 | 5 | 1 | 3 |
| \(r'_5\) | 2 | 1 | 3 | 5 | 2 |
1 · SCORE EVERY RECORD — WORST ATTRIBUTE WINS
| on B | on D | on E | \(\Score=\min\) | |
|---|---|---|---|---|
| \(r'_1\) | 1.00 | 0.75 | 1.00 | 0.75 |
| \(r'_2\) | 0.75 | 1.00 | 0.00 | 0.00 |
| \(r'_3\) | 0.50 | 0.75 | 0.75 | 0.50 |
| \(r'_4\) | 0.75 | 0.75 | 0.50 | 0.50 |
| \(r'_5\) | 0.25 | 0.25 | 0.25 | 0.25 |
Instead of treating each attribute equally and computing
it computes a weight \(w(i)=1/\log|\supp(i)|\), where \(\supp(i)\) is the set of records with a non-null value for attribute \(i\), and scores
What effect does this have on the outcome of the algorithm? Why—and when—would this algorithm perform better than the one that does not use \(w\)?
Bring back one benefit and one failure mode.
A rare movie, purchase or diagnosis rules out far more candidate records than a common one, so it should count for more.
\(w(i)\) is large exactly where \(|\supp(i)|\) is small, so agreement on a rare attribute moves the score far more than agreement on a common one. This is the supplied answer's point, and it is right.
Under \(\min\), a single bad attribute caps the whole score. Under \(\sum\), strong rare matches can outweigh one weak or noisy attribute.
| attribute \(i\) | \(|\supp(i)|\) | \(w(i)\) | \(\Sim(\aux_i,r'_i)\) candidate \(r'_A\) | \(\Sim(\aux_i,r'_i)\) candidate \(r'_B\) |
|---|---|---|---|---|
| common | 5000 | 0.12 | 1.0 | 0.6 |
| rare 1 | 3 | 0.91 | 1.0 | 0.5 |
| rare 2 (noisy aux) | 3 | 0.91 | 0.1 | 0.5 |
| \(\min_i\) | 0.10 | 0.50 ← | ||
| \(\sum_i w(i)\Sim_i\) | 1.12 ← | 0.98 |
\(r'_A\) matches both rare attributes—except one auxiliary value is corrupted. \(r'_B\) is mediocre everywhere.
\(\min\) picks \(r'_B\): the single 0.1 destroys \(r'_A\).
The weighted sum picks \(r'_A\): two rare hits outweigh one bad attribute.
The graph represents Alice, Bob, Cathy, Diane, Ed, Fred and Grace. A vertex is a person; an edge signifies a connection such as friendship.
The network is “anonymised”: people are associated only with vertex numbers.
Alice has three friends: Bob, Cathy and Ed. Alice knows Cathy is friends with everyone except Ed.
Can you de-anonymise the graph? What else do you learn besides a mapping from pseudo-identifiers to names?
Alice has three friends: Bob, Cathy and Ed. Cathy is friends with everyone except Ed.
Warm-up graph. d and e can be swapped without changing a single edge.
still unnamed — and the last edge leaks anyway
Three new positive edges — plus every non-edge she can now assert (Ed is connected to nobody but Alice and Bob) and the structure itself.
Consider an “anonymisation” procedure for releasing ages. Instead of the true age \(x\), the release contains
where the parameters \(\alpha\) and \(\beta\) are secret and shared across the table.
Alice is 25 (ID 1) and knows her friend Cathy (ID 5), age 29, is in the table. Can Alice guess the other ages? Justify your answer.
| ID | Age (perturbed) |
|---|---|
| 1 | 40 |
| 2 | 34 |
| 3 | 52 |
| 4 | 28 |
| 5 | 48 |
| 6 | 22 |
| 7 | 92 |
Alice: true 25 → released 40. Cathy: true 29 → released 48.
Solve for \(\alpha\) and \(\beta\), then write the inverse transformation before touching the rest of the table.
Two unknown parameters. Two distinct known input–output pairs give two independent equations, so \(\alpha=\Delta y/\Delta x\) and \(\beta\) follow.
| ID | released \(y\) | true \(x\) |
|---|---|---|
| 1 | 40 | 25 |
| 2 | 34 | 22 |
| 3 | 52 | 31 |
| 4 | 28 | 19 |
| 5 | 48 | 29 |
| 6 | 22 | 16 |
| 7 | 92 | 51 |
Any of the eight. Write four short lines — this is the routine you will need in the exam, and in the assignment.
What object was it? Set, multiset, sequence, sparse vector, graph, equations, constraints.
What did the adversary already know before the release?
One sentence, in words, with no formula in it.
Name one thing the evidence does not settle — an unresolved identity, an assumed probability model, a threshold you would have to pick.
Material that did not fit a 50-minute core path. Jump here on demand, or leave it for self-study.
The supplied solution treats every possible dataset multiset as equally likely. Sampling 200 people independently from a population would induce a different distribution over multisets.
But the number \(0.80\) is only meaningful once you say how the dataset was generated.
Also: non-uniqueness does not guarantee safety when every matching row carries the same sensitive value.
A database \(D\) is \((\theta,\omega)\)-de-anonymised with respect to auxiliary information \(\Aux\) if there exists an algorithm \(A\) which, on inputs \(D\) and \(\Aux(r)\) where \(r\) is in \(D\), outputs \(r'\) such that
\[\Pr\bigl[\Sim(r,r')>\theta\bigr]\ge\omega\]The attack does not have to return the exact row. Returning any record more than \(\theta\)-similar to the target already counts; \(\omega\) is how often it must manage that.
Sparsity says records have no close neighbours. De-anonymisation says an algorithm can find the right one anyway—that is the amplification of background knowledge.
radius \(1-\theta\) in dissimilarity, so the ring holds every record more than \(\theta\)-similar to \(r\) — here, nobody
the guess \(r'\) lands inside the ring
succeeds at least \(\omega\) of the time
The lecture's question back to you: where could \(\Aux\) come from to de-anonymise the Netflix dataset?
The question is not “does the average subscriber care about their viewing history?” but “is there any subscriber whose privacy this release compromises?”
A film history can expose political or sexual preferences. And forward privacy: once a viewing history is linked to a person, a fresh identity created later can still be traced back to it.
Robust to noise: wrong ratings and wrong dates in the adversary's background knowledge do not break the attack.
More aux than you think: the paper also uses the approximate number of films a user rated and the date they joined Netflix.
Four houses stand next to each other. Their colours are blue, red, yellow and green. Each resident is a golfer, skater, basketball player or tennis player; keeps a cat, parrot, dog or horse; and likes avocado, grapes, apples or oranges.
Given the auxiliary information below, who owns the cat?
Vocabulary normalisation: “keeps birds” refers to the only bird in the pet list—the parrot.
Start with the three high-leverage clues, then add the rest one at a time.
Which assumption creates a contradiction?
| Q | Answer |
|---|---|
| 1 | \(\dbinom{N}{K}=\dfrac{N!}{K!\,(N-K)!}\) |
| 2 | \(100\times 8\times 2 = 1600\) record types |
| 3 | \(\dbinom{1798}{199}\) — multiset of 199 from 1600 types, with \(r\) fixed |
| 4 | Quasi-ID (age, location): unique with probability \(\dfrac{799}{998}\approx 0.80\); a homogeneous group discloses even without uniqueness |
| 5 | A (\(N\) rows, \(M\) columns) has the higher \(\epsilon\); B is the sparser dataset |
| 6 | Rarity weighting and min → sum; better with reliable rare attributes and noisy aux, worse with erroneous rare attributes or an unrescaled \(\alpha\) |
| 7 | 1 = Alice, 5 = Cathy, 2 = Ed, 3 = Bob; 4/6/7 stay ambiguous; new edges: Bob–Ed, Bob–4, 6–7 |
| 8 | \(\alpha=2,\ \beta=-10\), so \(x=\dfrac{y+10}{2}\) — every age recovered |
| 9 | The skater, in house 1 |