Differential Privacy

Social networks, financial records and medical records can all be represented as a dataset $x = (x_1, x_2, \ldots)$ whose rows describe people. Analysis draws information from those rows by correlating genotypes with phenotypes, matching medical outcomes to risk factors, publishing aggregate statistics, spotting outliers for intrusion detection and mining customer data to update a strategy.

Releasing aggregates while withholding the rows seems safer. Three attacks show why it is not a privacy guarantee.

The differential attack is the simplest. A small database makes it concrete. Publish the prefix sums of one column, $s_i = x_1 + \cdots + x_i$ for $i = 1, \ldots, n$. Every row is the difference of two published numbers, $x_i = s_i - s_{i-1}$, so these aggregate statistics determine the whole database. The same subtraction breaks any pair of overlapping groups. Ask how many people in the room did XYZ last night, then ask how many people other than the speaker did it; the difference of the two answers is a fact about one person.

The needle in a haystack attack works on genomic data. Aggregate statistics from a genome-wide association study can enable membership inference about whether a specific individual's genome sits in the case group, even when the group is large. The big bang attack combines statistics released from multiple overlapping datasets to reconstruct sensitive attributes outright. In each attack the published statistics can be inverted to recover private records.

What went wrong. In 2008 Homer and colleagues showed that a person's presence in a genome-wide association study cohort can be detected from published aggregate allele frequencies. The National Institutes of Health responded by restricting access to such data.

Two released datasets make the point concrete. In 2014 the NYC Taxi and Limousine Commission published 19 GB of taxi fare data whose identifiers, which looked like anonymized tokens, were MD5 (Message-Digest Algorithm 5) hashes of the driver's medallion and license number; once that was noticed the hashes were inverted against public records. The Netflix Prize dataset of 2006 to 2009, released to improve a recommendation engine, was de-anonymized by matching rating patterns against public IMDb (Internet Movie Database) reviews. The episode ended in a class action lawsuit.

Common mistake. Stripping names and identifiers feels like anonymization. In 2000 Latanya Sweeney showed that ZIP code, birth date and sex uniquely identify 87% of Americans. Ordinary attributes combine into fingerprints.

The deck draws four lessons.

• Privacy is a concern whenever a dataset is published.
• Releasing aggregates in place of raw rows does not remove the concern.
• Aggregates alone can break privacy.
• Overly accurate estimates of too many statistics are blatantly non-private. Accuracy is the attack surface. This is the recurring theme of the whole chapter.

The target for the rest of the chapter is a notion of privacy-preserving data analysis analogous to semantic security for encryption (where a ciphertext reveals nothing about its message): the analyst learns nothing new about Alice. The ideal form is sharper. The analyst learns the same thing whether Alice is in the dataset or is replaced by a random member of the population.

Differential privacy asks that the outcome of an analysis be roughly equally likely whether or not any individual joins the dataset. Picture the same randomized process run on two databases that differ in one person. The two output distributions come out nearly the same, so an observer can barely tell which database produced the result. Alice goes away or Bob joins; no one-row change moves the odds by much. Changing the dataset wholesale is allowed to change the answers completely. Apple, Google and Microsoft use the definition in production.

What went wrong. In 2017 Tang and colleagues measured daily privacy loss on Apple's macOS 10.12 reaching $\eps = 6$, far above what users expected. A differential privacy claim without a stated, enforced budget is unverifiable.

The definition has three important consequences.

• Everything an adversary learns about one person could have been learned from the rest of the dataset, even without that person's participation. Population facts still come through. Differential privacy (DP) cannot license decisions about specific individuals.
• The guarantee is worst-case, over all datasets and against unbounded adversaries.
• The probability is over the mechanism's coins, never over a distribution on datasets.

Common mistake. Differential privacy is read as a promise that nothing about an individual can be learned. The guarantee is narrower: it bounds how much one record can move the output distribution. Aggregate facts such as smoking causing cancer still come through.

The workhorse query family is counting queries. A counting query is a predicate $q: \mathcal{X} \to \{0,1\}$ on rows, extended to datasets by counting the fraction of rows that satisfy it:

Four subfamilies recur.

