Differential privacy properly
Why it matters "We only publish anonymous statistics" used to sound safe. Earlier in this course you saw that clever questions about a dataset can still single out one person. Differential privacy is the tool that puts a hard, measurable limit on that, and its central idea, the privacy budget, is something you can implement in an afternoon.
Teaching code, not for real use: the randomness in this module's labs is seeded so grading is repeatable, which real privacy systems must never do. Real systems use vetted differential privacy libraries that also handle rounding and other subtle leaks. Never copy teaching code into a product.
The promise
Imagine a survey that is published with and without your answer. If the two published results look almost the same, then nobody reading them can tell whether you took part, let alone what you said. That is the whole promise.
Differential privacy (DP): a guarantee that the output of an analysis barely changes whether or not any one person's data is included. It is achieved by adding carefully sized random noise.
Epsilon: the number that says how much "barely" means. Small epsilon (say 0.1) means lots of noise and strong privacy; large epsilon (say 5) means little noise and weak privacy. For a simple count, adding Laplace noise with scale 1 / epsilon gives epsilon-DP, because one person can change a count by at most 1.
The budget
Here is the catch. Ask the same noisy question many times and average the answers: the noise cancels, as the maths lesson showed, and the true count appears. So every answer leaks a little, and the leaks add up.
Composition: when you answer several questions about the same people, their epsilons add. Answering with epsilon 0.25 four times costs 1.0 in total.
Privacy budget: the total epsilon you allow for a dataset. Every answer spends some. When the budget is gone, you stop answering, however politely the analyst asks.
Think of a prepaid card: each question costs something, the balance only goes down, and a refused question costs nothing. The bookkeeping is what you will build. The noise comes ready-made from laplace(scale, rng) in the practice world.
Local and central DP in the real world
Local DP: each device adds noise before sending anything, so the company never holds true values (randomised response is local DP). Central DP: a trusted server holds the true data and adds noise only to the results it publishes.
Apple announced in 2016 that it uses local differential privacy to learn things such as popular new words and emoji from devices without collecting what any one person typed. Google's early system, RAPPOR (2014), was also local, used for collecting statistics from its browser. Local DP needs a great deal of noise per person, so it only gives useful answers for very large crowds and fairly common values. Much of Google's later published work, such as its open-source differential privacy library (2019), uses the central model, where far less noise is needed for the same epsilon, at the price of trusting the server with the raw data.
Neither model is "the right one". Local DP protects you even from the company; central DP gives more accurate statistics. Secure aggregation, two lessons on, is one way to get some of both.
In other languages
The same budget check in JavaScript:
function spend(budget, epsilon) {
if (epsilon <= 0) return false;
if (budget.spent + epsilon > budget.total + 1e-9) return false;
budget.spent += epsilon;
budget.log.push(epsilon);
return true;
}And in Rust, where the borrow rules make "change nothing on refusal" explicit:
fn spend(b: &mut Budget, eps: f64) -> bool {
if eps <= 0.0 || b.spent + eps > b.total + 1e-9 { return false; }
b.spent += eps;
b.log.push(eps);
true
}Why the 1e-9?
Computers store decimals approximately: 0.1 + 0.2 is 0.30000000000000004 in Python. Without a tiny allowance, spending exactly the whole budget in small steps could be wrongly refused. Real libraries handle this more carefully; a small allowance is enough here.
A common misconception
"Noise means the published numbers are wrong, so DP is useless." The noise is sized to hide one person, not the trend. A count of 412 published as 409 or 415 still tells the shop which pages are popular, while the count of 31 visitors to a sensitive page cannot be used to confirm that a particular person was one of them.
Recap
- DP promises that results barely change with or without any one person; epsilon measures "barely".
- For a count, Laplace noise with scale 1 / epsilon gives epsilon-DP.
- Epsilons add up across questions, so a budget must be tracked and enforced, and refusals cost nothing.
- Local DP (noise on the device) trusts nobody but needs huge crowds; central DP is more accurate but trusts the server.
Write four functions that manage a privacy budget. make_budget(total) returns {"total": total, "spent": 0.0, "log": []}. remaining(budget) returns total minus spent. spend(budget, epsilon) returns False and changes nothing if epsilon is 0 or less, or if spending it would take spent above total by more than 1e-9; otherwise it adds epsilon to spent, appends it to log and returns True. noisy_count(true_count, epsilon, budget, rng) returns None if spend refuses, otherwise true_count + laplace(1 / epsilon, rng). You are graded on the bookkeeping, not on the exact noisy numbers.
This lesson is locked
Lessons open one at a time. Finish the previous lesson to unlock this one.