Differential Privacy

Suppose a hospital publishes that 47% of its patients have a certain condition. Harmless — until you realize that yesterday the figure was 46%, and you happen to know exactly one new patient was admitted overnight. Two innocent statistics, subtracted, can leak a single person's private record.

For years the fix was to "anonymize" data by deleting names. It failed again and again: researchers re-identified individuals in supposedly anonymous medical, Netflix and AOL datasets by cross-referencing other public information. Removing the obvious identifiers was never enough.

Differential privacy, introduced by Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith in 2006, takes a radically different stance. Instead of scrubbing the data, it adds a precise amount of random noise to the answers, with a mathematical promise: whether or not your record is in the database, the published result looks almost exactly the same.

Twelve people answered a sensitive yes/no question. Below you see the exact count of "yes" answers and a differentially private count that has calibrated noise added. Flip any single person and compare how the two numbers react.

<p class="hint">{{hint}}</p>
<div class="people" id="people"></div>
<div class="readout">
  <div class="card"><div class="lbl">{{lbl_exact}}</div><div class="val" id="exact">7</div></div>
  <div class="card priv"><div class="lbl">{{lbl_private}}</div><div class="val" id="noisy">7</div></div>
</div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <label class="eps">{{lbl_eps}}
    <input id="eps" type="range" min="0.1" max="4" step="0.1" value="0.5">
    <span id="epsv">0.5</span>
  </label>
  <button id="requery" type="button">{{btn_requery}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.people { display: grid; grid-template-columns: repeat(6, 1fr); gap: 6px; margin: .4rem 0 .8rem; }
.person { height: 44px; display: flex; align-items: center; justify-content: center;
          font: 700 16px system-ui, sans-serif; border-radius: 8px; cursor: pointer;
          user-select: none; border: 1px solid #cdd9e3; background: #e8eef3; color: #1d3557;
          transition: all .12s; }
.person.yes { background: #1d3557; color: #fff; border-color: #16294a; }
.person.flagged { outline: 3px solid #f4a259; outline-offset: 1px; }
.readout { display: flex; gap: 12px; margin: .5rem 0; flex-wrap: wrap; }
.card { flex: 1; min-width: 140px; border: 1px solid #cdd9e3; border-radius: 10px; padding: .6rem .8rem; background: #fafcfe; }
.card.priv { border-color: #2a9d8f; background: #eef8f6; }
.lbl { font-size: .78rem; color: #556; text-transform: uppercase; letter-spacing: .03em; }
.val { font: 800 30px ui-monospace, monospace; color: #1d3557; }
.card.priv .val { color: #1d7d6e; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #444; }
.btns { display: flex; gap: .7rem; flex-wrap: wrap; align-items: center; }
.eps { font-size: .85rem; color: #333; display: flex; align-items: center; gap: .4rem; }
.eps input { vertical-align: middle; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

The exact count is a snitch: flip one person and it moves by exactly one, betraying that individual. The private count barely flinches — and because the noise is random, that same shift could have happened with or without them. Slide the privacy budget ε down for more noise and stronger privacy, up for a sharper but leakier answer. This tug-of-war between accuracy and privacy is the whole game, and it echoes the trade-offs behind cryptographic hashing.

What makes differential privacy different from earlier "anonymization" is that it is a proven mathematical guarantee, not a hopeful heuristic.

• The promise. A randomized analysis is ε-differentially private if, for any two datasets differing in a single person's record, every possible output is at most e^ε times as likely in one as in the other. Your presence can shift the odds, but only by a tightly bounded factor.
• Sensitivity. A simple counting query has sensitivity 1: one person changes the true count by at most one. That number sets how much noise you need.
• The Laplace mechanism. Add noise drawn from a Laplace distribution with scale 1/ε. Smaller ε means more noise and stronger privacy; this is provably ε-differentially private.
• The privacy budget. ε is a budget you spend. Every query leaks a little, and the leaks compose — ask too many questions and the total guarantee weakens. You cannot get unlimited accurate answers for free.

Unlike the open problems behind P vs NP, this isn't a question waiting for an answer: the guarantee is a theorem. The hard part is engineering — choosing ε, bounding sensitivity, and spending the budget wisely.

Differential privacy left the lab and now runs at the scale of nations and billions of phones:

• The US Census. For the 2020 Census, the Census Bureau adopted differential privacy as its official disclosure-avoidance system, injecting calibrated noise into published tables to protect respondents by law.
• Apple. Since iOS 10, Apple has used local differential privacy — noise added on your device before data ever leaves — to learn popular emoji, typing suggestions and health trends without reading any one user.
• Google and Microsoft. Google's RAPPOR and Microsoft's telemetry use the same idea to gather aggregate usage data privately.
• Private machine learning. Training models with differential privacy bounds how much any single training example can influence the result, limiting memorization of personal data.

The unifying lesson is a friendlier cousin of constraint-satisfaction problems like SAT: here the goal isn't to satisfy hard rules but to maximize usefulness subject to a hard privacy constraint.

Differential privacy reframes a vague worry — "could this leak my data?" — into a number you can reason about. By adding just enough calibrated noise, a database can answer questions about a whole population while giving every individual plausible deniability that is provable, not promised.

It is not magic. Stronger privacy costs accuracy, and a finite budget limits how many questions you may ask. But the next time you read a statistic from a census or your phone quietly improves its autocorrect, there is a good chance a careful sprinkle of randomness is keeping you, specifically, invisible in the crowd.