Differential Privacy: Formal Privacy Guarantees

Every large Indian survey organisation faces the same problem. The National Sample Survey Office (part of the National Statistical Office under MoSPI) interviews hundreds of thousands of households on employment, consumption, and health, then publishes tables: average monthly spending by district, unemployment rate by age band and gender, literacy by caste category and block. The tables look harmless — they are sums, counts, and averages, not anyone's name. But statisticians have known since the late 1990s that publishing enough exact tables about the same underlying population is mathematically equivalent to publishing the underlying data itself. If a household is the only one in its village in a given age-and-income cell, a count of "3 people in this cell" combined with three other overlapping tables can pin that household down to a single row. This is called a database reconstruction attack: given enough linear constraints (each published statistic is one linear equation over the hidden micro-records), you can solve the system and recover individual rows almost exactly. The U.S. Census Bureau ran exactly this attack against its own 2010 release and reconstructed age, sex, race, and location for a large share of the population from public tables alone — precise enough that it changed how the Bureau builds every release since. This chapter is about the mathematical framework built to stop that: differential privacy, and the guarantee ε (epsilon) that makes "how private is this release?" a number you can compute, not a hope.

Why redacting names was never the guarantee it looked like

The instinct to protect privacy by deleting direct identifiers — name, Aadhaar number, roll number — and keeping "just the statistics" predates differential privacy by decades, and it fails in a specific, provable way. In 1997, computer scientist Latanya Sweeney showed that Massachusetts's "anonymised" hospital discharge records, stripped of name and address but keeping ZIP code, date of birth, and sex, could be re-linked to a public voter roll. She matched the record of the sitting governor, William Weld, and mailed his own diagnosis to his office to make the point. Her follow-up study found that ZIP code, birth date, and sex alone uniquely identify roughly 87% of the U.S. population — three "harmless" quasi-identifiers, none of them a name, are enough to break anonymity for almost everyone.

The lesson generalises beyond that one dataset: removing a list of fields is a syntactic property of a table. It says nothing about what a determined analyst, holding some outside information (a voter roll, a social media profile, another leaked dataset), can still infer. Differential privacy replaces "did we delete the obviously identifying columns?" with a question about the algorithm that produces the release, not the dataset itself: if my record were removed from the input entirely, how much could the output possibly change? If the answer is "barely at all, in a mathematically bounded sense," then no downstream observer — no matter what side information they hold — can learn much about whether you personally were in the data.

The formal definition

Let D and D′ be two databases that are neighbouring — identical except that D′ has one record added, removed, or changed relative to D (say, D′ is the NSSO sample with one household added). Let M be a randomised algorithm ("mechanism") that takes a database and produces an output — a published number, a noisy count, a released table. M satisfies ε-differential privacy if, for every pair of neighbouring databases D, D′ and every possible set of outputs S:

Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D′) ∈ S]

Read this literally: whatever output you observe, it was almost exactly as likely to have come from a database that included your record as from one that didn't — the two probabilities can differ by at most a multiplicative factor of e^ε. ε is the privacy loss parameter, often called the "privacy budget." When ε is small (0.1, 0.5), e^ε is close to 1, the two probability distributions are nearly indistinguishable, and an attacker's best guess about your presence in the data is barely better than a coin flip. When ε is large (5, 10), e^ε is large, the distributions can diverge sharply, and the guarantee becomes almost worthless — the released output can behave very differently depending on whether your one record was there. Crucially, ε is not a property of the data; it is a property of the mechanism M, chosen by whoever designs the release, and it must hold for every possible neighbouring pair, not just the "easy" ones — this is what makes it a formal, worst-case guarantee rather than a statistical average.

Worked example 1: randomized response, a mechanism a class can run with two coins

Before building anything with computers, it helps to see ε come out of the simplest possible mechanism — one a teacher could actually run in a classroom. Suppose a school wants to survey 40 students on a sensitive yes/no question: "Have you ever used unfair means (a phone, a chit) in an online unit test?" Nobody wants to answer honestly to a teacher's face. Instead, each student is asked to use Warner's randomized response mechanism, first published in 1965, long before "differential privacy" had a name, but it satisfies the same definition:

• With probability p = 0.75, answer truthfully.
• With probability 1 − p = 0.25, ignore the true answer and flip a fair coin: heads → answer "yes", tails → answer "no".

No one, including the teacher, can tell from a single "yes" whether it was the truth or the coin. To find ε, compare the two ways a "yes" answer could arise, treating "true answer = yes" and "true answer = no" as the two neighbouring inputs for a single individual (this is local differential privacy — the noise is added by each respondent, before any data is collected centrally, so there is no trusted collector required at all):

Pr[answer = yes | truth = yes] = p·1 + (1 − p)·0.5 = 0.75 + 0.125 = 0.875
Pr[answer = yes | truth = no] = p·0 + (1 − p)·0.5 = 0 + 0.125 = 0.125

The worst-case ratio between these is 0.875 / 0.125 = 7, so e^ε = 7, and ε = ln(7) ≈ 1.9459. This can be checked without a calculator's black box:

p = 0.75

p_yes_given_yes = p + (1 - p) * 0.5
p_yes_given_no  = (1 - p) * 0.5

ratio = p_yes_given_yes / p_yes_given_no

import math
epsilon = math.log(ratio)

print(round(ratio, 4), round(epsilon, 4))

Tracing it: p_yes_given_yes = 0.75 + 0.25×0.5 = 0.875. p_yes_given_no = 0.25×0.5 = 0.125. ratio = 0.875/0.125 = 7.0. epsilon = ln(7.0) = 1.94591…, which rounds to 1.9459. The program prints 7.0 1.9459. Notice the trade-off directly in the formula: raising p (more honesty, less noise) pushes the ratio further from 1 and ε upward — more useful data, weaker privacy. Lowering p toward 0.5 pushes ε toward 0 — closer to pure coin-flip noise, near-total privacy, but the teacher can barely estimate the true cheating rate at all. This tension between ε and usefulness is not a flaw to engineer away; it is the entire content of differential privacy — the framework's job is to make that trade-off a number you choose deliberately, instead of an accident of "we redacted the obvious fields and hoped."

Sensitivity: how far can one record move the answer?

Randomized response works record by record, but most useful statistics — a count, a sum, a mean — are computed centrally over the whole database, then released with noise added once to the final number. To calibrate how much noise is enough, you need the mechanism's global sensitivity, Δf: the largest amount the true answer f(D) can change between any two neighbouring databases.