• Point functions $q_y(w) = 1$ iff (if and only if) $w = y$ answer the histogram.
• Threshold functions $q_y(w) = 1$ iff $w \le y$ answer the cumulative distribution.
• Attribute means $q_j(w) = w_j$ on $\mathcal{X} = \{0,1\}^d$ answer the one-way marginals, the fraction of the dataset possessing each attribute.
• Conjunctions of $t$ literals answer the $t$-way marginals. For instance $q(w) = w_2 \wedge \neg w_4$ asks what fraction of individuals have lung cancer and are non-smokers. Answering all such queries amounts to the $t$-way contingency table.

Postprocessing lets a curator hand the output to anyone, in any further processed form, without spending more privacy budget. Privacy is a property of the release. Nothing done to the release afterwards can amplify it.

Common mistake. The guarantee is treated as a property of the dataset. It attaches to the computation that produced the release. The same underlying data released twice spends privacy budget twice; each release is accounted separately.

Composition turns the definition into an engineering tool. Privacy loss accumulates across analyses, so a total budget can be split among many mechanisms. Private pieces can be combined into a larger analysis with a known total cost. The definition is immune to auxiliary information, current and future, yields group privacy automatically and composes.

Worked number. Five counting queries at $\eps = 0.2$ each spend a total of $5 \times 0.2 = 1.0$ under basic composition. A sixth identical query raises the bound to $1.2$, so a strict budget of $1.0$ permits only the first five.

The oldest private mechanism predates the definition by decades. The survey question is "did you XYZ last night?" Each respondent runs the two-coin protocol in the stage below. Flip a coin. On tails answer honestly. On heads flip a second coin and answer YES on heads and NO on tails, ignoring the question entirely.

History. Stanley Warner proposed randomized response in 1965 in the Journal of the American Statistical Association, four decades before the definition existed. It is the ancestor of what is now called local differential privacy.

The arithmetic is short. A person who did it answers YES with probability $1/2 + 1/4 = 3/4$. A person who did not answers YES with probability $1/4$. The worst-case ratio of the two is $3$, so the protocol is $\eps$-DP ($\eps$-differentially private) for $\eps = \ln 3 \approx 1.098$. The symmetric ratio $\Pr[\text{NO} \mid \text{did}]\,/\,\Pr[\text{NO} \mid \text{did not}] = 3$ gives the same bound, since the definition bounds the ratio in both directions.

Accuracy comes from inverting the expectation. The expected YES fraction is $\frac{1}{4}(1 - p) + \frac{3}{4}p = \frac{1}{4} + \frac{p}{2}$ where $p$ is the true fraction, so the unbiased estimator (whose expectation equals the true $p$) is $\hat{p} = 2 \cdot \#\text{YES}/n - 1/2$. Chebyshev's inequality bounds the error by $O(1/\sqrt{n})$, so the estimate improves with the room size and the price of privacy is a constant factor in the variance.

The mechanism generalizes to any counting query $q$. Answer each row truthfully with probability $1/2 + \eps$ and flip the answer with probability $1/2 - \eps$. On neighboring datasets differing in row $j$, the output ratio telescopes to the single changed row:

for $\eps \le 1/4$, giving $O(\eps)$-DP. The estimator is unbiased after the linear correction $\hat{y} = \frac{1}{n}\sum_i \frac{1}{2\eps}(y_i - 1/2 + \eps)$. Its variance is at most $1/(4n\eps^2)$, so Chebyshev gives error $O(1/\sqrt{n}\,\eps)$. Randomized response pays $1/\sqrt{n}$; the next mechanism pays $1/n$.

The second mechanism perturbs the answer instead of the input. For a counting query, answer $M(x) = q(x) + \text{noise}$. Choose the noise distribution so that neighboring datasets, whose answers differ by at most $1/n$, produce densities within a factor $e^{\eps}$ at every point.

Common mistake. Any noise added to a statistic is assumed to make it private. The guarantee needs noise calibrated to the query's sensitivity inside a mechanism with a proof, such as the Laplace mechanism. Undocumented ad hoc noise carries no bound at all.

