Differential Privacy

"Private" and "anonymous" are informally understood terms that have been repeatedly shown to provide weaker guarantees than assumed. Re-identification attacks on supposedly anonymous datasets have revealed individuals' medical records, search histories, and location patterns. Differential Privacy (DP), introduced by Dwork, McSherry, Nissim, and Smith in 2006, provides a mathematical definition of privacy that makes precise claims verifiable: a mechanism is epsilon-differentially private if its output distribution changes by at most a factor of e^epsilon whether or not any single individual's data is included.

Intuitively, differential privacy guarantees that the output of a computation reveals essentially the same information regardless of whether any particular person's data was included. An adversary who sees the output of a differentially private mechanism gains at most epsilon units of information about any single person - and epsilon is a tunable parameter that precisely quantifies the privacy-utility tradeoff. Small epsilon (close to 0) provides strong privacy guarantees but requires more noise to be added, reducing accuracy. Larger epsilon allows higher accuracy but weaker privacy.

The standard mechanism for achieving differential privacy is adding calibrated random noise to a computation. For numerical statistics, the Laplace mechanism adds Laplace-distributed noise proportional to the query's sensitivity (how much the answer can change if a single person is added or removed) divided by epsilon. For more complex computations, the Gaussian mechanism adds Gaussian noise with standard deviation proportional to sensitivity and 1/epsilon. The randomness is what prevents an adversary from learning precise information about individuals: they see a noisy output that could plausibly have been produced by many different underlying datasets.

Differentially Private Stochastic Gradient Descent (DP-SGD) applies differential privacy to neural network training: in each mini-batch, gradients are clipped to a maximum norm (bounding sensitivity), then Gaussian noise is added to the clipped gradients before the update step. The privacy cost accumulates across all training steps, tracked by a privacy accountant that computes the total (epsilon, delta) guarantee for the full training run.

Differential privacy is deployed at scale by major technology companies. Apple uses DP to collect aggregate statistics on emoji usage, user preferences, and Health app usage without learning about individual users. Google uses DP in the US Census Bureau's disclosure avoidance system (the 2020 census), protecting individual households from re-identification. The Google Privacy Team released TensorFlow Privacy, an open-source library for training neural networks with differential privacy using DP-SGD.

The tradeoff between privacy and model quality is real and non-trivial. Strong privacy guarantees (epsilon < 1) typically require substantial noise, reducing model accuracy, particularly for small datasets or models that need to memorise rare patterns. Balancing privacy budgets across the multiple analyses that organisations want to perform from a single dataset requires careful privacy accounting.