Anonymity sets and entropy

Hiding in a crowd

Imagine a station full of commuters in identical black coats. If you wear a black coat too, you hide among hundreds. If you wear a bright yellow one, the crowd you hide in is just you.

In lesson 50 you measured how much one person, Sam, stood out in a crowd. Here you measure the whole crowd of 5,000 synthetic browsers (made up by synthetic_browsers, no real people), to see how well everyone hides.

Group, then count

Pick some traits, say ["timezone", "language"]. Each browser's fingerprint is the tuple of those values, for example ("Europe/London", "en-GB"). A tuple works as a dict key, so collections.Counter can count how many browsers share each one:

from collections import Counter
Counter([("A", "x"), ("A", "x"), ("B", "x")])
# Counter({('A', 'x'): 2, ('B', 'x'): 1})

Every count is an anonymity set. A count of 1 is a unique browser. With all 13 traits, most of the 5,000 browsers turn out to be unique.

Entropy: one number for the whole crowd

In lesson 48 you used Shannon entropy to measure how mixed-up the characters of a text are. The same formula works on a crowd: for each anonymity set, take its share p of everyone, and add up -p * log2(p).

Example: four browsers with time zones A, A, B, C. Shares are 1/2, 1/4 and 1/4, so entropy is 0.5 x 1 + 0.25 x 2 + 0.25 x 2 = 1.5 bits.

Trap 1: the ceiling

A crowd of 5,000 can never show more than log2(5000), about 12.3 bits, because at that point everyone is already unique. So a study of 5,000 browsers that finds "12 bits" may be hitting the ceiling, not measuring the trait. And unique among 5,000 is not unique among billions. Bigger samples give bigger, more honest numbers.

Trap 2: adding traits up

Time zone and language travel together: most Asia/Tokyo browsers say ja-JP. Graphics card and system do too. So adding each trait's entropy on its own counts the same information several times. Your sum_of_parts will come out far above joint, the entropy of all traits measured together, and far above the 12.3-bit ceiling. The joint number is the honest one.

A common misconception

"High entropy means everyone is trackable." Entropy is an average. A crowd can have high entropy while a large group of people with very common setups still hides well. Look at both the average and how many people sit in small sets.

function entropyBits(rows, traits) {
  const counts = new Map();
  for (const r of rows) {
    const key = JSON.stringify(traits.map(t => r[t]));
    counts.set(key, (counts.get(key) || 0) + 1);
  }
  let bits = 0;
  for (const c of counts.values()) {
    const p = c / rows.length;
    bits -= p * Math.log2(p);
  }
  return bits;
}

func entropyBits(keys []string) float64 {
    counts := map[string]int{}
    for _, k := range keys {
        counts[k]++
    }
    bits := 0.0
    for _, c := range counts {
        p := float64(c) / float64(len(keys))
        bits -= p * math.Log2(p)
    }
    return bits
}