The maximum change in a query's answer under a single row change is its sensitivity, $\Delta = \max_{x \sim x'} |q(x) - q(x')|$ over neighboring datasets. A counting query over $n$ rows has sensitivity $1/n$, since changing one row moves the answer by at most $1/n$. The Laplace scale is the sensitivity divided by $\eps$, hence $\sigma = 1/(\eps n)$. A query over fewer people gets wider noise. The same query over 100 rows uses ten times the noise of the same query over 1000. This calibration, noise matched to how much one row can move the answer, is the pattern every mechanism in the chapter follows.

Worked number. Summing salaries bounded at $200{,}000$ gives sensitivity $200{,}000$. At $\eps = 0.1$ the Laplace scale is $2{,}000{,}000$, which swamps the answer. Clip salaries at $50{,}000$ first: the scale drops to $500{,}000$ and the noise falls fourfold.

Common mistake. A smaller $\eps$ is treated as a free win. The Laplace scale equals sensitivity divided by $\eps$: halve $\eps$ and the noise doubles. Stronger privacy always trades against accuracy.

The accuracy side uses the tails. $L(0, \sigma)$ has mean $0$, standard deviation $\sqrt{2}\,\sigma$ and exponentially vanishing tails, $\Pr[|L(0, \sigma)| > \sigma t] \le e^{-t}$. Hence for any $0 < \beta \le 1$,

so with high probability the error is $O(1/(\eps n))$. Compare randomized response's $O(1/(\eps\sqrt{n}))$: for a single counting query the Laplace mechanism is a square root of $n$ more accurate.

The mechanism is not specific to counting queries. The proof used only the bound $|q(x) - q(x')| \le 1/n$ on neighbors. The right generalization is the global $\ell_1$-sensitivity of an arbitrary query $q: \mathcal{X}^n \to \R^d$:

Section 3 introduced the privacy-loss random variable $\Lambda(y) = \ln \frac{\Pr[M(x) = y]}{\Pr[M(x') = y]}$. $\eps$-Differentially Private (DP) is the statement that $\Lambda \le \eps$ at every output. Approximate DP relaxes that pointwise bound. A second parameter $\delta$ permits an additive probability term in the bound for every output event. The parameter $\delta$ is a failure probability. It is priced per person in the dataset, so it must stay very small.

The relaxation buys three things.

• Gaussian (bell-curve) noise, which gives better accuracy in high dimensions.
• Advanced composition, which answers $k$ queries with cumulative loss about $\sqrt{k}\,\eps$ instead of $k\eps$.
• Compatibility with cryptography that simulates a trusted center, which a later lecture takes up.

The relaxation pays in the comparison with Laplace. For every vector, $\|y\|_2 \le \|y\|_1 \le \sqrt{d}\,\|y\|_2$. Take the multivariate mean query on $x \in \{0,1\}^{n \times d}$. Then $\Delta_1 \le d/n$ while $\Delta_2 \le \sqrt{d}/n$. Laplace adds noise of magnitude $O(d/(n\eps))$; the Gaussian mechanism needs $O(\sqrt{d}\,\ln(1/\delta)/(n\eps))$ for roughly the same accuracy, a factor $\sqrt{d}$ better.

The relaxed definition keeps the structural properties, with the slack propagating.

• Postprocessing preserves $(\eps, \delta)$ unchanged.
• Group privacy over distance $k$ gives $(k\eps,\; k\delta\, e^{(k-1)\eps})$.
• Basic composition of $k$ mechanisms gives $(k\eps, k\delta)$.

The mechanisms so far output numbers, while many private analyses must choose an object. The running example is a digital auction: one seller with infinitely many copies of a good, $n$ buyers with valuations $v_i$ and a price $p$ to be chosen to maximize the revenue $p \cdot |\{i : v_i \ge p\}|$. The revenue can drop sharply. If $v_1 = v_2 = 1$ and $v_3 = 3.01$, raising the price from $1$ to $1.01$ drops the revenue from $3$ to $1.01$. A private auction must choose a price without revealing the valuations that determine it.

The Laplace mechanism is a special case. Take $\mathcal{H} = \R$ and the score $s(x, h) = -|q(x) - h|$ for a query of sensitivity $\Delta$. Sampling with weight $\exp(-\eps|q(x) - h|/(2\Delta s))$ is the Laplace mechanism up to a factor of two in the noise. Revisiting the privacy proof removes the factor.

For the digital auction, discretize the prices to $\mathcal{H} = \{\alpha, 2\alpha, \ldots, 1\}$ and score each price by its revenue $s(x, p) = p \cdot |\{i : v_i \ge p\}|$. Since $p \le 1$ and one buyer changes the count by at most one, $\Delta s \le 1$. Rounding the optimal price $p^*$ down to the grid loses at most $\alpha n$ in revenue. The accuracy theorem loses another $\ln(1/\alpha)/\eps$. Choosing $\alpha = \ln(n)/(n\eps)$, the released price earns at least $p^* - \ln(n)/\eps$, which is near-optimal revenue with the valuations never released.

Private Probably Approximately Correct (PAC) learning follows the same pattern. The input is a concept class $\mathcal{C}$ of functions $\{0,1\}^d \to \{0,1\}$ and a training set of $n$ labeled examples from an unknown target $c^* \in \mathcal{C}$. The goal is to output $\hat{c}$ with low generalization error. In the non-private baseline, with $n = \Omega(\ln|\mathcal{C}|/\alpha^2)$ samples, some concept in $\mathcal{C}$ that makes zero training errors generalizes to error at most $\alpha/2$, by Chernoff's tail bound plus a union bound over the class. The private version applies the exponential mechanism with $\mathcal{H} = \mathcal{C}$ and score $s((x, y), h) = -|\{i : h(x_i) \ne y_i\}|/n$, which has sensitivity $\Delta s = 1/n$ and optimum $0$. The accuracy theorem then needs $n = \Omega\big(2\ln|\mathcal{C}|/\alpha^2 + \ln|\mathcal{C}|/(4\alpha\eps)\big)$. The output has generalization error at most $\alpha$. Privacy costs one extra term in the sample complexity, logarithmic in the class size and inverse-linear in $\eps$.

The last application is answering a whole set $\mathcal{Q}$ of $k$ queries. The naive route splits the budget. Laplace with $\eps_i = \eps/k$ per query and basic composition gives per-query error $O(k/(\eps n))$ and a uniform error $\alpha \le O(k \ln k/(\eps n))$ over all answers. The Gaussian mechanism with advanced composition instead gives $\alpha \le O(\sqrt{k \ln k \ln(1/\delta)}/(\eps n))$, which answers $k = o(n^2)$ queries accurately. Beyond that, per-query noise is the wrong tool, so the next section changes strategy.

The mechanism is the exponential mechanism with the synthetic datasets as objects and score $s(x, y) = -\max_{q \in \mathcal{Q}} |q(y) - q(x)|$. Output each $y \in \mathcal{X}^m$ with probability proportional to $\text{weight}(y) = \exp(-\eps n \cdot \max_{q} |q(y) - q(x)|/2)$. Privacy follows from the exponential mechanism's theorem at $\eps$.

Accuracy has two halves. For existence, a random sample $y^*$ of $m$ rows from $x$ satisfies $\mathbb{E}[q(y^*)] = q(x)$. Chernoff's tail bound plus a union bound over $\mathcal{Q}$ shows that with $m = O(\log|\mathcal{Q}|/\alpha^2)$ rows, some small dataset approximates every query to within $\alpha$. For sampling, the exponential mechanism's accuracy theorem, with $\Delta s = 1/n$ and $|\mathcal{H}| = |\mathcal{X}|^m$, shows the mechanism outputs such a dataset with high probability. Substituting $\alpha/2$ for $\alpha$ and solving gives the bound in the theorem.

The downside is computational. The exponential mechanism enumerates all of $\mathcal{Y}$, so the running time is $\Omega(|\mathcal{X}|^m) = \Omega(|\mathcal{X}|^{O(\log|\mathcal{Q}|/\alpha^2)})$. Answering all conjunction queries $\mathcal{Q}^t_{\wedge}(d)$ with error tending to zero requires $n = \omega(d^2/\eps)$ this way. Private multiplicative weights is the state of the art for linear queries $q: \mathcal{X} \to [0,1]$. It reaches the same accuracy $\alpha \le O(\sqrt{\log|\mathcal{X}| \cdot \log(1/\delta) \cdot \log|\mathcal{Q}|}/(\eps n))$ in time polynomial in $|\mathcal{Q}|$, $|\mathcal{X}|$ and $n/\alpha^2$.

Take $\mathcal{X} = \{0,1\}$, so a dataset is a vector $x \in \{0,1\}^n$. A normalized inner-product query uses a selector $q \in \{0,1\}^n$ for a subset of the population. The answer $\langle q, x\rangle/n$ measures the correlation between that subset and the attribute. These can be rewritten as counting queries.

The corollary is the punchline. A mechanism answering all $2^n$ normalized inner-product queries with $\alpha \le 1/40$ is blatantly non-private, since $4\alpha \le 1/10$. Additive error $\Omega(1)$ is therefore necessary for that many queries. The SmallDB error is tight. Dinur and Nissim strengthened this to an efficient attack. For any mechanism answering all such queries with accuracy $O(\alpha n)$, an efficient attacker reconstructs all but $O(\alpha^2)$ positions using only $O(n)$ queries. That result shows the Laplace and Gaussian mechanisms are tight as well.

What went wrong. In 2019 the United States Census Bureau disclosed that its staff had reconstructed individual records for about 46% of the 2010 population from published tables alone. Table releases are themselves a leakage channel; the 2020 census moved to differential privacy.

Reconstruction also explains why the definition of section 2 is worst-case. A guarantee that held only on average over some distribution on datasets would leave unprotected the datasets on which the published statistics invert. Those are the ones an adversary targets.

SmallDB and private multiplicative weights answer far more than $n^2$ queries over $\{0,1\}^d$ when $n$ is large compared to $d$, for instance $n \ge d^2$, in time exponential in $d$. This section shows the exponential time is inherent in the worst case. The proof tool is a traitor tracing scheme for preventing piracy over a broadcast channel.

A traitor tracing scheme gives each of $n$ users a secret key $sk_i$. The broadcaster encrypts a message $m$ under a broadcast key $bk$ as $c \leftarrow \Enc(bk, m)$. Every user decrypts with $m = \Dec(sk_i, c)$. If a coalition $S \subseteq [n]$ of users pools its keys and builds a pirate decoder $\mathbf{P}$, the tracing algorithm $\Tag(tk)$, given the tracing key $tk$, identifies at least one member of the coalition with high probability. Two pirate models matter.

• A stateless pirate is a program $\mathbf{P}$ handed to the tracer, useful if it decrypts honest ciphertexts.
• A stateful pirate is queried by the tracer on ciphertexts $c_1, \ldots, c_k$. Cooperativeness requires it to keep decrypting honest ciphertexts even after seeing malformed ones.

The reduction has four steps.

1. Set up the traitor tracing scheme with $n + 1$ users.
2. Build a dataset $x$ holding the secret keys of all users except one, chosen at random.
3. Define the counting queries $q_c(sk_i) = \Dec(sk_i, c)$. Then $M(x)$ approximates, within $\alpha$, the number of users in $x$ whose key decrypts $c$ to $1$. For a valid encryption of $m$, rounding recovers $m$ since $\alpha < 1/2$.
4. Build the pirate program $\mathbf{P}((sk_i)_{i \in S}, c_1, \ldots, c_k) = (M(x, q_{c_1}), \ldots, M(x, q_{c_k}))$. Accuracy makes $\mathbf{P}$ cooperative. Postprocessing keeps it differentially private.

Tracing now contradicts privacy. By traceability, $\Tag$ outputs some coalition member with probability close to $1$, so for large $n$ some user $i^*$ is output with probability at least $1/2n$. Remove $i^*$ from the dataset. By $(1, 1/10n)$-DP that probability drops by at most a factor $e$ plus $1/10n$, leaving at least $1/(2en) - 1/(10en) = \Omega(1/n)$. But $i^*$ is absent from the new dataset. A tracer for a secure scheme cannot identify an absent user. The contradiction forces $\mathbf{P}$ untraceable, hence superpolynomial, and $M$ with it. As a corollary, assuming one-way functions, for every $n = \poly(d)$ no polynomial-time $(1, 1/10n)$-DP mechanism answers more than $O(n^2)$ queries over $\{0,1\}^d$ within $\alpha < 1/2$. The bound is tight, since $\Omega(n^2)$ counting queries can be answered accurately in polynomial time.

The concrete scheme behind the assumption is simple. Take any symmetric encryption $(\Enc, \Dec)$. The broadcast key is $bk = (sk_1, \ldots, sk_n)$. Encrypting a bit $b$ outputs $c = (\Enc(sk_1, b), \ldots, \Enc(sk_n, b))$; user $i$ decrypts the $i$-th component. Tracing uses hybrid ciphertexts $\TrEnc(sk, i) = (\Enc(sk_1, 1), \ldots, \Enc(sk_i, 1), \Enc(sk_{i+1}, 0), \ldots, \Enc(sk_n, 0))$, under which users $j \le i$ decrypt to $1$ and users $j > i$ decrypt to $0$. The tracer encrypts columns at random cut points $i_1, \ldots, i_k$, permutes them, queries the pirate on all of them and records, for each cut $i$, the fraction $p_i$ of pirate answers equal to $1$. Since $p_0 = 0$ and $p_n = 1$, some consecutive pair satisfies $p_{i^*} - p_{i^* - 1} \ge 1/n$. This $i^*$ lies in the coalition. If it did not, the key $sk_{i^*}$ would be unknown to the pirate. Encryption security makes adjacent hybrids indistinguishable, so the pirate could only guess which column is which. With $s = O(n^2 \ln n)$ repetitions per cut, Chernoff tail bounds keep every innocent gap below $1/n$. Fingerprinting codes, which embed a traceable mark in each user's key, improve the query complexity to $O(n^2)$.

The same idea rules out efficient synthetic data. SmallDB-style mechanisms output a compact representation of all answers, which corresponds to stateless pirates. For natural query families, the construction switches to digital signatures. The dataset holds $n$ rows $(m_i, \mathbf{S}(sk^*, m_i), vk^*)$ signed under one key pair. For each verification key $vk$ one query asks what fraction of rows are valid signatures under $vk$. An efficient curator producing synthetic data accurate for $vk^*$ must include a row with a valid signature under $vk^*$. If the message is new, unforgeability is violated; if it comes from $x$, differential privacy is violated, since each $m_i$ can appear with probability at most $e^{\eps}/2^n + \delta$. Via the Probabilistically Checkable Proof (PCP) theorem the signature check can be expressed with 2-way conjunctions. The resulting theorem says that, assuming one-way functions, there is some $\alpha > 0$ for which no polynomial-time $(1, 1/10n)$-DP mechanism with $n = \poly(d)$ can output synthetic data approximating all queries in $\mathcal{Q}^2_{\wedge}(d)$ within $\alpha$.

Every mechanism so far assumed the data already exists. The last part of the deck asks where it comes from, meaning why anyone participates, why they report truthfully and whether participation needs compensation. This is mechanism design territory, where the inputs are held by self-interested agents and the goal is to design the rules so that truth-telling is the easy strategy.

Differential privacy gives useful game-theoretic guarantees. Approximate truthfulness survives composition. Truthfulness is approximately a dominant strategy (the best move whatever the other agents do) even for coalitions of $k$ agents, degrading by $O(k\eps)$. Both properties are hard to get in ordinary mechanism design. Both come without money.

Differential privacy makes every report approximately as good as every other report, including malicious ones. Privacy makes lying harmless, which also makes truth unnecessary. Getting people to report truthfully, once harmless lying is possible, may still require compensation. That problem is much harder.

Differential privacy also serves as a tool inside game theory. A Nash equilibrium assigns each player a strategy such that no player benefits from switching alone; a correlated equilibrium lets players condition on correlated signals, such as a traffic light, and contains every Nash equilibrium plus more. Differential privacy has applications to mechanism design with correlated equilibria, where the correlating signal must be produced without revealing any player's input.

The open end is verification. Strictly incentivizing truth-telling in private mechanism design is hard, with two exceptions: settings where responses are verifiable and settings where agents care about the outcome. The hard cases are the ones with no observed outcome at all, the prevalence of drug use or the rate of cheating in a class, where nothing outside the survey ever corroborates a report. The deck closes the chapter by naming the remaining modeling challenge of how people currently value privacy, how they should value it and what promises a mechanism can credibly make.

• Programming Differential Privacy (Near and Abuah). A code-first book where every chapter is executable Python with a live in-browser Binder button.
• The Algorithmic Foundations of Differential Privacy (Dwork and Roth). The canonical theory text; its chapter order matches this course.
• A friendly introduction to differential privacy (Desfontaines). Minimal math with custom diagrams, plus separate posts on delta and on local versus central Differential Privacy (DP).
• OpenDP. A production DP library with real deployment epsilon choices.
• Wikipedia: Differential privacy. The informal then formal definition, a worked database example, the Laplace mechanism and composition.
• Wikipedia: Laplace distribution. Density plots and the quantile function used for sampling.

Further reading: Vadhan (2017), The Complexity of Differential Privacy, Chapter 7 of Tutorials on the Foundations of Cryptography (Yehuda Lindell, ed.), Springer.