For a counting query — "how many of the 40 students failed the last unit test?" — adding or removing one student's record changes the count by at most 1, so Δf = 1, regardless of how large the class is. For a sum query — "total marks scored across the class, each mark out of 100" — one student's record can shift the sum by anywhere from 0 to 100 (the largest possible single mark), so Δf = 100. Sensitivity depends on the query, not the database size: a sum over unbounded values (say, someone's income with no cap) technically has infinite sensitivity, which is exactly why real disclosure-control systems top-code or clip extreme values before summing — without a bound on Δf, no finite amount of noise can produce a finite ε.

Worked example 2: the Laplace mechanism, computed exactly

Take the counting query above: of 40 students, the true count of those who failed is f(D) = 6. Sensitivity Δf = 1. Choose a privacy budget ε = 0.5 (a fairly strong, cautious setting). The classic mechanism for numeric queries, due to Dwork, McSherry, Nissim and Smith (2006), is to add noise drawn from a Laplace distribution with scale b = Δf / ε:

M(D) = f(D) + Lap(b),   b = Δf/ε = 1/0.5 = 2

The Laplace distribution has density f_Lap(x; μ, b) = (1/2b)·e^{−|x−μ|/b} — a sharp peak at the true value μ that decays exponentially on both sides, controlled by scale b. To see why this specific noise shape gives exactly e^ε-differential privacy, compare the two neighbouring databases D (f(D) = 6, the real class) and D′ (f(D′) = 7, the same class plus one more student who also failed). Check the density ratio at the reported output x = 6:

import math

def laplace_pdf(x, mu, b):
    return (1 / (2 * b)) * math.exp(-abs(x - mu) / b)

epsilon, sensitivity = 0.5, 1
b = sensitivity / epsilon          # 2.0

f_D, f_D_prime = 6, 7              # neighbouring counts
x = 6                              # the reported (noisy) output

ratio = laplace_pdf(x, f_D, b) / laplace_pdf(x, f_D_prime, b)
bound = math.exp(epsilon)

print(round(ratio, 4), round(bound, 4))

Tracing by hand: laplace_pdf(6, 6, 2) = (1/4)·e⁰ = 0.25. laplace_pdf(6, 7, 2) = (1/4)·e^−1/2 = 0.25 × 0.60653 = 0.15163. ratio = 0.25 / 0.15163 = 1.64872. bound = e^0.5 = 1.64872. The program prints 1.6487 1.6487 — the two match to four decimal places, because they are the same quantity: at the point x = f(D), the density ratio hits its maximum, exactly e^{|f(D)−f(D′)|/b} = e^Δf/ε = e^ε. This is not a coincidence of this example; it is the general proof that the Laplace mechanism achieves exactly ε-DP for any counting or sum query, with equality attained precisely at the true value of the smaller-magnitude database. The diagram below plots both curves from this worked example — the overlap you see is the privacy guarantee: an attacker staring at any single reported number cannot confidently tell whether it came from the 40-student class or the 41-student class, because the two bell-shaped curves sit almost on top of each other.

Composition: why a privacy budget is spent, not reused

Real analysis is never one query. If the NSSO releases ten different cross-tabulated statistics from the same underlying sample, each computed with its own ε = 0.5 Laplace mechanism, the sequential composition theorem says the combined release satisfies (ε₁ + ε₂ + … + ε₁₀)-differential privacy — the losses add. Ten queries at ε = 0.5 each compose to a total ε = 5.0, and e⁵ ≈ 148.41: the bound on how differently the whole release could behave with or without your record has grown from a tight 1.65× to a nearly meaningless 148×. This is precisely the mechanism behind the reconstruction attack from the opening paragraph — publishing many exact, zero-noise statistics from the same data is the ε → ∞ extreme of this same theorem, where the "noise" is zero and every additional table adds an unbounded amount to the total privacy loss. Composition is why production differential-privacy systems track a fixed total budget across a deployment's entire lifetime, and why data curators must decide up front how many queries a dataset will ever answer, not add "just one more" indefinitely.

Where the formal guarantee is actually deployed

The U.S. Census Bureau's 2020 Census used a mechanism called the TopDown Algorithm, built on differential privacy, to inject calibrated noise into every published table before release, with a formal, publicly stated total ε budget — the first time a national census committed to a provable numeric privacy guarantee rather than ad hoc suppression rules. Apple has shipped local differential privacy since iOS 10 (2016) for telemetry like emoji suggestions and QuickType predictions — noise is added on the phone itself, the exact local-DP pattern from the randomized-response example, before anything leaves the device. Google's RAPPOR, published in 2014, uses a related randomized-response-style mechanism inside Chrome to collect statistics on browser settings without any individual report being attributable. India's statistical releases, by contrast, still lean on classical disclosure-control heuristics — dropping names, coarsening geography to state or district level, top-coding extreme incomes — the same category of technique Sweeney's 1997 attack defeated. That is not a criticism of the people running those releases; it reflects that formal DP tooling is a genuinely recent, computation-heavy addition to a statistical agency's pipeline, and adopting it means explicitly trading some table accuracy for a provable ε, a decision every one of the deployments above had to make in public.

The misconception: "we deleted the names, so it's anonymous"

The single most common misunderstanding a student carries into this topic is treating anonymisation as something you do to a dataset — strip identifying columns, and the rest is safe to publish. Differential privacy is a property of the mechanism, not the data. A dataset itself cannot be "ε-differentially private" any more than a photograph can be "in focus" independent of the camera that took it — ε describes a randomised algorithm's worst-case behaviour across all neighbouring inputs, checked before a single number is released, and it holds regardless of what outside information (a voter roll, a leaked table, a Sweeney-style linkage) an attacker brings to bear afterward. Deleting names is a syntactic transformation with no bound on inferential leakage — as the reconstruction attack and the Governor Weld case both show, an attacker who never sees a name can still recover the individual. A mechanism satisfying ε-DP, by contrast, comes with a mathematical proof that holds against any attacker, with any amount of outside knowledge, forever — which is exactly the guarantee "just remove the identifiers" was never able to make.

Active recall

Attempt each question before reading its answer.

1. A survey of 250 students uses Warner's randomized response with truth probability p = 0.6 (else a fair coin, as in worked example 1). Derive ε.
2. Using the Laplace mechanism with Δf = 1, what noise scale b is needed to achieve ε = 0.2? What does the change in b (compared to the worked example's b = 2) tell you about the trade-off?
3. Two independent counting queries are each released with ε = 0.3 using the Laplace mechanism, computed sequentially on the same database. What is the combined ε, and what is e^ε for the combined release?
4. True or false, with justification: "Differential privacy guarantees that no released output can ever reveal whether a specific student's record was in the database."
5. A query sums exam marks (each mark an integer from 0 to 100) across a class. What is the global sensitivity Δf of this sum query, and why is it different from the sensitivity of a counting query?
6. In worked example 2, ε was 0.5. If a stricter ε = 0.1 were required instead for the same count query, compute e^0.1 and the new noise scale b. What does this imply about how "sharp" the released number can be trusted to be?

Answers.

1. Pr[yes|yes] = p + (1−p)(0.5) = 0.6 + 0.2 = 0.8. Pr[yes|no] = (1−p)(0.5) = 0.2. Ratio = 0.8/0.2 = 4, so e^ε = 4 and ε = ln(4) ≈ 1.3863. Lower truth probability than the p = 0.75 example (0.6 vs 0.75) correctly produced a smaller ε — more randomisation, stronger privacy, as expected.

2. b = Δf/ε = 1/0.2 = 5, compared with b = 2 for ε = 0.5. A smaller ε (stricter privacy) forces a larger noise scale — the Laplace curve gets wider and flatter, so any single reported count is a noisier, less reliable estimate of the true value. Privacy and utility move in opposite directions through b.

3. By sequential composition, total ε = 0.3 + 0.3 = 0.6. e^0.6 ≈ 1.8221. Even though each individual release looks tight (e^0.3 ≈ 1.35), asking the same database two related questions already loosens the combined worst-case bound to 1.82×.

4. False. Differential privacy bounds the ratio of probabilities (by at most e^ε), not the possibility of any output occurring. Any specific output remains possible whether or not a given record was included — the guarantee is that its probability under either scenario is close, so an attacker's confidence shift is bounded, not eliminated. With ε = 5 (as in the ten-query composition example), a factor of 148 is technically still "bounded" but gives almost no real protection — "bounded" is not the same as "small."

5. Δf = 100. One student's record can be added, removed, or changed such that the sum shifts by anything from 0 up to the maximum possible single mark, 100 — unlike a counting query, where a single record can only ever add or subtract exactly 1 regardless of its content. Sensitivity depends on the largest possible per-record swing in the query's value, not merely on whether one record changed.

6. e^0.1 ≈ 1.1052, noticeably tighter than e^0.5 ≈ 1.6487 — an attacker's ability to distinguish D from D′ is now bounded by only about a 10.5% multiplicative shift instead of 65%. The cost is b = Δf/ε = 1/0.1 = 10, five times the noise scale of the original example, so any single released count could plausibly be off from the true value by several students in either direction — a much noisier, less individually trustworthy number, even though it is a far stronger privacy guarantee in aggregate over many releases.

Think About It

Think about this: How would you explain differential privacy: formal privacy guarantees to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where differential privacy: formal privacy guarantees is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting differential privacy: formal privacy guarantees to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind differential privacy: formal privacy guarantees, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.