CS 1261: Fairness, Privacy, and Cryptography
Lecture Notes

Course Taught by Professor Cynthia Dwork
Notes Compiled by Cristiana Murgoci

Spring 2026

Three Flavors of Indistinguishability

Statistical Indistinguishability

The course opens by comparing two coins:

• Coin 1: $p = 1/2$

• Coin 2: $p = 1/2 + b$

Distinguishing Biased Coins

Let $X \sim \mathrm{Binomial}(n,p)$. Then: $$\mathbb{E}[X] = pn, \qquad \mathrm{Var}(X) = p(1-p)n.$$ By Chernoff bounds, $$\Pr[|X - \mathbb{E}[X]| \ge t\sigma] \le e^{-\Theta(t^2)}.$$

Insight: Statistical indistinguishability is governed by variance scaling as $\sqrt{n}$.

Differential Privacy and Adjacent Datasets

Two datasets $x, y$ are adjacent if they differ in exactly one individual’s record. Concretely: $x$ might be everyone in the room, and $y$ might be everyone in the room plus one additional person. Only that one record differs; everything else is identical.

Why adjacency?

The goal of differential privacy is to protect individuals: to ensure that no single person’s decision to contribute their data can meaningfully change what an observer learns. Defining privacy with respect to adjacent datasets captures this precisely.

Why randomized mechanisms?

Differential privacy necessarily involves randomized algorithms. For a given input, a randomized mechanism does not produce the same output every time — it produces a probability distribution over outputs. Privacy is then a statement about these distributions: the distributions on adjacent inputs must be nearly identical.

Interpretation.

Every possible transcript of an interaction with $M$ is essentially equally likely whether or not any given individual is present in the dataset. An observer who sees the output of $M$ cannot reliably infer whether a specific person’s data was included.

Statistical vs. computational protection.

DP is a statistical guarantee: it is indistinguishability in the face of unlimited computational power. Unlike cryptographic notions, DP does not rely on hardness assumptions. The protection comes from how many observations the adversary gets — running the mechanism more times leaks more — not from the adversary’s computational limitations. Even an adversary with infinite computing power who knows every other person’s data cannot determine whether a target individual participated.

Real-world motivation.

• US Census. The Census Bureau must release aggregate statistics about the population while protecting respondents’ individual records.

• Medical research. Studies on shared datasets (e.g., the Framingham Heart Study) require guarantees that individual patient data remains private even as the data is used for research by many groups over many years.

• Industry. Google applied DP to mobility data analysis in a Scandinavian country so that engineers could analyze aggregate trajectories without being exposed to individual movement histories — making the analysis both privacy-preserving and more comfortable for the analysts themselves.

Computational Indistinguishability

In cryptography, indistinguishability is restricted to polynomial-time adversaries. The key definitions below are from Barak’s lecture notes (§2.4).

The indistinguishability game.

An adversary Eve tries to tell $X$ from $Y$. A challenger flips a hidden bit $b\in\{0,1\}$, samples from $X$ if $b{=}0$ or $Y$ if $b{=}1$, and gives the sample to Eve. Eve outputs a guess $b'$. The scheme is secure if $$\Pr[\text{Eve wins}] = \Pr[b' = b] \;\le\; \tfrac{1}{2} + \tfrac{\varepsilon}{2},$$ equivalently, Eve’s advantage $|\Pr[b'{=}1\mid b{=}0] - \Pr[b'{=}1\mid b{=}1]| \le \varepsilon$.

Properties. Computational indistinguishability ($\approx$) satisfies:

• Symmetry: $X \approx Y \Rightarrow Y \approx X$.

• Transitivity: $X \approx Y$ and $Y \approx Z \Rightarrow X \approx Z$ (proved by a hybrid argument).

• Closure under efficient computation: if $X \approx Y$ and $f$ is poly-time, then $f(X) \approx f(Y)$.

Unlike DP, computational indistinguishability:

• quantifies over efficient algorithms only;

• relies on hardness assumptions (not information-theoretic).

Pseudorandom Generators: A Concrete Example

The canonical application of computational indistinguishability is the pseudorandom generator (PRG).

Setup.

A PRG $G : \{0,1\}^n \to \{0,1\}^{2n}$ takes an $n$-bit seed and deterministically produces a $2n$-bit output string. (The stretch factor of 2 is for concreteness; any polynomial stretch works.) The machinery of $G$ is completely deterministic — the only randomness is in the choice of the seed.

How many pseudorandom strings are there?

There are $2^n$ possible seeds, so there are at most $2^n$ possible outputs — a tiny fraction of all $2^{2n}$ strings of length $2n$. A truly random string of length $2n$ almost certainly falls outside the image of $G$, because $|\mathrm{Im}(G)| / 2^{2n} \le 2^n / 2^{2n} = 2^{-n}$.

The indistinguishability requirement.

An exponential-time distinguisher could enumerate all $2^n$ outputs of $G$, check membership, and distinguish pseudorandom from truly random strings easily. The requirement is therefore restricted to polynomial-time distinguishers:

PRGs are the building block for stream ciphers and are studied in depth in Chapter 14.

The Third Flavor: Outcome Indistinguishability (Preview)

The chapter title promises three flavors. The third arises in the context of prediction algorithms and algorithmic fairness.

The problem of evaluating prediction algorithms.

Prediction algorithms assign probabilities to events: the probability that it will rain tomorrow, that a patient’s tumor will metastasize, that a person will repay a loan. Evaluating such algorithms is fundamentally difficult because these are non-repeatable events — we cannot rewind the future, re-run it many times, and measure the frequency of outcomes. There is no universally agreed mathematical definition of the probability of a non-repeatable event.

Calibration: necessary but not sufficient.

One natural criterion is calibration (Dawid, 1982): a forecaster is calibrated if, among all instances on which it predicted probability $p$, the fraction of true outcomes is approximately $p$. For example, among all days on which the forecaster said “70% chance of rain,” it should have actually rained on approximately 70% of those days.

Calibration is clearly desirable. Alarmingly, however, it is achievable by a complete charlatan who knows nothing about the phenomenon being predicted — one can construct a perfectly calibrated forecaster that is entirely uninformative. This shows that calibration alone is not a meaningful guarantee of accuracy or fairness.

The outcome indistinguishability framework.

Inspired by Feynman’s account of how physics validates a new law — build an experiment to test whether the law’s computed consequences match reality, and if they don’t, the law is wrong regardless of its elegance — we want a richer notion of what it means for a model’s predictions to be valid.

The class of distinguishers $\mathcal{D}$ encodes what kinds of tests we care about. By varying $\mathcal{D}$, one recovers:

• simple calibration (distinguishers that only see the predicted probability and the outcome);

• group-conditional calibration (distinguishers that also see demographic attributes);

• complex fairness criteria (distinguishers with access to richer features).

This gives a hierarchy of fairness notions ordered by distinguisher power, and connects algorithmic fairness directly to the indistinguishability framework used throughout the course. The full theory is developed in Chapter 4.

Summary: three flavors.

Algorithmic Fairness

Representation and Bias

Algorithms never operate on individuals directly. Instead, each individual is mapped through a representation function $\rho : \mathcal{X} \to \mathcal{Z}$ that extracts a finite set of features. The algorithm sees only $\rho(x)$, not the full person $x$. This compression is a fundamental source of bias.

Choice of features matters.

Consider a cancer study. Two research groups each study whether a particular treatment causes metastasis. Group A examines positions $\{r_1,\ldots,r_k\}$ in a tumor’s DNA and finds a 30% metastasis rate among patients who look like you in those positions. Group B examines positions $\{b_1,\ldots,b_m\}$ and finds a 5% rate. What can we conclude about your prognosis? Nothing — because the two groups studied different projections of your tumor. Only a study examining both sets of features simultaneously would be informative. Whenever the representation matters this much, it is a vector for the introduction of bias.

Sources of Bias

Non-representative training data.

A classifier trained to minimize error on a distribution $\mathcal{D}$ only generalizes to that distribution. If a minority group constitutes a small fraction of $\mathcal{D}$, near-zero error overall can be achieved by performing arbitrarily badly on the minority while doing well on the majority. The algorithm has no incentive to be accurate on groups that barely affect aggregate loss.

Biased labels.

Labels themselves may encode historical discrimination. If the same behavior by a child of color is systematically coded as “defiant” while an identical behavior by a white child is coded as “spirited,” the training data absorbs this bias. The algorithm then learns to replicate it. Similarly, rearrest is used as a proxy for recidivism in criminal justice tools, but rearrest rates reflect policing intensity and systemic inequality, not solely individual behavior. People who commit crimes may not be rearrested; people who are arrested may not have committed a crime.

Differentially expressive features.

The same feature value can mean different things for different populations. The Allegheny County Child Protective Services screening tool (Virginia Eubanks, Automating Inequality, 2014) accessed Medicaid records to flag prior drug treatment. A poor family on Medicaid has a visible treatment history; a wealthy family that paid privately at a clinic has none. The feature “no drug treatment history” means different things depending on socioeconomic status. Other examples: income of $100,000/year has different implications for men and women given structural wage inequality; number of children is positively correlated with career success for men and negatively for women.

Principled criteria for feature selection.

The question of which features to include in a predictor is under-studied but critical. Several principled objections arise:

• Subjective assessment. Features that are subjectively coded (e.g., “kempt vs. unkempt” in early risk instruments) introduce the assessor’s bias directly into the model, while appearing to be objective data.

• Autonomy. Features outside an individual’s control — immutable characteristics like race or biological sex — make predictions that cannot be acted upon. They also raise serious concerns about accountability for outcomes.

• Private sphere. Marital status, family composition, and similar features may belong to a domain where prediction is simply inappropriate, regardless of predictive accuracy.

• Correlation vs. causation. A feature may be predictive today only because it correlates with a causal factor. If social norms shift (e.g., if men’s smoking rates converge with women’s), the feature loses its predictive value — and any policies built on it become wrong. Example: women’s greater longevity correlates with biological sex but is partly explained by proximal factors (risk-taking behavior, occupational stress, smoking rates) that are socially contingent.

• The “New York Times” test. A practical heuristic: if you would be embarrassed to explain in a news article that you used feature $X$ to make prediction $Y$, you should reconsider the feature. This does not replace formal analysis, but it is a useful sanity check on whether your modeling choices are defensible to a non-specialist audience.

Measurement and hardware bias.

Bias can be embedded in the hardware itself. Camera lenses are historically optimized for white skin tones; microphones and broadcast frequencies were calibrated for male vocal ranges, leading to the perception that women’s voices are “shrill” — a perception produced by the technology, not by the voices. These are not labeling errors; they are biases in the measurement apparatus.

Label inflation and denominator problems.

When labels reflect reporting rates rather than ground truth, populations that are surveilled more will appear to have higher rates of the labeled behavior. CPS receives more calls about families in dense urban neighborhoods (where neighbors can hear a crying baby) than about identical situations in rural areas. “Number of prior calls” is not “prior abuse” — it is a function of surveillance density, which correlates with poverty and race.

Group Fairness

Group fairness properties are statistical requirements imposed on a classifier’s behavior across demographic groups.

The Confusion Matrix

For a binary classifier with true label $Y \in \{0,1\}$ and predicted label $\hat{Y} \in \{0,1\}$, all outcomes fall into four cells:

Chouldechova’s Impossibility Theorem

Proof sketch.

There is a mathematical identity linking these four quantities for any group $G$: $$\mathrm{PPV}_G = \frac{p_G(1 - \mathrm{FNR}_G)}{p_G(1-\mathrm{FNR}_G) + (1-p_G)\mathrm{FPR}_G}.$$ This identity holds independently within each group. Requiring equal FPR and equal FNR across $S$ and $T$ pins two of the three varying quantities; the identity then forces $\mathrm{PPV}_S = \mathrm{PPV}_T$ if and only if $p_S = p_T$. If base rates differ, at least one of the three conditions must be violated.

Real-world instantiation: COMPAS.

In 2016, ProPublica (Julia Angwin) reported that Northpointe’s COMPAS recidivism risk tool exhibited higher false positive rates for Black defendants and higher false negative rates for white defendants. Northpointe responded that their tool was calibrated — equal positive predictive value across racial groups. Both claims were correct. Chouldechova’s theorem explains why: differential base rates in rearrest (themselves a product of differential policing) make it mathematically impossible to equalize all three criteria simultaneously.

Statistical Parity and Its Limits

Statistical parity is meaningful in the breach: a large violation is a warning sign worth investigating. But it is not a solution concept. A discriminatory actor can satisfy statistical parity while circumventing its intent: if a steakhouse owner wishes to exclude group $G$ and is required to show equal advertising rates across $G$ and $\bar G$, they can target the ads at the vegetarians within $G$ — people who will not come regardless. The statistical parity requirement is met; the discriminatory intent is achieved.

Scoring Functions: Analogous Impossibility

For scoring functions $s : \mathcal{X} \to [0,1]$ (rather than binary classifiers):

Proof sketch.

Calibration implies that the total score assigned to group $G_t$ equals the number of positive individuals in $G_t$: $$\sum_{i \in G_t} s_i = \mu_t \qquad (t = 1, 2),$$ where $\mu_t$ is the number of positives in group $t$. The balance conditions fix $X$ (average score for negatives) and $Y$ (average score for positives) to be group-independent. Expanding the sum: $$\mu_t = Y \cdot \mu_t + X \cdot (n_t - \mu_t),$$ which simplifies to $\mu_t = n_t X + \mu_t(Y - X)$ for groups of equal size $n_t = n$. This gives a pair of lines (one per group) in the $(X, Y)$ plane; they coincide only when base rates $\mu_1/n = \mu_2/n$ are equal. Otherwise, the lines intersect only at $X=0, Y=1$ (perfect prediction).

Takeaway.

Group fairness desiderata are not merely in political tension — they are algebraically incompatible for imperfect classifiers when base rates differ.

Individual Fairness

This is a Lipschitz constraint over distributions.

Fairness Linear Program

The individually fair classification problem can be cast as a linear program: $$\min_{\{\mu_u\}_{u \in \mathcal{U}}} \;\mathbb{E}_{u,o}[L(u,o)] \quad \text{subject to} \quad \|\mu_u - \mu_v\| \le d(u,v) \quad \forall\, u,v \in \mathcal{U}.$$ Fairness is a hard constraint; utility is the soft objective. Linear programs are solvable in polynomial time.

Limitations.

Three practical obstacles limit this approach:

1. Scale. The universe $\mathcal{U}$ may contain billions of individuals. A polynomial running time in $|\mathcal{U}|$ is infeasible in practice (e.g., $|\mathcal{U}|^2$ constraints is already a trillion for a billion-person universe). One needs something closer to linear time.

2. Generalization. The LP is built on the individuals observed during training. It provides no fairness guarantee for individuals outside the training set.

3. Metric access. The LP requires the task metric $d$ as input. Where does $d$ come from? This is the metric-learning problem, addressed in Chapter [chap:metric].

PAC learning (probably approximately correct learning) offers a partial remedy to the first two problems by working on a small sample rather than the full universe — producing a classifier that is likely to be approximately fair on the population.

Task-Competitive Composition

Motivation.

Consider an online advertising setting where multiple advertisers compete for each user’s attention in a real-time auction. When you visit a news website, an instantaneous auction determines which ad you see. Higher bidders displace lower bidders. Can fairness be guaranteed across this system?

A concrete example.

A grocery delivery service bids $1 for the attention of expectant parents (high lifetime value; subscription retention is strong). A tech company bids $0.50 for qualified undergraduate candidates. Both advertisers design their classifiers to be individually fair for their own task — the grocery service advertises equally to similarly-situated expectant households; the tech company advertises equally to similarly-qualified candidates.

The grocery service outbids the tech company whenever both want the same user. The effective result: the tech company can only reach users the grocery service passed on. Expectant parents — disproportionately on parental leave or career transitions, disproportionately female — are systematically excluded from tech job ads, not by any intentional discrimination, but by the financial dynamics of the auction. Neither advertiser violated its own fairness condition.

Historical instantiation. A 2010 Wall Street Journal investigation reported that a major ad network categorized users into demographic bins with names like “White Picket Fence” and “Double Income, No Kids.” Credit card companies using this network were accused of steering minority users toward credit products with less favorable terms — a serious concern given federal anti-discrimination law in credit. The steering emerged from the composition of individually-designed targeting strategies, not from any single actor’s misconduct.

Formal setup.

A randomized classifier is a map $C : \mathcal{U} \to \Delta(\mathcal{O})$ assigning each individual a distribution over outcomes. For binary outcomes $\mathcal{O} = \{0,1\}$, define $p_u := \Pr[C(u)=1]$. Individual (metric) fairness requires $\|\mu_u - \mu_v\| \le d(u,v)$; for binary outcomes this becomes $|p_u - p_v| \le d(u,v)$.

Naive task-competitive composition.

Consider tasks $T$ (grocery) and $T'$ (tech), with task-specific metrics $d$ and $d'$ and individually fair classifiers $C$ and $C'$ respectively. Ties go to $T$.

• User $u$ receives the $T'$ ad only if $T$ did not bid on them.

• $\Pr[u \text{ receives } T'] = (1 - p_u)\,p_u'$.

The difference in $T'$-exposure between two individuals $u, v$: $$(1-p_u)p_u' - (1-p_v)p_v'.$$

Key observation. Even if $p$ is Lipschitz with respect to $d$ and $p'$ is Lipschitz with respect to $d'$, the product $(1-p)p'$ need not be Lipschitz under either metric. The multiplicative interaction introduced by outbidding breaks both fairness conditions.

Proof of violation.

Choose $u, v$ with $0 < p_u < p_v$ (task $T$ favors $v$) and $p_u' \ge p_v' > 0$ (task $T'$ favors $u$), with $d'(u,v)$ maximized. The gap in $T'$-exposure is: $$(1-p_u)p_u' - (1-p_v)p_v' \;=\; \underbrace{d'(u,v)}_{\text{allowed gap}} + \underbrace{(p_v - p_u)p_v'}_{\text{violation term} > 0}.$$ Setting $\alpha = p_v / p_u$ and choosing probabilities so that $\alpha \ge p_u' / p_v'$ (achievable because $\alpha$ can be pushed to exceed this ratio without violating $C'$’s fairness), the violation term is strictly positive. The system as a whole violates individual fairness for task $T'$, even though each classifier is individually fair in isolation.

Implication: coordination is necessary.

Fairness of the whole system does not follow automatically from fairness of its parts. An advertising network that wants to guarantee multi-task individual fairness must actively coordinate across advertisers — it is insufficient for each advertiser to independently satisfy its own fairness criterion. This is not merely a theoretical concern: when the structure of a market (auctions, outbidding, priority rules) causes tasks to interact, the platform bears responsibility for the emergent aggregate behavior.

The Denominator Problem in Auditing

Auditing a classifier for fairness requires a benchmark: a reference quantity against which to compare observed rates. The choice of benchmark determines the conclusion.

Population-based benchmark.

Compare the stop rate for group $S$ against the stop rate for group $T$, using total population as the denominator: $$\frac{\text{stops in }S}{|S|} \quad\text{vs.}\quad \frac{\text{stops in }T}{|T|}.$$ In hypothetical data (Neil and Winship, Annals of Criminology): $S$ has 15,000 criminals out of 100,000; $T$ has 10,000 out of 100,000. If 10% of $S$ are stopped vs. 5% of $T$, the population benchmark concludes a 2:1 disparity — strong evidence of discrimination against $S$.

Usage-based benchmark.

Now suppose every person in a public space is stopped independently with probability $1/4$, uniformly, with no consideration of race. Approximately 25% of $S$ and 25% of $T$ in the space are stopped. This is by construction non-discriminatory. Yet if $S$ uses the space at twice the rate of $T$ (for socioeconomic or geographic reasons), the population-based ratio of stops will be 2:1, exactly matching the earlier “evidence of discrimination” — even though the stopping rule is blind to race.

Implications.

When evaluating claims based on benchmark tests:

• Is the denominator justified by the mechanism being studied?

• Do stop rates vary by time of day, location, or type of crime in ways that interact with demography?

• Are the police targeting specific behaviors or areas, and does that targeting confound the comparison?

Different defensible answers produce different conclusions from the same data. This does not mean fairness auditing is impossible, but it means conclusions require explicit assumptions that should be stated and scrutinized.

Structural limits: a summary.

Taken together, the results of this chapter suggest that group fairness is not a well-posed solution concept:

• Natural desiderata (FPR, FNR, PPV) are mutually exclusive when base rates differ.

• Statistical parity is gameable by a sophisticated bad actor.

• Auditing via benchmarks is highly sensitive to unstated denominator assumptions.

• None of the above is resolved by introducing a human into the decision loop — a human decision-maker is still an algorithm, just one with flesh rather than silicon.

The appropriate response to a group fairness failure is investigation, not automatic remediation. The mathematical impossibility results explain the failure; they do not prescribe a solution.

Paper Readings

Chouldechova (2017) — Fair Prediction with Disparate Impact.

When base rates differ across demographic groups, no classifier can simultaneously satisfy calibration within each group, equal false positive rates, and equal false negative rates. The argument is purely algebraic: once calibration fixes the conditional expectations, the error rates are fully determined by the base rates, leaving no freedom to equalize them. This result is the mathematical backbone of the COMPAS controversy and demonstrates that apparent fairness trade-offs can be structural impossibilities rather than design failures.

Dwork, Hardt, Pitassi, Reingold, Zemel (2012) — Fairness Through Awareness.

Introduces individual fairness as a Lipschitz condition: a randomized classifier is fair if similar individuals (under a task-specific metric $d$) receive outcome distributions within $D(M(u), M(v)) \leq d(u,v)$ of each other. The fairness-constrained classification problem can be expressed as a linear program, and the central open question — where the metric comes from — motivates Chapter 3. This paper established the individual-vs.-group distinction that now structures most of the algorithmic fairness literature.

Learning the Metric: Human Arbiter

Individual Fairness: Treat Similar People Similarly

The most intuitive articulation of fairness is also one of the hardest to formalize: similar individuals should be treated similarly. This is the principle of individual fairness, introduced by Dwork, Hardt, Pitassi, Reingold, and Zemel (2012) as a formal counterpart to informal notions of non-discrimination.

The central challenge: “similar” is not a property of individuals in isolation — it is task-specific and context-dependent. Two candidates might be similar for the purpose of hiring engineers but dissimilar for the purpose of assessing surgical risk. There is no universal similarity function; the metric must be chosen by someone who understands the task.

Why a metric?

The Lipschitz condition requires $d$ to be a true metric (symmetric, satisfies triangle inequality, $d(u,u)=0$). The triangle inequality is not just a technical convenience: it prevents the situation where $u$ and $w$ are each deemed “similar” to $v$ but treated very differently.

The metric $D$ on outcomes.

A natural choice for $D$ is total variation distance between the outcome distributions. If outcomes are binary (e.g., loan approved/denied), total variation between two Bernoulli distributions simplifies to $|p_u - p_v|$ — the absolute difference in approval probabilities.

The Metric Problem

Individual fairness does not say which metric $d$ to use. This is intentional: the choice of $d$ is a normative decision, not a mathematical one. The question “are these two people similar for this task?” is a policy question, not a data question.

Why the metric cannot be learned from the data.

A natural thought: learn $d$ from historical outcomes. If the historical data comes from a biased process (discriminatory hiring, unequal access to credit), then distances learned from those outcomes will encode the bias. Using biased historical data to define “similarity” and then requiring the algorithm to respect that similarity perpetuates the original discrimination under the guise of mathematical fairness.

The metric must be an external normative input that reflects what we believe people ought to be judged on — not what they have historically been judged on.

Who specifies the metric?

Several approaches have been proposed:

1. Domain experts. A hiring committee, a medical board, or a panel of legal experts specifies which features are task-relevant and how differences in those features should be weighted.

2. Regulatory requirements. Anti-discrimination law may mandate that certain features (race, sex, religion) be ignored, implicitly defining a metric that is insensitive to those coordinates.

3. Human arbiter / oracle. A designated human (or panel) answers queries about specific pairs or triplets of individuals. This externalizes the normative question: the math defers to human judgment.

The Human Arbiter Model

The human arbiter approach treats the task-specific metric $d$ as accessible only through a human oracle that can answer comparison queries. We do not assume the oracle reveals exact distances; it only answers ordinal questions.

Why triplets?

Exact distances are hard for humans to provide: asking “how similar are these two candidates on a scale of 0 to 1?” yields inconsistent, poorly calibrated answers. Comparative judgments — “which of these two candidates is more similar to a third?” — are more reliable and cognitively natural. Triplet queries have been validated empirically as a basis for metric learning from human feedback.

Learning an Ordering via Triplet Queries

From comparisons to orderings.

Fix a representative individual $r \in \mathcal{X}$. The triplet oracle can answer queries of the form “which of $u, v$ is closer to $r$?” This is exactly the comparison oracle needed to run any comparison-based sorting algorithm.

Proof.

MergeSort makes $\Theta(n \log n)$ comparisons. Each comparison is one triplet query. The sort returns individuals in non-decreasing order of $d(r, \cdot)$, which is a valid total ordering because $d(r, \cdot)$ is a real-valued function.

From an ordering to distances.

A total ordering gives us the ranks $\sigma(u)$ for each $u$, but not the actual distances $d(r, u)$. To estimate $d(r, u)$, we use the gaps between adjacent elements in the sorted order. This requires stronger oracle access (e.g., asking for approximate ratios of distances, not just ordinal comparisons), and recovery is only approximate.

Approximate Metric Recovery: $\alpha$-Submetrics

Exact metric recovery from ordinal queries is information-theoretically impossible in general: many metrics are consistent with the same set of triplet answers. We therefore aim for approximate recovery.

Representative-based distance.

Fix a representative $r$. Define: $$d_r(u, v) \;=\; \bigl|d(r, u) - d(r, v)\bigr|.$$ By the reverse triangle inequality, $d_r(u,v) \leq d(u,v)$ for all $u, v$ (it is a 1-Lipschitz projection of $d$). It is a pseudometric: it satisfies all metric axioms except it may assign zero distance to distinct points (if $d(r,u) = d(r,v)$ but $u \neq v$).

Using multiple representatives.

Choose a set of representatives $R = \{r_1, \ldots, r_k\}$. Define: $$\hat{d}(u, v) \;=\; \max_{r \in R} d_r(u, v) \;=\; \max_{r \in R} \bigl|d(r,u) - d(r,v)\bigr|.$$ This is always a lower bound: $\hat{d}(u,v) \leq d(u,v)$. If $R$ is chosen such that for every pair $(u,v)$ there exists $r \in R$ with $d(r,u)$ and $d(r,v)$ differing by close to $d(u,v)$, then $\hat{d}$ approximates $d$ well.

For doubling-dimension metric spaces (where every ball of radius $2\rho$ can be covered by a bounded number of balls of radius $\rho$), a random sample of size $O(\log n)$ is sufficient for a good approximation with high probability.

The Mahalanobis Distance: A Canonical Parametric Form

When individuals are represented as vectors in $\mathbb{R}^p$, the most expressive linear metric is the Mahalanobis distance:

Special cases: $A = I$ gives Euclidean distance; $A = \Sigma^{-1}$ (inverse covariance) gives the classical Mahalanobis distance that whitens the feature space. The matrix $A$ encodes which features matter and how much: a large diagonal entry for feature $j$ means differences in $j$ are penalized heavily.

Metric learning as semidefinite programming.

Given a set of “must-link” pairs $\mathcal{S}$ (similar individuals) and “cannot-link” pairs $\mathcal{D}$ (dissimilar individuals), one can find the best-fit $A$ by solving: $$\begin{align*} \min_{A \succeq 0} \quad & \sum_{(u,v) \in \mathcal{S}} d_A(u,v)^2 \\ \text{subject to} \quad & \sum_{(u,v) \in \mathcal{D}} d_A(u,v)^2 \geq 1. \end{align*}$$ This is a semidefinite program (SDP): the constraint $A \succeq 0$ (positive semi-definiteness) is convex, so the problem can be solved in polynomial time. The constraint set $\mathcal{S}$ and $\mathcal{D}$ can be populated from human arbiter responses to pairwise queries.

Historical context.

The Mahalanobis distance was introduced by P.C. Mahalanobis in 1936, originally to measure anthropometric distances between population groups in British India — arguing that intra-caste variation exceeds inter-caste variation, and that geographic proximity is a more principled basis for social classification than caste hierarchy. The original application was explicitly political; the tool it introduced is genuinely powerful and now ubiquitous in statistics and machine learning. This history is a reminder that mathematical tools are not neutral: they are invented to answer specific questions, those questions carry normative assumptions, and the tools can be repurposed in both better and worse directions.

Limitations and Critiques

Who is the arbiter?

The human arbiter model defers the normative question to a human — but does not resolve it. If the designated arbiter is not representative (e.g., drawn from a homogeneous population), the metric will reflect their perspective, not the affected community’s. Diversity of the arbiter pool matters as much as the mathematical formalism.

Whose similarity?

The metric is task-specific: similar for hiring engineers is not the same as similar for bail decisions. In practice, the same features (education, neighborhood) are used across many tasks, creating de facto cross-task conflation of similarity.

Tension with group fairness.

Individual fairness and group fairness (e.g., equalized odds, demographic parity) are not equivalent, and can conflict. A metric that treats individuals as similar when they have the same qualifications may still produce racially disparate outcomes if qualifications are unequally distributed across groups as a result of historical inequality. Individual fairness is silent on this; it only asks that the algorithm respect the metric, not that the metric itself be equitable.

The bootstrapping problem.

Validating a fairness metric requires knowing what the fair outcomes are — but knowing fair outcomes is equivalent to having the metric. There is no ground truth to check against: the arbiter’s responses are constitutive, not descriptive, of the fairness standard.

Paper Readings

Dwork, Hardt, Pitassi, Reingold, Zemel (2012) — Fairness Through Awareness.

The foundational paper for this chapter: proposes the human arbiter model in which a designated oracle answers comparison queries about individual similarity, externalizing the normative question of who counts as similar for a given task. The paper proves that the resulting metric can be used to formulate fair classification as a linear program, and explicitly frames the open problem — how to elicit or learn the metric in practice — that the rest of this chapter addresses.

Mukherjee, Yao, Gaboardi, Learned-Miller, Agarwal (2020) — Two Simple Ways to Learn Individual Fairness Metrics from Data.

Shows that a Mahalanobis distance encoding task-specific similarity can be learned from human-provided pairwise labels (similar/dissimilar) or triplet comparisons without requiring full expert specification. Both approaches reduce to convex optimization: the pairwise-constraint version is a semidefinite program; the triplet version uses gradient descent. The resulting metric is interpretable as a feature reweighting, but the quality of the metric depends entirely on the raters’ judgments — the method systematizes elicitation without validating whether the elicited standard is itself equitable.

Outcome Indistinguishability & the Multi-$X$ Framework

Motivation: the meaning of a single probability

Richard Feynman famously asked: what does it mean to say there is a 12% chance of rain tomorrow? For a repeatable experiment we can check the prediction by running many trials; but tomorrow is a unique event. The same question applies to recidivism prediction, loan approval, or medical diagnosis: the ground truth $\pi^\star_i$ for individual $i$ is never directly observable.

The Outcome Indistinguishability framework sidesteps this epistemological problem by asking a behavioral question: can a downstream observer—using whatever statistical tests they care about—distinguish behavior under the model from behavior under the true distribution? If not, the model is, in every practical sense, as good as the truth.

This mirrors the scientific method: propose a model, derive observable consequences, and test whether those consequences match reality. Passing the tests does not prove the model is universally correct; it only says the model is good for the uses captured by the tests in $\mathcal{C}$.

Connection to computational indistinguishability.

The OI framework was inspired in part by the polynomial-time indistinguishability definitions from cryptography (Chapter 14). Both use the same template: fix a class of efficient tests; require that two distributions (real-world outcomes vs. model outcomes, or truly random bits vs. pseudorandom bits) cannot be told apart by any test in that class. OI is the fairness-flavored instantiation of the same core idea.

Formal setup

• Universe of individuals/features: $\mathcal{X}$.

• Individuals are drawn from a population distribution: $$I \sim \mathcal{D}_{\mathcal{X}}.$$

• Ground-truth per-individual success probability: $$p_i^\star \in [0,1].$$ The real-life outcome is: $$Y_i^\star \sim \mathrm{Bernoulli}(p_i^\star).$$

• Model / predictor: $$\tilde p_i \in [0,1].$$ The model-generated outcome is: $$\tilde Y_i \sim \mathrm{Bernoulli}(\tilde p_i).$$

• Distinguishers: $$c:(i,\tilde p_i,y)\mapsto [0,1].$$ The distinguisher receives information about an individual, possibly the model’s prediction, and an outcome, and outputs a bounded real value.

The goal is that $c$ should behave nearly the same whether the outcome is drawn from real life or from the model.

Distinguisher hierarchy

Different real-world observers have different amounts of information. We organize them into a four-level hierarchy of increasing power:

1. No-access distinguisher: sees only the raw input $i$ and the binary outcome $y$; receives no prediction $\tilde p_i$.

2. Sample-access distinguisher: sees $(i, \tilde p_i, y)$ but only for finitely many sampled individuals. Cannot query the model on arbitrary inputs.

3. Oracle-access distinguisher: can query the model on any $i\in\mathcal{X}$, receiving $\tilde p_i$, then observe the outcome $y$.

4. Full-access distinguisher: knows the model $\tilde p$ in full; can compute $\tilde p_i$ for every $i$ without querying.

Demanding OI against a stronger class $\mathcal{C}$ is a strictly stronger requirement. In the algorithm we will work with real-valued distinguishers: $c : \mathcal{X} \times [0,1] \times \{0,1\} \to [0,1]$, mapping (individual, prediction, outcome) to a score in $[0,1]$. The distinguishing gap becomes $$\Delta_c = \mathbb{E}_i\!\bigl[\mathbb{E}[c(i,\tilde p_i, \tilde Y_i)] - \mathbb{E}[c(i,\tilde p_i, Y_i^\star)]\bigr] = \mathbb{E}_i\!\bigl[(\pi^\star_i - \tilde p_i)\,\delta_c(i)\bigr],$$ where $\delta_c(i) := c(i,\tilde p_i, 1) - c(i,\tilde p_i, 0)$ is the per-individual contrast (how much $c$ changes when the outcome flips).

Real world versus model world

Fix a distinguisher $c\in\mathcal{C}$.

Define the expected behavior of $c$ in the real world: $$A_c = \mathbb{E}_{I\sim\mathcal{D}_{\mathcal X}} \left[ \mathbb{E}\left[ c(I,\tilde p_I,Y_I^\star)\mid I \right] \right].$$

Define the expected behavior of $c$ in the model world: $$B_c = \mathbb{E}_{I\sim\mathcal{D}_{\mathcal X}} \left[ \mathbb{E}\left[ c(I,\tilde p_I,\tilde Y_I)\mid I \right] \right].$$

The distinguishing gap is: $$\Delta_c = A_c-B_c.$$

The model is $\varepsilon$-outcome-indistinguishable with respect to $\mathcal{C}$ if $$|\Delta_c|\le \varepsilon \qquad \forall c\in\mathcal{C}.$$

Decomposition of the distinguishing gap

Interpretation. The gap is an inner product between the error vector $(\pi^\star_i - \tilde p_i)$ and the sensitivity vector $\delta_c(i)$. A distinguisher can detect the model’s flaws exactly when its sensitivity is aligned with those flaws.

Algorithm: iterative $\tilde p$-nudging

Start with the trivial predictor: $$\tilde p^{(0)}(i)=\frac{1}{2} \qquad \forall i.$$

Repeat:

1. If $|\Delta_c|\le \varepsilon$ for every $c\in\mathcal{C}$, stop.

2. Otherwise, choose a distinguisher $c$ with $|\Delta_c|>\varepsilon$.

3. Update: $$\tilde p^{(t+1)}(i) = \Pi_{[0,1]} \left( \tilde p^{(t)}(i) + \frac{\Delta_c}{2}\delta_c(i) \right).$$

Here $\Pi_{[0,1]}$ is projection back into the interval $[0,1]$.

Circuit interpretation

The algorithm can be viewed as gradually building a predictor circuit.

• Initially, the circuit outputs $1/2$ for every individual.

• Each failed distinguisher contributes one additional correction layer.

• After $T$ updates, the predictor is the result of composing these $T$ nudges.

The computationally hard part is often finding a distinguisher $c\in\mathcal{C}$ with large $|\Delta_c|$. This is related to agnostic learning. But once such a distinguisher is found, the update itself is simple.

Convergence: potential function argument

Define the mean-squared error potential $$\Phi(\tilde p) \;=\; \mathbb{E}_I\!\bigl[(\pi^\star_I - \tilde p(I))^2\bigr] \;\in [0,1].$$

Multi-$X$: accuracy, calibration, and validity

Multi-accuracy is a special case of OI: it corresponds to taking $\mathcal{C}$ to be the class of indicator-function distinguishers $c(i,\tilde p_i, y) = \mathbf{1}[i\in S]\cdot y$. The iterative algorithm above therefore produces a multi-accurate predictor in $O(1/\varepsilon^2)$ rounds whenever $\mathcal{S}$ is finite (or efficiently enumerable).

Connection to group fairness.

Multi-accuracy is stronger than requiring average calibration per group: it bounds the signed error, preventing the model from simultaneously over-predicting for one demographic subgroup while under-predicting for another. By choosing $\mathcal{S}$ to contain all protected groups and their pairwise (and higher-order) intersections, we approach intersectional fairness.

Multi-calibration.

Strengthening multi-accuracy to require calibration within each score bucket of each group yields multi-calibration (Hébert-Johnson, Kim, Reingold, Rothblum, 2018): $$\forall S\in\mathcal{S},\;\forall v\in[0,1]: \quad \mathbb{E}\!\bigl[\pi^\star_I \mid I\in S,\;\tilde p_I = v\bigr] \;\approx\; v.$$ The same nudge-and-project algorithm achieves this; it is a strictly stronger guarantee than multi-accuracy.

Limitations

1. Small groups. When a group $S\in\mathcal{S}$ is small, the empirical estimate of $\mathbb{E}_{I\in S}[\pi^\star_I - \tilde p_I]$ has high variance. Meaningful multi-accuracy guarantees require sample sizes that grow with $|\mathcal{S}|$ and shrink with group size.

2. Intersectionality at scale. Requiring accuracy on all intersections $S_1\cap S_2\cap\cdots$ causes $|\mathcal{S}|$ to grow exponentially in the number of protected attributes, making the $O(1/\varepsilon^2)$ bound vacuous without additional structure (e.g., computationally efficient distinguisher classes).

3. Gameable accuracy definitions. A model can achieve multi-accuracy while still making badly miscalibrated predictions within fine-grained subgroups, motivating the stronger multi-calibration guarantee.

Connection to fairness

Multi-accuracy protects against systematic group-level prediction errors. If a predictor systematically overpredicts loan repayment for one group, multi-accuracy pushes those predictions down. If it systematically underpredicts for another group, multi-accuracy pushes those predictions up.

By choosing $\mathcal{S}$ to include protected groups and intersections of protected groups, one obtains a form of intersectional fairness.

However, small groups are difficult:

• If $S$ is tiny, the training sample may contain too few examples from $S$.

• Then the algorithm may not be able to detect or correct systematic error on $S$.

Thus Multi-$X$ helps with intersectionality only for groups explicitly included in $\mathcal{S}$ and sufficiently represented in the data.

Paper Readings

Hébert-Johnson, Kim, Reingold, Rothblum (2018) — Multicalibration: Calibration for the Computationally Identifiable Masses.

Introduces multicalibration: the requirement that a predictor be calibrated not just globally but on every subgroup that a polynomial-time algorithm can identify. The main result is an efficient boosting-style algorithm that iterates through subgroups, applies a small nudge wherever calibration fails, and halts after $O(1/\alpha^2)$ rounds — the same structure as the OI algorithm in this chapter. Multicalibration implies multi-accuracy and is implied by outcome indistinguishability against oracle-access distinguishers, making it a key waypoint in the OI hierarchy.

Dwork, Kim, Reingold, Rothblum, Yona (2021) — Outcome Indistinguishability.

Formally defines the OI framework: a predictor is outcome indistinguishable with respect to a class $\mathcal{C}$ of distinguishers if no $c \in \mathcal{C}$ can tell real-world outcomes from model-generated ones. The paper proves the equivalences between OI, multi-accuracy, and multicalibration at each level of the distinguisher hierarchy, and shows that the nudge-and-project algorithm achieves $\varepsilon$-OI in $O(1/\varepsilon^2)$ rounds. It is the primary reference for the material in this chapter.

Trevisan, Tulsiani, Vadhan (2009) — Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.

Proves that any distribution with high Shannon entropy can be efficiently simulated by a distribution that is computationally indistinguishable from it, by iteratively correcting the simulator against the best-fitting distinguisher from a fixed class. The boosting-style argument and the potential function that bounds the number of correction steps are structurally identical to those in the OI convergence proof, providing the complexity-theoretic underpinning for the algorithm analyzed in this chapter.

Differential Privacy and Reconstruction

Fundamental Law of Information Recovery

Specifically: error $o(n)$ implies blatant non-privacy; even $o(\sqrt{n})$ error fails under many random queries.

Database Reconstruction Model

Let the database be $d \in \{0,1\}^n$. A query corresponds to a subset $S \subseteq [n]$: $\text{True answer: } \sum_{i \in S} d_i$, mechanism response: $R(S) = \sum_{i \in S} d_i + \text{noise.}$ We assume a uniform accuracy guarantee: $\forall S \subseteq [n],\ \left| R(S) - \sum_{i \in S} d_i \right| \le E.$

Blatant Non-Privacy

Reconstruction from Accurate Answers

Proof Sketch.

Both $d$ and any consistent $c$ satisfy $|R(S) - \sum_S d_i| \le E$ and $|R(S) - \sum_S c_i| \le E$. By triangle inequality, $|\sum_S d_i - \sum_S c_i| \le 2E$ for all $S$. Setting $S_1 = \{i:d_i=1\}$ and $S_0=\{i:d_i=0\}$: $$H(c,d)=\left|\sum_{i\in S_0}d_i - \sum_{i\in S_0}c_i\right| +\left|\sum_{i\in S_1}d_i-\sum_{i\in S_1}c_i\right|\le 2E+2E=4E.$$ If $E=o(n)$ then $H(c,d)=o(n)$: almost the entire database is reconstructable.

Reconstruction from Linearly Many Random Queries

Take $q \in \{-1,1\}^n$ drawn uniformly at random; true answer $q\cdot d$; noise $|\text{noise}| \le \frac{\sqrt{\alpha n}}{3}.$

Signal from Distant Databases

If $H(c,d) \ge \alpha n$, then $q \cdot (d-c)$ is a sum of $\alpha n$ independent $\pm 1$ variables. By anti-concentration, $\Pr_q[|q\cdot(d-c)|\ge\sqrt{\alpha n}]\ge \kappa$ for some constant $\kappa>0$.

After $\beta n$ independent queries, by union bound: $$\Pr[\exists \text{ distant } c \text{ that survives}] \le 2^{\alpha n} \cdot p^{\beta n}, \quad p = 1-\kappa.$$ Choosing $\beta > \frac{\alpha + \gamma}{\log_2(1/p)}$ drives this to $2^{-\gamma n}$, eliminating all distant databases with high probability.

Concentration vs. Anti-Concentration

Let $S = \sum_{i=1}^k X_i$, $X_i \in \{-1,1\}$ i.i.d.

Concentration (Chernoff): $\Pr[|S|\ge t]\le 2e^{-t^2/(2k)}$. Most mass lies near 0.

Anti-Concentration: $\Pr[|S|\ge \sqrt{k}]\ge \kappa > 0$ (from CLT: $S/\sqrt{k}\approx \mathcal{N}(0,1)$).

Connection to Differential Privacy

Noise must scale at least $\Omega(\sqrt{n})$ to prevent reconstruction. Differential privacy $\Pr[M(x)\in S]\le e^\varepsilon \Pr[M(y)\in S]$ prevents catastrophic reconstruction even under adaptive querying.

Paper Readings

Dinur and Nissim (2003) — Revealing Information While Preserving Privacy.

Proves that any mechanism answering all subset-sum queries on an $n$-bit database with error $o(\sqrt{n})$ allows efficient reconstruction of almost the entire database. The attack issues $O(n)$ random queries, forming an overdetermined linear system whose solution approximates the private bits; the $\sqrt{n}$ error threshold is tight. This result is the formal justification for differential privacy: it establishes that useful statistical answers and full individual-level privacy cannot coexist, so any practically private mechanism must inject noise of order at least $\sqrt{n}$.

Laplace and Exponential Mechanisms

Global Sensitivity

Sensitivity measures how much one individual’s data can change the output.

Laplace Mechanism

Proof idea. For adjacent $x,y$, the ratio of output densities is bounded: $$\frac{\mathrm{pdf}_{M(x)}(t)}{\mathrm{pdf}_{M(y)}(t)} \le e^\varepsilon.$$

Accuracy for a Single Query

Let $Y \sim \mathrm{Lap}\!\left(\frac{\Delta f}{\varepsilon}\right)$. We want $\Pr[|Y| \le \alpha] \ge 1-\beta$. Using the Laplace tail bound: $$\Pr[|Y| \ge t \cdot b] = e^{-t}, \quad b=\frac{\Delta f}{\varepsilon}.$$ Set $t = \ln(1/\beta)$, giving: $$\alpha = \frac{\Delta f}{\varepsilon}\ln(1/\beta).$$

High-Dimensional Laplace Mechanism

For vector-valued queries $f:\mathcal{X}^n \to \mathbb{R}^k$, define the $\ell_1$ sensitivity: $$\Delta_1 f = \max_{\text{adj }x,y} \|f(x)-f(y)\|_1.$$ For instance, if we ask simultaneously how many people are over six feet tall and how many prefer vanilla to strawberry, one person can change both counts by 1, giving $\ell_1$ sensitivity 2. In general, for $k$ arbitrary counting queries, one person can affect all $k$ counts, so $\Delta_1 f = k$ in the worst case.

The mechanism draws $k$ independent noise terms and adds one to each coordinate: $$M(x) = f(x) + (Y_1,\dots,Y_k), \qquad Y_i \overset{\mathrm{i.i.d.}}{\sim} \mathrm{Lap}\!\left(\frac{\Delta_1 f}{\varepsilon}\right).$$ The privacy proof is identical to the one-dimensional case, applied coordinate by coordinate.

Accuracy for $k$ Queries

We want $\Pr\!\left[\max_i |Y_i| \le \alpha\right] \ge 1-\beta$. By a union bound: $$\Pr[\exists\, i: |Y_i|\ge \alpha] \le k \cdot \Pr[|Y|\ge \alpha].$$ Setting $\Pr[|Y|\ge\alpha] \le \beta/k$ and solving via the Laplace tail: $$\exp\!\left(-\frac{\alpha\varepsilon}{\Delta_1 f}\right) \le \frac{\beta}{k} \quad\Longrightarrow\quad \alpha = \frac{\Delta_1 f}{\varepsilon}\ln\!\left(\frac{k}{\beta}\right).$$

Histogram Queries: Sensitivity Is Always 1

A histogram query partitions the population into disjoint cells and counts how many individuals fall into each cell. Examples include:

• Country of birth (each person is born in exactly one country).

• City of residence (to a first approximation, each person lives in one city).

• Any attribute that takes a unique value per individual.

This is one of the foremost practical advantages of DP for administrative statistics. Most government statistics — population counts by region, age, income bracket, and so on — are histograms or contingency tables (multi-dimensional histograms). All have sensitivity 1.

Choosing the right algorithm.

For a given $\varepsilon$, there are often many $\varepsilon$-DP algorithms for the same task with different accuracy. Exploiting histogram structure yields dramatically better accuracy at no privacy cost. The comparison between algorithms is always on utility, never on privacy.

Privacy Budget Interpretation

Differential privacy can be viewed as having a total budget $\varepsilon$.

• Answer one query: use full $\varepsilon$.

• Answer many queries: split the budget.

Naively splitting gives $\varepsilon/k$ per query, forcing noise $\propto k/\varepsilon$.

Differential Privacy vs. Cryptographic Privacy

The cryptographic setting.

A sender transmits an encrypted message. The legitimate receiver learns the plaintext; the eavesdropper learns nothing useful. These two parties are different. Modern cryptography — under standard hardness assumptions — achieves this.

The DP setting.

The data analyst is both the legitimate user and the potential adversary. We cannot simultaneously let the analyst learn something useful and prevent them from learning anything.

An additional subtlety: even a well-intentioned analyst who publishes results enables a later party to combine them with other analyses from the same dataset. Privacy loss accumulates over time across all users, which is why composition theorems matter.

The Exponential Mechanism

The Laplace mechanism works for real-valued outputs. But many natural outputs are discrete or categorical — the most common search query string, the best expert among a panel, the optimal auction price. Adding noise to these does not make sense.

Why the factor of 2?

Adding one individual can increase the utility of some outcomes and decrease the utility of others simultaneously. The $2\Delta u$ denominator accounts for this: the numerator contributes at most $e^{\varepsilon/2}$, and the ratio of normalizing constants contributes another $e^{\varepsilon/2}$.

Outputs far below the optimum are exponentially unlikely. This bound is a template: plug in $|\Psi|$, $|\Psi^*|$, and the gap $u^* - V$ for each application.

Limitations of Independent Noise

Laplace answers queries independently, with noise uncorrelated across queries. It cannot exploit structure shared between queries.

SmallDB: Nets, Exponential Mechanism, Accuracy

Motivation: Answering Exponentially Many Queries

With $n$ data points and Laplace noise, we can accurately answer roughly $n$ adaptive queries. Can we do better? Remarkably, yes: with the exponential mechanism we can answer exponentially many counting queries by releasing a synthetic database.

Setup.

We have a real database $X$ of $n$ rows and a large collection $\mathcal{Q}$ of counting queries. Instead of answering each query directly, we release a synthetic database $\tilde{X}$ that approximates the fractional answers to all queries in $\mathcal{Q}$. The fractional query is $f_q(X) = \frac{1}{n}\sum_{i=1}^n q(x_i)$. We want $\tilde{X}$ such that for all $q\in\mathcal{Q}$: $$|f_q(\tilde{X}) - f_q(X)| \le \alpha.$$

The SmallDB Algorithm

Outcome space.

The exponential mechanism chooses $\tilde{X}$ from the set of all small databases of size $$m = \left\lceil \frac{\log|\mathcal{Q}|}{\alpha^2} \right\rceil,$$ drawn from the same universe as $X$. Crucially, $m$ depends only on $|\mathcal{Q}|$ and $\alpha$, not on $n$.

Utility function.

For a candidate small database $\psi$: $$u(X, \psi) = -\max_{q \in \mathcal{Q}} |f_q(X) - f_q(\psi)|.$$ All utilities are $\le 0$; a utility close to 0 means $\psi$ agrees well with $X$ on all queries.

Sensitivity.

Under the swap adjacency (replace one row of $X$), each fractional query changes by at most $1/n$, so $\Delta u = 1/n$.

Privacy and accuracy.

The exponential mechanism with parameter $\varepsilon$ is $\varepsilon$-DP, and with high probability outputs $\tilde{X}$ within $\alpha + O\!\left(\frac{\log|\mathcal{Q}|}{n\varepsilon}\right)$ of $X$ on all queries.

The Histogram Representation

Fix the universe $\mathcal{X}$ of all possible data rows with types $\mathcal{X}_1, \mathcal{X}_2, \ldots$

A small database of size $m$ corresponds to a histogram with entries summing to $m$. Even if the universe has $2^d$ types, a small database of size $m \ll 2^d$ has at most $m$ nonzero histogram entries.

The Net Theorem and the Probabilistic Method

Why this is surprising.

The size $m$ depends only on $|\mathcal{Q}|$ and $\alpha$, completely independent of $n$. No matter how large the original database, a tiny synthetic database of size $m$ can approximate all queries.

Accuracy of SmallDB

From the exponential mechanism accuracy theorem: $$d(X,\widehat{Z}) \;\lesssim\; \alpha + \frac{1}{\varepsilon n}\log|\mathcal{R}| + \frac{1}{\varepsilon n}\log(1/\beta),$$ where $\alpha$ is the net approximation error, the second term is the privacy penalty, and the third is a confidence correction.

Size of the Net

Each database in $\mathcal{R}$ has $m$ rows drawn from $\mathcal{X}$, so $|\mathcal{R}| \approx |\mathcal{X}|^m$, giving: $$\log|\mathcal{R}| \approx m\log|\mathcal{X}| = O\!\left(\frac{\log|\mathcal{Q}|}{\alpha^2}\log|\mathcal{X}|\right).$$

Optimizing the Error

Plugging into the accuracy bound and balancing $\alpha$ against the privacy term: $$\alpha \approx \frac{\log|\mathcal{Q}|\log|\mathcal{X}|}{\varepsilon n \alpha^2} \quad\Longrightarrow\quad \alpha^3 \approx \frac{\log|\mathcal{Q}|\log|\mathcal{X}|}{\varepsilon n} \quad\Longrightarrow\quad \alpha \approx \left(\frac{\log|\mathcal{Q}|\log|\mathcal{X}|}{\varepsilon n}\right)^{1/3}.$$ The absolute error satisfies $n\alpha \approx n^{2/3}$.

Why This Does Not Break Privacy Lower Bounds

Reconstruction theorems say: too many queries answered too accurately $\Rightarrow$ reconstruction of the database. SmallDB avoids this because the error $\approx n^{2/3}$ is large enough to prevent reconstruction — the noise is not too small.

Feature Dimension Warning

The accuracy bound depends on $\log|\mathcal{X}|$. If individuals have many features, $|\mathcal{X}|$ grows exponentially and the error grows accordingly.

Comparison with Laplace

• Laplace: answers each query independently with noise $\sim k/\varepsilon$; no structure across queries is exploited.

• SmallDB: releases one synthetic dataset; answers are correlated; supports query classes of exponential size.

Advanced Composition and Privacy Loss

Motivation: Going Beyond Simple Composition

Simple composition says that $k$ applications of an $\varepsilon$-DP mechanism cost $k\varepsilon$ in privacy. For large $k$ this bound is too pessimistic. Advanced composition shows the true cost scales like $\sqrt{k}\,\varepsilon$ — an exponential improvement for high-query regimes.

The key insight is that privacy loss is a random variable, not a fixed constant. It can be negative, and the positive and negative losses partially cancel. The cumulative loss behaves like a biased random walk.

The Adaptive Composition Game

Advanced composition is proved via a general game that captures cumulative privacy loss across different databases and mechanisms, not just repeated queries to one database.

The game.

1. The challenger fixes a secret bit $b \in \{0,1\}$ at the start.

2. In each round $i = 1, \ldots, k$:

   • The adversary chooses a pair of adjacent databases $x_i^0, x_i^1$ and an $\varepsilon$-DP mechanism $M_i$ (adaptively, based on all prior outputs).

   • The challenger returns $y_i \sim M_i(x_i^b)$.

3. After $k$ rounds, the adversary guesses $b$.

The adversary may use a different pair of databases and a different mechanism each round. This models your cumulative privacy loss across all databases you participate in throughout your life, not just one interaction.

Privacy Loss Random Variables

For an $\varepsilon$-DP mechanism: $|\mathcal{L}| \le \varepsilon$ almost surely (this is exactly the bounded log-ratio condition).

Negative Privacy Loss and the Random Walk Intuition

When is privacy loss negative?

The loss is negative when $\Pr[M(x)=c] < \Pr[M(y)=c]$: the observed output is more likely under the adjacent database $y$ than under the true database $x$. Instead of giving a hint toward $x$, the output points away from it, giving the adversary a false read.

The random walk picture.

Imagine your database is $x$. Each mechanism output shifts the adversary’s belief slightly toward $x$ (positive loss) or away from it (negative loss). Since $x$ is the true database, outputs are somewhat more likely under $x$, so the walk has a slight positive drift. But many steps go in the negative direction, partially canceling the drift. The cumulative loss after $k$ steps behaves like $O(\sqrt{k}\cdot\varepsilon)$ rather than $k\cdot\varepsilon$, just as a random walk with drift $\mu$ has standard deviation $O(\sqrt{k})$ after $k$ steps.

Expected loss is $O(\varepsilon^2)$, not $O(\varepsilon)$.

A technical lemma (proved using KL divergence properties) shows: $$\mathbb{E}[\mathcal{L}^{(Y)}_{M(x)\|M(y)}] \;\le\; \varepsilon(e^\varepsilon - 1) \;\le\; \varepsilon^2.$$ (The improved bound $\varepsilon^2$ without the factor of 2 was established in later work.) Since $\varepsilon < 1$, the expected loss per step is $\varepsilon^2 \ll \varepsilon$ — the positive and negative losses cancel to a much smaller residual than the worst case.

Adversary Views and Bad Views

Two parallel worlds.

Define the adversary’s view as everything it observes: its own randomness $R$ and all outputs $y_1, \ldots, y_k$. There are two parallel versions:

• $V^0$: the view when the secret bit is $0$ (challenger always runs $M_i(x_i^0)$).

• $V^1$: the view when the secret bit is $1$ (challenger always runs $M_i(x_i^1)$).

Privacy fails if these two views are distinguishable.

By the chain rule of probability and the DP bound at each step: $$\ln\frac{\Pr[V^0 = v]}{\Pr[V^1 = v]} = \sum_{i=1}^k \mathcal{L}_i,$$ where $\mathcal{L}_i$ is the privacy loss at step $i$, conditioned on the shared history.

Bad views.

A view $v$ is bad if $\Pr[V^0=v] > e^{\varepsilon^*} \Pr[V^1=v]$ for some target $\varepsilon^*$. Privacy fails only when the adversary lands in a bad view. We decompose: $$\Pr[V^0 \in S] \;\le\; \Pr[V^0 \text{ is bad}] + e^{\varepsilon^*} \Pr[V^1 \in S]$$ for any set $S$. If the probability of a bad view is at most $\delta$, the mechanism is $(\varepsilon^*, \delta)$-DP.

Applying Azuma–Hoeffding

The privacy losses $\mathcal{L}_1, \ldots, \mathcal{L}_k$ form a martingale difference sequence: each is bounded $|\mathcal{L}_i| \le \varepsilon$, and $\mathbb{E}[\mathcal{L}_i \mid \mathcal{L}_1,\ldots,\mathcal{L}_{i-1}] \le \varepsilon^2$. The Azuma–Hoeffding inequality applies to exactly this setting:

$$\Pr\!\left[\sum_{i=1}^k \mathcal{L}_i > k\varepsilon^2 + t\varepsilon\sqrt{k}\right] \;\le\; e^{-t^2/2}.$$

Setting $t = \sqrt{2\ln(1/\delta)}$ gives the right-hand side equal to $\delta$, and:

Optimal privacy budget.

Equating the two terms and solving for $\varepsilon$ as a function of $k$: choosing $\varepsilon \approx 1/\sqrt{k}$ minimizes the total privacy loss for a fixed number of queries.

Approximate Differential Privacy and the Gaussian Mechanism

Motivation: The Limits of Pure DP

All the mechanisms we have seen so far satisfy pure $\varepsilon$-differential privacy: for all adjacent $x,y$ and all events $S$, $\Pr[M(x)\in S] \le e^\varepsilon \Pr[M(y)\in S]$. This is a worst-case, information-theoretic guarantee.

The ubiquitous Gaussian distribution — beloved in statistics for its tail concentration and its connection to least-squares estimation — cannot satisfy this guarantee. Accommodating Gaussian noise requires a relaxed definition.

Why Gaussian Noise Does Not Give Pure DP

The natural question is: why use Laplace noise rather than Gaussian noise? Gaussian noise is familiar, analytically convenient, and has lighter tails. The answer is that Gaussian noise cannot satisfy pure $\varepsilon$-DP.

The log-ratio argument.

Pure $\varepsilon$-DP requires the log-ratio $\ln\frac{p_X(c)}{p_Y(c)}$ to be bounded by $\varepsilon$ for all outputs $c$ and all adjacent $X, Y$. For the Laplace distribution, this ratio is bounded everywhere because the PDF decays exponentially and the ratio of two shifted Laplace PDFs converges to a fixed constant. For the Gaussian $\mathcal{N}(f(X), \sigma^2)$ vs. $\mathcal{N}(f(Y), \sigma^2)$: $$\ln\frac{p_{f(X)}(c)}{p_{f(Y)}(c)} = \frac{(c - f(Y))^2 - (c - f(X))^2}{2\sigma^2} = \frac{(f(X)-f(Y))(2c - f(X) - f(Y))}{2\sigma^2}.$$ This is linear in $c$ and grows without bound as $c \to \pm\infty$. No finite $\varepsilon$ can bound the log-ratio over all outputs.

$\ell_2$ Sensitivity

Comparison to $\ell_1$ sensitivity.

For $k$ counting queries (each output coordinate is a fraction in $[0,1]$):

• $\ell_1$ sensitivity: $\Delta_1 f = k$ (each query can change by $1/n$ per person, and one person can affect all $k$ queries, giving total $\ell_1$ change $k/n$; scaling to sensitivity-1 queries gives $\Delta_1 = k$).

• $\ell_2$ sensitivity: $\Delta_2 f = \sqrt{k}$ (Cauchy–Schwarz: $\|\mathbf{1}\|_2 = \sqrt{k}$).

Since $\sqrt{k} \ll k$ for large $k$, the Gaussian mechanism can add far less noise than Laplace for high-dimensional queries — at the cost of the pure-DP guarantee.

Approximate $(\varepsilon,\delta)$-Differential Privacy

We relax the pure DP guarantee by allowing a small additive failure probability $\delta$.

Interpretation.

With probability at most $\delta$, the mechanism may “fail” — the ratio of output probabilities on adjacent databases may exceed $e^\varepsilon$. On the remaining $1-\delta$ probability mass, the standard $e^\varepsilon$ bound holds.

Quantifier order: pure vs. approximate.

There is a subtle but important difference:

• Pure DP. Fix $x$; simultaneously for all adjacent $y$ and all $S$, the ratio condition holds with probability 1.

• Approximate DP. Fix $x$ and $y$; a priori the probability of a “bad” event is at most $\delta$. But an adaptive adversary who chooses $y$ after seeing the output might be able to find an adjacent pair that violates the ratio for that particular output.

Pure DP is strictly stronger. In practice, approximate DP is widely used because it enables the Gaussian mechanism and better composition bounds.

How Small Must $\delta$ Be?

$\ell_2$ Sensitivity

The Gaussian mechanism adds noise calibrated to the $\ell_2$ sensitivity, which can be substantially smaller than the $\ell_1$ sensitivity used by Laplace.

Comparison for counting queries.

For $k$ arbitrary counting queries, adding or removing one individual can change each count by at most 1, so $f(x)-f(y)$ has at most $k$ nonzero entries each in $\{-1,0,1\}$.

• $\ell_1$ sensitivity: $\Delta_1 f = k$ (worst case: one individual affects all $k$ counts).

• $\ell_2$ sensitivity: $\Delta_2 f = \sqrt{k}$ (since $\|\cdot\|_2 \le \sqrt{k}\,\|\cdot\|_\infty$ and each coordinate is at most 1).

The Gaussian Mechanism

Why $\ell_2$ sensitivity?

The mechanism adds independent Gaussian noise of the same variance to each coordinate. The privacy loss depends on $\|f(x)-f(y)\|_2$: the $\ell_2$ distance between the outputs on adjacent databases. Calibrating $\sigma$ to $\Delta_2 f$ ensures coverage of the worst-case pair.

Accuracy of the Gaussian Mechanism

For a single coordinate $Y_i\sim\mathcal{N}(0,\sigma^2)$, standard Gaussian tail bounds give $$\Pr[|Y_i|\ge t\sigma] \;\le\; 2e^{-t^2/2}.$$ Applying a union bound over all $k$ coordinates:

Laplace vs. Gaussian: A Comparison

For $k$ arbitrary counting queries (so $\Delta_1 f = k$, $\Delta_2 f = \sqrt{k}$):

Connection to Advanced Composition

Advanced composition and the Gaussian mechanism both exploit the same phenomenon: with high probability, privacy loss accumulates like $O(\sqrt{k}\,\varepsilon)$, not $k\varepsilon$.

Sparse Vector and Private Multiplicative Weights

Motivation: Answering Many Queries Cheaply

So far every mechanism we have studied pays a privacy cost proportional to the number of queries answered. Sequential composition says $k$ queries each at privacy level $\varepsilon$ costs $k\varepsilon$ total. Can we do better when most queries have values that fall below a threshold?

The key observation: reporting that an answer is below a threshold is cheap. If a verifier only needs to know which queries are above a threshold $T$, we can inspect many queries privately while paying full privacy cost only for the ones we actually reveal.

The Sparse Vector Technique

Proof sketch.

The crucial insight is that $\bot$ outputs reveal essentially nothing about $x$: saying “this query is below the noisy threshold” is a statement about noise, not data. The formal argument proceeds by noting that:

• The noisy threshold $\hat{T}$ is sampled once and depends on $x$ only through the fixed $T$; adjacent datasets shift the threshold by at most $1$ (sensitivity of $T$).

• Each $\top$ output involves comparing $q_i(x) + \nu_i$ to $\hat{T}$. Changing one person shifts $q_i(x)$ by at most 1, absorbed by noise of scale $4c/\varepsilon$.

• $\bot$ outputs are never re-sampled, so they leak nothing about $x$ beyond the already-noisy comparison.

A coupling argument over adjacent $x, y$ bounds the log-likelihood ratio by $\varepsilon$.

Accuracy.

If a query $q_i$ satisfies $q_i(x) \geq T + \alpha$ (well above threshold), it is reported $\top$ with high probability; if $q_i(x) \leq T - \alpha$ (well below), it is reported $\bot$ with high probability. The error probability for a single query is $e^{-\Omega(\alpha \varepsilon / c)}$, so for $c = O(1)$ and $m$ queries, the overall error is small when $\alpha = O\!\left(\tfrac{c}{\varepsilon} \log m\right)$.

Application: private query release.

If an analyst submits queries one at a time and only cares which ones are significant (above threshold), SVT answers all of them at the same privacy cost as answering $c$ individually. This is useful when the “interesting” queries are sparse among a large pool of candidates.

Private Multiplicative Weights (PMW)

Sparse vector tells us which queries are significant; Private Multiplicative Weights uses those answers to build a synthetic database that answers future queries accurately.

Setting.

We have a true dataset $x$ over a universe $\mathcal{U}$ of records, and we want to maintain a candidate distribution $\mathbf{z}$ over $\mathcal{U}$ such that for any future linear query $q$, $q(\mathbf{z}) \approx q(x)$.

Algorithm.

Initialize $\mathbf{z}^{(0)}$ to the uniform distribution over $\mathcal{U}$. At each round $t$:

1. The analyst submits query $q_t$.

2. If $|q_t(\mathbf{z}^{(t)}) - q_t(x)| \leq \alpha$ (small error): output the noisy answer and do not update ($\mathbf{z}^{(t+1)} = \mathbf{z}^{(t)}$).

3. Otherwise (significant mistake): update via multiplicative weights: $$\mathbf{z}^{(t+1)}_u \;\propto\; \mathbf{z}^{(t)}_u \cdot \exp\!\Bigl(-\eta\, q_t(u) \cdot \mathrm{sgn}\bigl(q_t(\mathbf{z}^{(t)}) - q_t(x)\bigr)\Bigr),$$ where $\eta > 0$ is a learning rate. This multiplicatively downweights records $u$ that contribute to the mistake.

Potential function analysis.

Define the potential $$\Phi_t \;=\; \mathrm{KL}\!\left(x \,\|\, \mathbf{z}^{(t)}\right) \;=\; \sum_{u} x_u \ln \frac{x_u}{\mathbf{z}^{(t)}_u} \;\geq\; 0.$$ Two facts drive the analysis:

• Upper bound: $\Phi_0 = \mathrm{KL}(x \| \mathbf{z}^{(0)}) \leq \ln|\mathcal{U}|$ (uniform initialization maximizes entropy).

• Descent: each significant update decreases $\Phi_t$ by at least $\Omega(\eta\alpha)$.

Proof.

Each significant mistake means $|q_t(\mathbf{z}^{(t)}) - q_t(x)| > \alpha$, which causes $\Phi_t$ to drop by at least $\eta\alpha - O(\eta^2)$ (by a Taylor expansion of $\ln$ after the multiplicative update, setting $\eta = \alpha / 2$). Since $\Phi_t \geq 0$ and $\Phi_0 \leq \ln|\mathcal{U}|$, there can be at most $\ln|\mathcal{U}| / (\eta\alpha - O(\eta^2)) = O(\ln|\mathcal{U}|/\eta^2)$ such drops.

Privacy.

Each significant round uses one noisy answer (via the Laplace mechanism at scale $O(1/(\varepsilon n))$) to decide whether to update. By the convergence theorem, only $T^*$ such answers are ever used, so the total privacy cost is $T^* \cdot \varepsilon_0$ for a per-query budget $\varepsilon_0$. Choosing $\varepsilon_0 = \varepsilon / T^*$ gives $\varepsilon$-DP overall.

Accuracy.

After the synthetic database stabilizes (no more significant updates), it answers any query in the query class to within error $\alpha$. Setting $\alpha = O(\sqrt{\ln|\mathcal{U}|} / \sqrt{n})$ and the noise scale accordingly gives:

Paper Readings

Dwork, Naor, Reingold, Rothblum, Vadhan (2009) — On the Complexity of Differentially Private Data Release.

Introduces the Sparse Vector Technique as a tool for answering many queries while charging privacy cost only for those whose answers cross a significance threshold. The main result characterizes when private data release with low error is computationally feasible, and shows that restricting to above-threshold queries dramatically reduces the effective privacy cost relative to answering everything. The SVT mechanism analyzed in this chapter is a direct instantiation of these ideas.

Hardt and Rothblum (2010) — A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis.

Shows that the private multiplicative weights algorithm achieves near-optimal accuracy for releasing all linear queries over a data universe under differential privacy. The key insight is a potential function argument: the KL divergence from the true data distribution to the current synthetic hypothesis decreases by a fixed amount per significant update, bounding the total number of corrective rounds by $O(\log|\mathcal{U}|/\eta^2)$. This gives the first efficient differentially private synthetic data generator with provable accuracy guarantees for an exponentially large query class.

The US Census, Reconstruction, and Why DP Was Needed

Origin Story

When Cynthia Dwork and colleagues began thinking about privacy for statistical analysis of large datasets around 2001, the model they had in mind was the US Census. The Census is a great cause: it counts the population, determines political representation, and allocates hundreds of billions of dollars in federal funds—with no commercial interest involved. Crucially, unlike most data holders, the Census Bureau is legally mandated to protect confidentiality, providing a genuine customer for rigorous mathematical privacy guarantees.

The connection between differential privacy and the Census developed over several years. Adam Smith (later a co-inventor of DP) was among the early collaborators who recognized that the Bureau’s existing confidentiality methods—while well-intentioned—could not withstand the kind of reconstruction attacks that were becoming computationally feasible. In 2017, the Bureau carried out internal reconstruction tests, confirmed that their prior methods were insufficient, and decided to modernize using differential privacy. The 2020 decennial census was the result.

Why the Census Matters

The decennial census is a constitutionally mandated enumeration of all people—not just citizens—living in the United States. Its outputs drive:

• Congressional apportionment. The 435 seats in the House of Representatives are allocated among states by the Huntington–Hill algorithm based on state population totals. When one state loses population and another gains, a seat transfers.

• Electoral college. Each state’s electoral votes equal its House seats plus two senators—directly derived from Census counts.

• Redistricting. Within each state, congressional and legislative district boundaries are drawn to equalize population ($\le 5\%$ variation is the judicial standard). These numbers also feature in Voting Rights Act lawsuits about minority representation.

• Federal funding. Hundreds of billions of dollars in formula-driven programs (education, infrastructure, housing) flow to states and localities based on population counts.

• Policy research. Researchers and policymakers use fine-grained demographic data to measure disparities, plan school resources, and target public services.

Marginalized populations—undocumented immigrants, people experiencing homelessness, communities with historical distrust of government—are systematically harder to enumerate. States that invest more in outreach get more accurate (and advantageous) counts.

What the Census Collects

The 2020 decennial census form collected, for each person in each household:

• Name and whether the person normally lives elsewhere (college students, incarcerated individuals, and rehab residents are counted at their current location).

• Relationship to person 1 (spouse/partner, biological/adopted child, parent-in-law, roommate, foster child, etc.).

• Sex (two options in 2020).

• Age and date of birth.

• Ethnicity: Hispanic/Latino origin (Mexican, Puerto Rican, Cuban, etc.) or not. In Census terminology “ethnicity” always means Hispanic or non-Hispanic.

• Race: checkboxes for White (with origin detail), Black or African American, American Indian or Alaska Native (with tribal affiliation), Chinese, Filipino, Asian Indian, Vietnamese, Korean, Japanese, other Asian, Native Hawaiian, Samoan, Chamorro, other Pacific Islander, or some other race. Multiple boxes may be checked, yielding 63 possible combinations.

What counts as a “race” on the Census form is explicitly political and has changed dramatically over time—Jews and Italians have at various points been proposed as separate races. Race is always self-identification; people change their declared race between censuses, and the Bureau does not challenge such changes.

Legal Confidentiality Requirements

The Census is governed by Title 13 of the US Code, which imposes strict confidentiality obligations:

Because responding to the Census is legally required, confidentiality protections are essential for encouraging accurate responses, especially from people who fear the government. The Bureau does not do law enforcement; even people who are breaking the law should feel safe in reporting their true situation.

Why Privacy Harms Are Real

1. Section 8 housing eviction. Federal housing leases specify maximum household occupancy. If Census data reveals that a household has more occupants than their lease permits, the family could be evicted and become homeless—a direct, concrete harm from privacy compromise.

2. Legal prosecution. A family reports a 13-year-old girl where a prior census recorded a 3-year-old boy. In states where supporting gender re-identification is illegal, this could result in prosecution.

3. Doxing and harassment. Even if your neighbors know your household is a same-sex couple, a compiled national list of gay households is qualitatively different from distributed local knowledge. Information known in a distributed fashion has different safety implications than information in a centralized, searchable list that could be weaponized.

The Bureau’s own rules: responses cannot be used to the detriment of any respondent. Each example above is a case where published statistics could, via reconstruction, be used to harm the very people who trusted the Bureau with their data.

Census Geography

The Bureau’s fundamental geographic unit is the census block—the smallest unit, ranging from zero to roughly 2,000 inhabitants (the density of a city block). The Bureau uses the analogy of pixels: it is acceptable to blur the pixels a little, as in an Impressionist painting—when you step back, you still see the correct picture.

Blocks aggregate upward in a hierarchy: $$\text{Block} \to \text{Block Group} \to \text{Census Tract} \to \text{County} \to \text{State} \to \text{Division} \to \text{Region}$$ Additional overlapping geographic entities—zip code tabulation areas, school districts, voting districts—are also constructed from block-level data. American Indian, Alaska Native, and Native Hawaiian areas have their own separate spine because these communities cross state boundaries and have very small populations that require special handling.

The Old Method: Record Swapping

Before differential privacy, the 2010, 2000, and 1990 censuses used a method called record swapping:

1. Identify “at-risk” households—those that stand out in their neighborhood (racial minorities in a non-diverse block, unusually large households, same-sex couples in an area without others like them, etc.).

2. Find a “match” household elsewhere in the country that agrees on total population and voting-age population.

3. Swap all the detailed records between the two households.

The exact algorithm was secret, may not have been fully algorithmic, and was not applied uniformly across demographic groups. The swapped dataset—the “100% data file”—was treated as the Bureau’s official reference, and all tabulations were computed from it.

The problem.

The swapping rate was low (typically a small fraction of households), which means the 100% data file was very close to the original Census Edited File (CEF). And as we will see next, no amount of swapping could protect against reconstruction from the sheer volume of statistics released.

Scale of the 2010 Census Release

From the 2010 census, the Bureau published:

• 150 billion statistics in total.

• 86 billion linearly independent statistics at the block level.

• 241 million linearly independent statistics at the tract level.

This is a massive collection of accurate, fine-grained aggregate counts with essentially no noise added for privacy.

The Reconstruction Attack

The Bureau’s internal team (later published in 2025 after security clearance) showed that published statistics could reconstruct the 100% data file.

BEARS fields.

The attack focused on five fields (the acronym BEARS): Block, Ethnicity, Age, Race, Sex. Each individual can be characterized by their combination of BEARS values—their “person type.”

The reconstruction procedure.

1. From the published tabulations, extract the count of each BEARS person-type in each block. This yields a large system of linear/integer constraints that any consistent microdata set must satisfy.

2. Feed the constraints to a commercial integer program solver to reconstruct a candidate dataset $\hat{X}$ consistent with the published statistics.

3. The reconstructed dataset $\hat{X}$ is called the Reconstructed 100% Data File (RHDF).

Solution variability.

The solver may find multiple solutions. The attackers exploited this by solving a second integer program: given the published solution, find the dataset $Z$ maximizing distance from it—but the true dataset is also a valid solution. If this maximum distance is small, the true dataset cannot be far from the reconstruction. The attacker can certify how accurate the attack was using only public information.

In practice, most blocks had only one solution consistent with the published statistics, meaning the published data uniquely determined individual-level BEARS information for most people.

Re-identification.

Once BEARS fields are reconstructed, the attacker links the reconstructed dataset to commercial databases (voter rolls, credit records, etc.) that share block, age, race, and sex. Reconstruction followed by re-identification is then trivial.

The lawyers’ reaction.

When the Bureau’s statisticians and computer scientists presented these findings, the lawyers asked: “Can we retract the 2010 Census publications?” The data were already on the public web and could not be clawed back. The lawyers concluded: “We can’t do this again.” The Bureau’s argument to itself: the distinction between publishing microdata (protected by subsampling) and publishing tabular statistics (no explicit protection) is not justified. From enough accurate tabulations, one can reconstruct microdata without any sampling secrecy.

Why Swapping Was Not Enough

The Bureau’s own argument: since the RHDF closely reproduced the 100% data file (post-swapping), and the 100% data file was already very close to the original CEF (swapping was low-rate), the reconstruction was essentially recovering the true census microdata. The Bureau decided this violated its own confidentiality mandate.

No amount of swapping can protect against reconstruction when the number of published statistics exceeds the effective entropy of the dataset.

Concentrated Differential Privacy

The scale of the Census—billions of statistics, millions of geographic units, tight accuracy requirements for redistricting—motivated a variant of differential privacy called concentrated differential privacy.

Motivation.

Recall from advanced composition (Chapter 8): to achieve $(\varepsilon,\delta)$-DP over $k$ mechanisms, each individual mechanism must use noise of order $\varepsilon / (\sqrt{k \ln(1/\delta)})$. The $\sqrt{\ln(1/\delta)}$ factor is annoying: when $\delta$ must be cryptographically small, this factor can be as large as 10, forcing 10$\times$ more noise.

The key insight: the $\varepsilon\delta$ guarantee is itself probabilistic. Why require each building block to never exceed $\varepsilon/(\sqrt{k}\sqrt{\ln 1/\delta})$? If in expectation each step contributes $\varepsilon/\sqrt{k}$, and the excess cancels out, we get the same asymptotic behavior without the $\sqrt{\ln 1/\delta}$ penalty.

Definition.

Informally, concentrated differential privacy (CDP) requires that the privacy loss random variable $\mathcal{L}$ behaves like a Gaussian: $$\forall k:\quad \Pr[\mathcal{L} > k\varepsilon] \;\le\; e^{-\Theta(k^2)}.$$ This is exactly the tail behavior of a Gaussian distribution—hence “concentrated.”

Zero-concentrated DP (zCDP).

Dwork and Rothblum introduced an initial version of CDP. Bun and Steinke later introduced zero-concentrated differential privacy (zCDP), using a slightly different characterization of sub-Gaussian random variables that achieves exact closure under post-processing. zCDP is the variant used in the 2020 Census.

Practical benefit.

Under zCDP, composing $k$ mechanisms eliminates the $\sqrt{\ln(1/\delta)}$ overhead entirely. For the Census, where $\delta$ must be extremely small, this represents a factor of up to $10\times$ reduction in the noise that must be added—a massive accuracy gain for redistricting.

The Lawsuits: Why 16 States Sued

Following the Census Bureau’s adoption of differential privacy for the 2020 decennial census, sixteen states—predominantly Republican-led—brought suit, arguing that DP produced unreliable data. The stated technical argument:

“Because differential privacy creates false information by design, it prevents the states from accessing municipal-level information crucial to performing this essential government function.”

A few observations on this argument:

State-level counts are preserved.

Differential privacy in the 2020 Census (the TopDown algorithm) preserves exact state-level population totals, which are the constitutional basis for House apportionment and electoral college votes. DP noise is applied only at finer geographic levels. Any accuracy concerns about redistricting must be weighed against the accuracy gains from having a mathematically rigorous, auditable guarantee, versus the old swapping method whose error was uncharacterized and secret.

Paper Readings

Abowd et al. (2025) — The 2010 Census Confidentiality Protection Evaluation.

Using only publicly released 2010 Census tabulations, the authors reconstructed the BEARS fields (block, ethnicity, age, race, sex) for essentially all individuals in the 100% data file, then linked the reconstruction to commercial databases to re-identify a large fraction of the population. The paper was classified for years due to its sensitivity and released only after the 2020 Census was finalized; it provided the definitive technical justification for the Bureau’s adoption of differential privacy.

Abowd et al. (2022) — The 2020 Census Disclosure Avoidance System.

Full specification of the TopDown algorithm used in the 2020 Census: a hierarchical allocation of a global zCDP privacy budget that processes the geographic hierarchy from nation down to census block, using integer programming at each level to ensure consistency of counts across geographic units. The algorithm and its code are publicly available on GitHub, and it was tested against 2010 data during an extended public comment period — allowing affected communities, including Native American tribes whose geographic units cross state lines, to advocate for changes in budget allocation before the 2020 enumeration.

DP Protects Against Overfitting

Friedman’s Paradox

Consider a standard regression setting. We have a design matrix $X \in \mathbb{R}^{n \times d}$ where each row is an observation (a person) and each column is a feature. We observe an outcome vector $Y \in \mathbb{R}^n$ and believe it satisfies $$Y = X\beta + \varepsilon$$ for some true weight vector $\beta$ and small noise $\varepsilon$. A natural data-analysis workflow is:

1. Fit $\beta$ by minimizing $\|\varepsilon\|$.

2. Inspect the coefficients: drop features whose fitted weight is near zero (“clearly irrelevant”).

3. Refit the equation on the remaining features and report a clean model.

This seems entirely reasonable. Friedman’s paradox shows it is catastrophically wrong.

The setup.

Let every entry of $X$ be an independent draw from $\mathcal{N}(0,1)$, and let $Y$ also be a vector of independent $\mathcal{N}(0,1)$ draws. There is no real relationship between $X$ and $Y$ whatsoever.

The problem.

Even so, the procedure above finds “significant” predictive features. The reason is anti-concentration: by ordinary sampling variation, some features will, purely by accident, be slightly further from their expected value than others. The procedure selects those accidentally-extreme features and then declares victory — but the relationship is a statistical fluke, not a real signal.

Formally: we are implicitly taking the maximum over many random variables. The maximum of $d$ i.i.d. mean-zero variables is not mean-zero; it is $\Theta(\sqrt{\log d})$. By keeping only the features with large fitted weights, we are conditioning on a high-probability event of the noise, then treating the conditioned noise as signal.

Exploratory vs. Adaptive Data Analysis

In statistics, the general practice of “looking around in the data for a signal before deciding what to ask” is called exploratory data analysis (EDA). It is ubiquitous and has no universally accepted principled remedy.

In computer science the same phenomenon goes by a different name: adaptive data analysis. The analyst adapts the next question to the answers received so far. This dependence between queries and the data set is the root cause of overfitting.

Why naivety and malice are indistinguishable.

Friedman’s paradox shows that a completely well-intentioned analyst using a standard procedure can produce results indistinguishable from deliberate data manipulation. We therefore cannot rely on the good intentions of analysts when designing statistical methodology: we must build defenses that are robust even against the worst case.

Overfitting, formally.

Concretely: if a trained classifier achieves 95% accuracy on the training set but only 55% accuracy on fresh draws from the same distribution, it has overfit. The training effort was wasted; the model learned noise, not signal.

The Accuracy Adversary

We formalize the problem by defining an adversary whose sole goal is to cause overfitting.

Setup.

Fix a universe $\mathcal{X}$, a distribution $\mathcal{D}$ on $\mathcal{X}$, a data set $X = (x_1,\ldots,x_n)$ drawn i.i.d. from $\mathcal{D}$, and a class $\mathcal{Q}$ of counting queries: functions $q : \mathcal{X} \to \{0,1\}$.

For a query $q$ define: $$\hat{\mu}(q, X) = \frac{1}{n}\sum_{i=1}^n q(x_i) \qquad\text{(empirical mean on }X\text{)} \qquad \mu(q) = \mathop{\mathbb{E}}_{z \sim \mathcal{D}}[q(z)] \qquad\text{(true distributional mean)}.$$

The adversary is modeled as purely malicious for the same reason cryptographic security definitions assume the worst-case attacker: it makes the guarantee unconditional. An honest-but-naive analyst is captured as a special case.

Non-Adaptive Baseline: Chernoff Bound

If the queries are fixed before the data set is collected (non-adaptive), standard concentration bounds already give strong guarantees.

The key word is “fixed in advance.” This guarantee fails completely if queries are chosen adaptively based on answers to previous queries.

The Killer Query

To see why adaptivity destroys non-adaptive accuracy guarantees, suppose the adversary has somehow learned the data set $X$ exactly. Define: $$q^*(z) = \begin{cases} 1 & z \in X \\ 0 & z \notin X. \end{cases}$$

Then: $$\hat{\mu}(q^*, X) = 1 \qquad\text{(every element of }X\text{ maps to 1)}$$ $$\mu(q^*) = \Pr_{z \sim \mathcal{D}}[z \in X] = \frac{n}{|\mathcal{X}|} \approx 0 \quad\text{(data set is a tiny fraction of the universe)}.$$

The gap is $\approx 1$, which exceeds any reasonable $\tau$. The killer query is trivial to construct once the data set is known.

How might an adversary learn $X$? Via a coding query: define $q_{\mathrm{code}}(z) = 2^{-z}$ (treating elements as integers), then $\sum_{z \in X} 2^{-z}$ is a binary encoding of $X$. Alternatively, the adversary could launch a database reconstruction attack (as studied in Chapter 11). Either way: if the adversary learns $X$, the game is over.

This motivates our goal: answer queries in a way that prevents the adversary from learning too much about $X$, even adaptively.

Formal Model of Adaptive Data Analysis

The adaptive interaction.

The adversary $\mathcal{A}$ proceeds in rounds:

1. Choose query $Q_1$ (with no access to $X$; this round is trivially non-adaptive).

2. Receive answer $A_1 = M(X, Q_1)$ from mechanism $M$.

3. Choose $Q_2$ based on $A_1$. Receive $A_2 = M(X, Q_2)$.

4. $\ldots$

5. Choose $Q_i$ based on $(A_1,\ldots,A_{i-1})$. Receive $A_i$.

The adversary wins if any $Q_i$ is bad for $X$ (i.e., $|\hat{\mu}(Q_i, X) - \mu(Q_i)| > \tau$).

Why the first query is safe.

At round 1, $\mathcal{A}$ has not seen any answer from $M(X,\cdot)$. Therefore $Q_1$ is completely independent of $X$. By the Chernoff bound, $\Pr[X \text{ is bad for } Q_1] \le 2e^{-2n\tau^2}$, regardless of the adversary’s strategy.

Simple solution: data splitting.

Reserve $1/\tau^2$ fresh samples for each query. Answer $Q_i$ using its own reserved subsample (then discard those samples). This handles $n\tau^2$ queries but wastes data linearly. We want exponentially better.

Max-Information

The key to proving that differential privacy prevents overfitting is a new information-theoretic quantity introduced by Dwork et al.

Intuition.

• $k = 0$: $\mathbf{D}$ and $\boldsymbol{\Phi}$ are completely independent. Observing the query tells you nothing about the data set.

• $k > 0$: observing $\boldsymbol{\Phi} = \varphi$ can increase the probability of any particular data set by at most a factor of $2^k$. As $k$ grows, the query leaks more about the data set (and vice versa).

Connection to mutual information.

Max-information is a worst-case variant of mutual information $I(\mathbf{D}; \boldsymbol{\Phi})$ from information theory. Standard mutual information measures the average reduction in uncertainty; max-information measures the worst-case increase in log-probability. The symmetry $I_\infty(\mathbf{D}; \boldsymbol{\Phi}) = I_\infty(\boldsymbol{\Phi}; \mathbf{D})$ follows from Bayes’ theorem: the condition $\Pr[\mathbf{D}=d \mid \boldsymbol{\Phi}=\varphi] \le 2^k \Pr[\mathbf{D}=d]$ is equivalent to $\Pr[\boldsymbol{\Phi}=\varphi \mid \mathbf{D}=d] \le 2^k \Pr[\boldsymbol{\Phi}=\varphi]$ (up to the same constant $k$), by a Bayes’ theorem rearrangement.

Differential Privacy Bounds Max-Information

The proof uses exactly two properties of differential privacy: post-processing (the adversary’s query choice is a post-processing of the DP outputs) and group privacy (all data sets are within $n$ substitutions of each other).

DP Protects Against Overfitting

We now combine the max-information bound with the standard Chernoff sampling assumption to prove the main result.

Assumption.

For a fixed query $q$, the probability over a randomly drawn data set $X$ that $X$ is bad for $q$ (i.e., not $\tau$-representative) is at most $2^{-cn}$ for some constant $c > 0$ (this follows from the Chernoff bound with $c = 2\tau^2 / \ln 2$). Let $B_q$ denote the set of data sets that are bad for $q$.

The key intellectual leap.

Overfitting is reframed as a win for the accuracy adversary. Once we define the adversary formally, standard tools from differential privacy — post-processing, group privacy, and composition — give a complete, quantitative, and mechanistic explanation of why DP prevents overfitting.

The Reusable Holdout

Standard holdout (and its failure mode).

The classical defense against overfitting is to reserve a holdout set $H$ that is never used during training. The analyst works freely on the training set $T$, derives a hypothesis, and evaluates it once on $H$. If $H$ gives a good result, the hypothesis is accepted.

The problem: if the hypothesis fails on $H$, the analyst wants to try again. But now the choice of what to try next has been influenced by $H$’s answer. The holdout set is tainted and cannot be safely reused. In practice, analysts use holdout sets many times, invalidating the statistical guarantees.

The fix: wrap $H$ in a DP mechanism.

 

Conceptually: the accuracy adversary has the training set $T$ hardwired into its strategy. Its only access to $H$ is through the private mechanism. Theorem [th:dp-overfit] then guarantees that no adaptive sequence of queries can overfit $H$.

The Algorithm: Numeric Sparse Vector

The reusable holdout has a concrete algorithmic instantiation. Given:

• A training set $T$ and holdout set $H$,

• A privacy budget $B$ (total number of DP queries to $H$),

• An overfitting budget $k_{\max}$ (number of detected overfits allowed),

• Parameters $\tau$ (accuracy threshold) and $\sigma$ (noise level),

the algorithm handles each incoming statistical query $q : \mathcal{X} \to [-1,1]$ as follows:

1. Draw a random sample $S \subseteq T$ (from the training set).

2. Compare the holdout answer $\hat{\mu}(q,H) + \text{noise}$ against the training estimate $\hat{\mu}(q,S)$.

3. If the two estimates are close (within a threshold $\tilde{\tau}$): output the training estimate and continue. No privacy budget is spent.

4. If the two estimates are far apart (the training answer is overfit): output the holdout estimate, decrement the overfitting budget, and continue.

5. If the overfitting budget is exhausted: halt.

The connection to Sparse Vector.

This algorithm is precisely Numeric Sparse Vector (a variant of the Sparse Vector Technique from Chapter 11), applied with the holdout mechanism as the private database and the analyst’s queries as the input stream. Sparse Vector was introduced as an abstract privacy tool; here it reappears as the heart of a practically motivated reusable holdout mechanism.

Paper Readings

Dwork et al. (2015) — Preserving Statistical Validity in Adaptive Data Analysis.

Shows that running adaptive statistical queries under differential privacy bounds the max-information $I_\infty$ between the dataset and the sequence of query answers, which in turn implies that all reported p-values and confidence intervals remain honest. Classical statistical practice assumes queries are chosen independently of the data; this paper formalizes what goes wrong when they are not, and proves that DP is a sufficient condition for validity even under arbitrary adaptivity. The result reframes differential privacy as a tool for statistical integrity rather than purely for individual privacy, connecting the two halves of this course.

Foundations of Modern Cryptography

What is Cryptography?

• Cryptography: building secure systems

• Cryptanalysis: breaking them

• Cryptology: both together

What Problems Does Cryptography Solve?

• Secure communication: secrecy (confidentiality), integrity (no tampering), authentication (know the sender).

• Digital signatures: authenticity + transferable proof of origin (not just convincing the receiver, but any third party).

• Pseudorandom generators: “stretch” a random seed to a longer string that “looks” random.

• Collision-resistant hash functions: hard to find $m \ne m'$ with $H(m)=H(m')$. In practice, signatures are applied to a hash of the message, not the full message.

• Commitment schemes: commit to a secret value $z$ by publishing $\alpha$ that is hiding (reveals nothing about $z$) and binding (hard to open as a different value). Analogy: write a prediction on paper, seal it in an envelope. Neither party can alter it, but nobody can read it until the envelope is opened.

• Private Information Retrieval (PIR): librarian can’t determine which book you read / which data you downloaded.

• Homomorphic encryption: “compute” on encrypted values.

• Non-malleable encryption: given $E(x)$ and function $f$, can’t find $E(f(x))$.

• Zero-knowledge proofs: prove a statement without revealing why it is true.

Two Innovations of Modern Cryptography

Innovation 1: Base security on complexity theory

Instead of requiring information-theoretic impossibility, require only that breaking the scheme is computationally infeasible. The central primitive is a one-way function.

Hardness is computational, not information-theoretic.

A trapdoor function is a one-way function that becomes easy to invert given secret auxiliary information (the “trapdoor”). This is essential for public-key encryption: everyone can encrypt; only the receiver can decrypt.

Innovation 2: Security by reduction

Complexity-Theoretic Background

Asymptotic notation

An algorithm has running time $O(f(n))$ if there exist constants $C$ and $n_0$ such that for all $n \ge n_0$, the running time is at most $C \cdot f(n)$. This captures the growth rate but hides constants and small-$n$ behavior. Example: sorting $n$ numbers requires $\Theta(n \log n)$ comparisons (both upper and lower bound).

Polynomial time and negligible functions

A problem is efficiently solvable if there exists a polynomial-time algorithm for it. In cryptography we want to argue the opposite: that no efficient algorithm can break a scheme. This requires care, since asserting “no polynomial-time algorithm exists” is an unproven conjecture for most problems of interest (and proving it would resolve P vs. NP).

We capture hardness probabilistically: a function $\mu(k)$ is negligible if it decreases faster than the inverse of any polynomial—for every polynomial $p$, there exists $k_0$ such that $\mu(k) < 1/p(k)$ for all $k > k_0$.

What does it mean for an algorithm to fail?

Saying an algorithm $A$ does not factor integers requires precision. Options:

• Fails on all inputs of each size—too strong; easy inputs (even numbers) are trivially factorable.

• Fails on all but a negligible fraction of inputs of each size—the right notion. For every polynomial $p$ and all sufficiently large $k$, $A$ fails to factor a randomly chosen $k$-bit number with probability at least $1 - 1/p(k)$.

The second formulation correctly captures that factoring a random integer is hard even if a constant fraction of inputs are easy.

Uniform vs. non-uniform computation

A Turing machine (or equivalently, a fixed program in C) is a uniform model: one program of fixed length works for all input sizes. A circuit family is a non-uniform model: one circuit per input size, and each circuit can be different (and can have hard-coded solutions for specific instances). Non-uniform circuits are strictly more powerful; in cryptography we usually work with uniform (Turing machine) adversaries, though the distinction matters in some proofs.

One-Way Functions

Security parameter. The string $1^k$ (a sequence of $k$ ones) is fed to $A$ to ensure it can run in time polynomial in $k$. Without this, $A$ might not have enough time to read the implicit security level.

Valid inversions. Note that $A$ wins if it produces any pre-image of $f(x)$, not necessarily $x$ itself (since $f$ need not be injective).

Candidate: integer factoring.

Let $f(a,b) = a \cdot b$ for $k$-bit primes $a,b$. Computing $f$ is easy (multiplication); inverting (factoring the product into its prime factors) is believed to be hard. RSA is built on this conjecture. Note: the naive formulation “given a random $k$-bit integer, factor it” is too weak because roughly half of all integers are even and trivially factorable. The correct hardness conjecture restricts to products of two random $k$-bit primes.

Candidate: lattice problems.

Problems such as finding the shortest vector in a lattice, or learning with errors (LWE), have been studied for decades without yielding polynomial-time solutions. They form the basis of post-quantum cryptography—schemes believed to resist quantum computers. (Ajtai 1996 initiated this direction; Google’s current post-quantum transition is likely lattice-based.)

Trapdoor Functions

Trapdoor functions are essential for public-key encryption: the public key encodes $f$, the private key encodes $\tau$. Anyone can encrypt (apply $f$); only the key holder can decrypt (invert using $\tau$).

Finding Large Primes Efficiently

Building RSA requires generating large primes. This is surprisingly easy:

1. By the prime number theorem, a random $k$-bit integer is prime with probability approximately $1/(k \ln 2) = \Theta(1/k)$.

2. Primality testing can be done in polynomial time (AKS, or probabilistic tests like Miller–Rabin).

3. Algorithm: repeatedly sample a random $k$-bit integer and test for primality. Expected number of trials: $O(k)$. Each test runs in polynomial time in $k$, so the whole procedure is efficient.

In practice, RSA uses primes of 1024 bits each; their product is a 2048-bit modulus. The randomization in key generation is essential: if the same prime were always chosen, an attacker could precompute.

One-Way Functions and Pseudorandom Generators

This chapter develops the formal theory underlying the primitives introduced in Chapter 13. The material follows Goldwasser–Bellare (GB) Sections 2.4.1, 3.1–3.4, and Barak Section 2.4.

Formal Definition of One-Way Functions

Important warning.

OWF hardness is directional (easy forward, hard backward), not the same as NP-hardness. OWF existence is an unproven assumption; it implies P $\neq$ NP but is believed to be strictly stronger.

Hard-Core Predicates

A one-way function $f$ hides its input $x$ when given $f(x)$, but how much does it hide? A hard-core predicate extracts a single bit of $x$ that is provably hidden.

In words: given $f(x)$, the adversary cannot guess $B(x)$ with probability noticeably better than $1/2$ (random guessing).

An alternative but equivalent characterization (GB Def. 2.50):

The Goldreich–Levin Theorem

The most important result about hard-core predicates is that every one-way function has one — we need not search for $f$-specific tricks.

Why must $r$ be included in the output of $f'$?

To compute $B(x\circ r)=\langle x,r\rangle$, the receiver needs $r$. So $f'$ reveals $r$ (which is public anyway) while hiding $x$ (since $f$ is one-way). If $r$ were hidden, even the legitimate user could not evaluate $B$.

Proof sketch (by reduction).

Suppose $\mathcal{A}$ predicts $B(x\circ r)$ with advantage $\varepsilon > 1/p(k)$. One constructs a reduction $\mathcal{B}$ that, given $f(x)$, uses $\mathcal{A}$ as a subroutine to recover $x$ with non-negligible probability — contradicting that $f$ is a OWF. The key idea: $\langle x,r\rangle \bmod 2$ is a random parity of $x$; random $r$ makes all such parities “look independent,” so any non-trivial prediction of the parity implies partial knowledge of $x$.

Pseudorandom Generators: Definitions

A pseudorandom generator (PRG) stretches a short truly random seed into a longer output that is computationally indistinguishable from uniform randomness.

Relationship to Barak Definition 2.10.

The PRG security condition $G(U_k)\approx_p U_{\ell(k)}$ is exactly the asymptotic indistinguishability (Definition 2.10 from Barak, see §1.3) applied to the two ensembles $\{G(U_k)\}$ and $\{U_{\ell(k)}\}$.

Constructing a PRG from a One-Way Function

The proof is constructive and proceeds in two steps.

Step 1: The $G^1$ Construction (1-bit stretching)

Why $G^1$ is a PRG.

We must show $(f(s), B(s)) \approx_p U_{k+1}$. By Definition 2.50 (GB), the hard-core property gives $(f(s), B(s)) \approx_p (f(s), U_1)$. Since $f$ is one-way, $f(s)$ already “looks random” in the relevant sense, so $(f(s), U_1) \approx_p (U_k, U_1) = U_{k+1}$. Chaining these two indistinguishabilities (using transitivity of $\approx_p$), the output of $G^1$ is pseudorandom.

Step 2: The $G^Q$ Construction (polynomial stretching)

A 1-bit extension is not useful on its own. We chain $G^1$ to produce polynomially many bits.

The Hybrid Argument: Proving $G^Q$ is a PRG

Error accumulation.

Each step introduces indistinguishability error $\mathrm{negl}(k)$. Over $Q(k) = \mathrm{poly}(k)$ steps, total error is $Q(k)\cdot\mathrm{negl}(k) = \mathrm{negl}(k)$ (a polynomial times a negligible function is negligible).

Why adjacent hybrids are indistinguishable.

$H_{i-1}$ and $H_i$ differ only in position $Q-i$: $H_{i-1}$ has $B(s_{Q-i})$ (hard-core bit), $H_i$ has a truly random $U_1$. Any distinguisher $D$ separating $H_{i-1}$ from $H_i$ yields an adversary breaking the hard-core predicate property of $B$ — contradicting OWF hardness. This is a reduction: $D \Rightarrow$ adversary against hard-core predicate $\Rightarrow$ OWF inversion.

Next-Bit Tests

There is a striking alternative characterization of PRGs: a string looks random if and only if no poly-time algorithm can predict its next bit from its previous bits.

Proof sketch ($\Rightarrow$).

If $G$ fails a statistical test $T$ — i.e., $T$ distinguishes $G(U_k)$ from $U_{\ell(k)}$ — then there exists a position $i$ such that $T$ distinguishes the distribution of the first $i+1$ bits of $G$ from the first $i+1$ bits of $U_{\ell(k)}$, even given that the first $i$ bits are the same. This directly yields a next-bit predictor.

Significance.

To prove $G$ is a PRG, it suffices to show next-bit unpredictability — a simpler, local condition — rather than fooling all possible statistical tests. This is why the hybrid argument works: each step only needs to argue about one bit at a time.

Two Intuitions for Randomness

Before the formal definition, it is worth grounding the notion of a PRG in two complementary intuitions about what it means for a bit string to “look” random.

Intuition 1: Passes all statistical tests.

A random sequence should be unbiased (equal numbers of 0s and 1s in the long run), should have every fixed-length pattern appear with the expected frequency, and should pass any other efficiently computable statistical test. A distinguisher in the formal definition is exactly such a test: it takes a string and says “random” or “not random.”

Intuition 2: Unpredictability.

Given any prefix of the sequence, a computationally bounded observer should not be able to guess the next bit with probability noticeably better than $\tfrac{1}{2}$. This is the next-bit test view.

Why restrict to polynomial-time distinguishers?

An exponential-time adversary given a string of length $\ell(n)$ could enumerate all $2^n$ seeds, compute $G(\text{seed})$ for each, and check whether the string is in the range of $G$. A random string of length $\ell(n)$ lands in the range with probability at most $2^n / 2^{\ell(n)}$, which is negligible when $\ell(n) > n$. So exponential time can distinguish; we restrict to polynomial time because that is the realistic adversary model.

(Remark: for other applications — such as derandomization and complexity theory — people study pseudorandomness against weaker classes, e.g. log-space bounded tests. The connection to outcome indistinguishability from the fairness portion of this course is not a coincidence: OI was framed knowing exactly this type of poly-time indistinguishability formula.)

Why PRGs Are Practically Useful

True randomness is expensive.

Generating truly random bits requires a physical entropy source (thermal noise, radioactive decay, quantum measurement, atmospheric noise, lava lamps, …). These sources are slow and require special hardware. In contrast, a PRG lets you spend a small amount on a short truly random seed and then stretch it into as many pseudorandom bits as needed.

Derandomization.

An important open question: does randomness help computation? We do not know whether $\mathrm{BPP} = \mathrm{P}$ (roughly, whether every efficient randomized algorithm has an efficient deterministic simulation). PRGs are a tool for minimizing the number of truly random bits required by an algorithm, with the hope of eventually eliminating them entirely. If strong enough PRGs exist, $\mathrm{BPP} = \mathrm{P}$ follows.

PRGs vs. OWFs.

A PRG $G$ must certainly be hard to invert (otherwise, given an output, one could recover the seed and distinguish pseudo from truly random). In fact, every PRG is a OWF. The converse is also true: OWFs exist if and only if PRGs exist (a deep result; in class we prove the easier direction via the GL theorem and the $G^Q$ construction).

Hybrid Argument: Proof Structure for Next-Bit $\Leftrightarrow$ PRG

The proof that next-bit unpredictability implies full pseudorandomness uses a hybrid argument — the second of the two fundamental techniques in cryptography (the first being reductions).

Construction for this proof.

Assume for contradiction that some PPTM $\mathcal{A}$ distinguishes $G(U_k)$ from $U_{\ell(n)}$ with non-negligible advantage $\ge 1/R(n)$. Define $\ell(n)+1$ hybrid distributions $D_0, D_1, \ldots, D_{\ell(n)}$: $$D_i \;=\; \underbrace{G(s)_1,\;\ldots,\; G(s)_{\ell(n)-i}}_{\text{first ℓ(n)−i\ell(n)-i bits: pseudorandom}},\; \underbrace{r_1,\;\ldots,\; r_i}_{\text{last $i$ bits: truly random}}.$$

• $D_0 = G(U_k)$ (all pseudorandom — the red distribution).

• $D_{\ell(n)} = U_{\ell(n)}$ (all truly random — the blue distribution).

Since $\mathcal{A}$ distinguishes $D_0$ from $D_{\ell(n)}$ with advantage $\ge 1/R(n)$, and there are $\ell(n)$ steps in the chain, by averaging there must exist some index $i^*$ such that $$\bigl|\Pr[\mathcal{A}(D_{i^*})=1] - \Pr[\mathcal{A}(D_{i^*+1})=1]\bigr| \;\ge\; \frac{1}{R(n)\cdot\ell(n)},$$ which is still non-negligible (since $\ell(n)$ is polynomial). But $D_{i^*}$ and $D_{i^*+1}$ differ only in whether position $\ell(n)-i^*$ is a pseudorandom bit $G(s)_j$ or a truly random bit $r$ — which yields a next-bit predictor for position $\ell(n)-i^*$, contradicting our assumption.

The Blum–Blum–Shub (BBS) Generator

The BBS generator is a concrete, number-theory-based PRG with provable security under the Quadratic Residuosity assumption.

Setup.

Let $p, q$ be large primes with $p \equiv q \equiv 3 \pmod{4}$; let $N = pq$ (Blum integer). Let $QR_N = \{x \in \mathbb{Z}_N^* : x = y^2 \bmod N \text{ for some } y\}$ be the quadratic residues. The squaring function $f(x) = x^2 \bmod N$ on $QR_N$ is a one-way permutation under the Quadratic Residuosity Assumption: deciding whether an element of $\mathbb{Z}_N^*$ is a quadratic residue is hard without knowing $p$ or $q$.

Hard-core predicate.

The least significant bit $B(x) = x \bmod 2$ is a hard-core predicate for $f(x)=x^2\bmod N$ under the Quadratic Residuosity Assumption.

Why BBS is notable.

• Concrete: security rests on a specific, well-studied number-theoretic problem (quadratic residuosity $\Leftrightarrow$ factoring).

• Backward secure: given all $Q$ output bits and $x_Q$, one cannot recover earlier states $x_0, x_1, \ldots$ (squaring is one-way).

• Historically important: one of the first provably secure PRG constructions.

Chapter Summary: The Implication Chain

Randomness, Weak/Strong OWFs, and the Goldreich–Levin Proof

Why Randomness Is Essential in Key Generation

Both in the shared-key setting (two parties share a secret key) and in the public-key setting (one party publishes a public key; any sender can encrypt; only the receiver can decrypt), keys must be generated using randomness.

Answer.

If key generation is deterministic, every party who runs the algorithm produces the same key. In the shared-key case, everyone would share the same secret; in the public-key case, everyone’s “private” key would be identical and publicly deducible. The requirement is unpredictability: different parties must produce different, independently unguessable keys. This mirrors the role of randomness in differential privacy — without it one could reverse-engineer which of two adjacent databases produced a given output.

Probabilistic Polynomial-Time Machines (PPTMs)

In cryptography, “easy” means computable by a PPTM, and “hard” means no PPTM succeeds (with non-negligible probability).

Negligible Functions

Examples.

$2^{-k}$, $2^{-\sqrt{k}}$, $k^{-\log k}$ are negligible. $k^{-5}$ is not negligible (it is $1/\mathrm{poly}$).

Key closure property.

This is essential for composition: if each sub-protocol leaks only negligibly, running polynomially many sub-protocols in sequence still leaks negligibly in total. This is far nicer than differential privacy, where privacy losses add linearly (or sub-linearly via advanced composition, but never remain negligible for free).

Formalizing “Hard to Invert”: Two Attempts

Straw-man definition (too weak)

A first attempt: $f$ is hard to invert if it is not the case that there exists a PPTM $M$ such that for all $y$, $f(M(y)) = y$. Formally: $$\forall M,\; \exists y \text{ such that } M(y) \notin f^{-1}(y) \text{ or } M \text{ runs in time } > |y|^c.$$ This is too weak. It would allow a PPTM to invert $f$ on all but a single string of each length $n$ (for infinitely many $n$), which is clearly not “hard.” The issue is that a finite set of exceptions can be hardcoded into the finite control of the machine, and the definition does not prevent inversion on a $1 - o(1)$ fraction of inputs.

Proper definition: negligible success probability

The adversary receives the security parameter $1^k$ (in unary, so algorithms run in time polynomial in $k$) to prevent trivially ruling out constant-time machines.

Weak versus Strong One-Way Functions

Comparison.

• Strong OWF: success probability is negligible (adversary almost never wins).

• Weak OWF: failure probability is non-negligible (adversary sometimes loses).

Note the asymmetry: “success probability $\le \mathrm{negl}$” is strictly stronger than “failure probability $\ge 1/\mathrm{poly}$”. (The latter allows, for example, success probability $1 - 1/n^{22}$, where the adversary is almost always right.)

The construction amplifies hardness by evaluating $f$ on many independent inputs; if the adversary could invert all of them simultaneously, it would need to be almost surely correct on every sub-instance.

One-Way Functions Do Not Hide All Input Bits

A common misconception: if $f$ is one-way, then all bits of $x$ are hidden given $f(x)$. This is false.

Example.

Let $H$ be a one-way function on $n$-bit inputs. Define $F(x \circ r) = H(x) \circ r$ where $x, r \in \{0,1\}^n$.

• $F$ is one-way: given $H(x) \circ r$, we cannot find $x$ (since $H$ is one-way).

• $F$ leaks $r$ entirely — exactly half the input bits are public.

This same construction ($f'(x \circ r) = f(x) \circ r$) appears in the Goldreich–Levin theorem. The point is: being one-way means some part of the input is hidden, but the definition does not require hiding every single bit.

Hardcore Predicates: Formal Definition

A predicate is a function $B : \{0,1\}^* \to \{0,1\}$ (output a single bit; “true” or “false” in logic).

Intuition.

• $B(x)$ is a single bit, so random guessing gives success probability exactly $1/2$.

• A hardcore predicate says: seeing $f(x)$ gives the adversary no useful hint for guessing $B(x)$; it can do at most negligibly better than chance.

• If you know $x$, computing $B(x)$ is easy. If you only see $f(x)$, it is as hard as flipping a coin.

The Goldreich–Levin Hardcore Bit

Why $r$ is included in the output.

To evaluate $B(x \circ r)$, one needs both $x$ (hidden) and $r$ (which must therefore be revealed). So $G$ outputs $r$ in the clear while hiding $x$ via the OWF $f$.

Geometric intuition.

$r$ specifies a random subset of bit positions of $x$; $B(x \circ r)$ is the XOR of those bits. Although $r$ is public, the parity of the chosen bits still hides $x$ completely.

Polynomial-Time Indistinguishability (Revisited)

Recall (Chapter 14):

Proof that the GL Bit Is Hardcore

We prove: $$\bigl\{(G(s),\; B(s))\bigr\} \;\approx_p\; \bigl\{(G(s),\; 1 - B(s))\bigr\},$$ where $s = x \circ r$ is drawn uniformly from $\{0,1\}^{2k}$.

Unpacking: the red distribution is $G(s)$ concatenated with the hardcore bit $B(s)$; the blue distribution is $G(s)$ concatenated with $\overline{B(s)} = 1 - B(s)$. Both draw $s = x \circ r$ with $x, r \leftarrow \{0,1\}^k$ independently.

Proof by contradiction

Assume

there exists a PPTM $\mathcal{A}$ and polynomial $R$ such that for infinitely many $n$: $$p_n - q_n \;\ge\; \frac{1}{R(n)},$$ where $$p_n = \Pr_{s \leftarrow \{0,1\}^{2k}}[\mathcal{A}(G(s) \circ B(s)) = 1], \qquad q_n = \Pr_{s \leftarrow \{0,1\}^{2k}}[\mathcal{A}(G(s) \circ \overline{B(s)}) = 1].$$ (We handle the absolute value at the end; WLOG assume the red probability exceeds the blue probability for infinitely many $n$.)

Construction.

Build a PPTM $\mathcal{B}$ that, given $G(s) = f(x) \circ r$, guesses $B(s)$ with probability non-negligibly greater than $1/2$:

1. Receive $G(s)$ (i.e., $f(x) \circ r$).

2. Sample a fresh uniform bit $Z \in \{0,1\}$.

3. Run $\mathcal{A}$ on $G(s) \circ Z$.

4. If $\mathcal{A}$ outputs 1, output $Z$ (guess $B(s) = Z$).

5. If $\mathcal{A}$ outputs 0, output $1 - Z$ (guess $B(s) = 1-Z$).

Analysis.

$$\Pr[\mathcal{B} \text{ correct}] \;=\; \Pr[Z = B(s)] \cdot \Pr[\mathcal{A}(G(s)\circ Z)=1 \mid Z=B(s)] + \Pr[Z \ne B(s)] \cdot \Pr[\mathcal{A}(G(s)\circ Z)=0 \mid Z\ne B(s)].$$ Since $Z$ is an independent uniform bit, $\Pr[Z = B(s)] = 1/2$. The conditional on $Z = B(s)$ has the adversary $\mathcal{A}$ receiving a sample from the red distribution, giving success probability $p_n$. The conditional on $Z \ne B(s)$ has $\mathcal{A}$ receiving the blue distribution; when $\mathcal{A}$ outputs 0, we correctly flip, giving probability $1 - q_n$. Therefore: $$\Pr[\mathcal{B} \text{ correct}] \;=\; \frac{1}{2}\,p_n \;+\; \frac{1}{2}(1 - q_n) \;=\; \frac{1}{2} + \frac{p_n - q_n}{2} \;\ge\; \frac{1}{2} + \frac{1}{2R(n)}.$$

This is non-negligibly better than $1/2$, contradicting the hardcore predicate property of $B$.

Handling the absolute value.

If $q_n > p_n$ for infinitely many $n$ instead, define $\mathcal{B}$ to flip the output of $\mathcal{A}$ (run $1 - \mathcal{A}(\cdot)$ as the distinguisher); this still runs in polynomial time and achieves the same advantage. At least one of the two cases must occur infinitely often, so the argument goes through.

Remark on P vs. NP.

All the hardness assumptions in this chapter (OWF existence, indistinguishability) are unproven. If $\mathrm{P} = \mathrm{NP}$, polynomial-time algorithms exist for inverting any OWF, and modern public-key cryptography collapses. The probability of $\mathrm{P} = \mathrm{NP}$ is unknown.

Candidate One-Way Functions Revisited

Subset Sum Modulo $M$

Parameters: $n$ elements $a_1, \ldots, a_n \in \mathbb{Z}_M$, target $t \in \mathbb{Z}_M$. The function $f_a(s) = \sum_i a_i s_i \bmod M$ maps $s \in \{0,1\}^n$ to $\mathbb{Z}_M$. Inverting it (finding a subset summing to $t$) is a modular version of the knapsack problem. Hardness depends on the density $\delta = n / \log M$:

• $\delta < 1$ or $\delta > n / \log n$: efficient algorithms exist.

• $\delta = \Theta(1)$: believed hard; related to lattice-based cryptography.

The solution need not be unique; one-wayness only requires that some preimage is hard to find.

Discrete Logarithm

Let $p$ be a large prime and $g$ a generator of $\mathbb{Z}_p^*$, i.e., the powers $g^1, g^2, \ldots, g^{p-1}$ enumerate all elements of $\{1, \ldots, p-1\}$.

The forward direction (exponentiation: given $x$, compute $y = g^x \bmod p$) is easy via fast exponentiation. The inverse (given $y$, find $x$) is the discrete log problem, which is conjectured hard. The famous ElGamal cryptosystem is based on this hardness.

Post-Quantum Cryptography

Both integer factoring and discrete log can be solved in polynomial time on a quantum computer via Shor’s algorithm (1994). If large-scale quantum computers are built, these cryptosystems are broken.

Post-quantum cryptography refers to schemes whose security does not rely on the hardness of factoring or discrete log. The leading candidate is lattice-based cryptography, where hardness is based on problems like Learning With Errors (LWE). Interestingly, lattice algorithms (due to Lenstra–Lenstra–Lovász) were originally used to break knapsack cryptosystems; Regev and others later showed lattice problems could also be used to build secure systems.

GL Proof: Refined Case Analysis

The following is a more explicit version of the argument from §15.10, using conditional probabilities to make each case transparent.

Setup.

As before, $\mathcal{B}$ receives $G(s) = f(x) \circ r$, samples a fresh uniform bit $Z \in \{0,1\}$, and runs $\mathcal{A}$ on $G(s) \circ Z$.

Case 1: $\mathcal{A}$ outputs 1.

$\mathcal{B}$ guesses $B(s) = Z$. This is correct iff $Z = B(s)$, which happens with probability $\tfrac{1}{2}$ (since $Z$ is chosen uniformly, independent of $s$). Conditioned on $Z = B(s)$, we are feeding $\mathcal{A}$ from the red distribution, so $$\Pr[\mathcal{A}(G(s)\circ Z)=1 \mid Z=B(s)] \;=\; p_n.$$ Contribution to $\Pr[\mathcal{B}\text{ correct}]$: $$\Pr[Z=B(s)] \cdot \Pr[\mathcal{A}(G(s)\circ Z)=1 \mid Z=B(s)] \;=\; \tfrac{1}{2}\,p_n.$$

Case 2: $\mathcal{A}$ outputs 0.

$\mathcal{B}$ guesses $B(s) = 1-Z$. This is correct iff $Z = 1-B(s)$ (i.e. $Z \ne B(s)$), which also happens with probability $\tfrac{1}{2}$. Conditioned on $Z = 1-B(s)$, we are feeding $\mathcal{A}$ from the blue distribution, so $$\Pr[\mathcal{A}(G(s)\circ Z)=0 \mid Z=1-B(s)] \;=\; 1-q_n.$$ Contribution to $\Pr[\mathcal{B}\text{ correct}]$: $$\Pr[Z=1-B(s)] \cdot \Pr[\mathcal{A}(G(s)\circ Z)=0 \mid Z=1-B(s)] \;=\; \tfrac{1}{2}(1-q_n).$$

Total.

By the law of total probability: $$\Pr[\mathcal{B}\text{ correct}] \;=\; \tfrac{1}{2}p_n + \tfrac{1}{2}(1-q_n) \;=\; \tfrac{1}{2} + \tfrac{p_n - q_n}{2} \;\ge\; \tfrac{1}{2} + \frac{1}{2R(n)},$$ which is non-negligibly better than $\tfrac{1}{2}$, contradicting the hardcore property.

Corollary: Hardcore Bit Is Indistinguishable from a Random Bit

The previous theorem showed: $$\bigl\{G(s) \circ B(s)\bigr\} \;\approx_p\; \bigl\{G(s) \circ (1-B(s))\bigr\}.$$ A useful corollary strengthens this: the hardcore bit is indistinguishable from a uniformly random bit.

Encryption and Semantic Security

Private-Key Encryption: Syntax

Perfect Secrecy (Shannon)

The One-Time Pad (OTP) achieves perfect secrecy: $c = m \oplus k$ for a uniformly random key $k$ of the same length as $m$.

Shannon’s impossibility.

Any perfectly secret scheme requires $|K|\ge|M|$ — the key must be at least as long as the message. This makes perfect secrecy impractical, motivating computational security.

Semantic Security

IND-CPA Security

Conceptual importance.

Semantic security is the “right” intuitive definition (nothing is leaked), while IND-CPA is the “right” technical definition (clean game, easy to use in reductions). Their equivalence means we can use whichever is convenient.

Stream Ciphers from PRGs

Proof sketch.

If $\mathcal{A}$ distinguishes $\mathrm{Enc}_s(m_0)$ from $\mathrm{Enc}_s(m_1)$, it distinguishes $G(s)\oplus m_0$ from $G(s)\oplus m_1$. Since XOR with a fixed message is a bijection, this implies distinguishing $G(s)$ from $U_{\ell(k)}$ — breaking the PRG.

Caution: single-use.

If the same seed $s$ is reused to encrypt two messages $m, m'$, the adversary sees $G(s)\oplus m$ and $G(s)\oplus m'$ and can XOR them to recover $m\oplus m'$, completely breaking secrecy.

Public-Key Encryption

Private-key encryption requires the sender and receiver to share a secret key in advance. This is the key distribution problem: how do two parties who have never met establish a shared secret over a public channel?

Public-key encryption (PKE) resolves this by having each party hold a key pair: a public key they broadcast freely and a private key they keep secret. Anyone can encrypt to you using your public key; only you can decrypt using your private key.

IND-CPA for PKE.

The definition is the same as for private-key IND-CPA, except the adversary is given the public key $\mathit{pk}$ at the start. This is actually a stronger requirement: since the adversary has $\mathit{pk}$, they can encrypt arbitrary messages themselves, so the scheme must remain secure even against adversaries with full encryption access.

Why encryption must be randomized.

In a public-key cryptosystem, if encryption were deterministic, any observer could encrypt both messages themselves (the public key is public) and compare against the ciphertext, immediately learning which message was encrypted. A secure scheme must have multiple possible encryptions of each message—i.e., encryption must sample from a distribution. A corollary: if encryptions of $0$ are computationally indistinguishable from encryptions of $1$, then by the same hybrid argument used in the GL hardcore bit proof, encryptions of any fixed bit $b$ are also indistinguishable from encryptions of a uniformly random bit.

Quadratic Residues and the QR Hardness Assumption

The Goldwasser–Micali scheme (below) builds on the computational hardness of distinguishing squares from non-squares modulo a composite.

The Jacobi symbol.

For $N = pq$, the Jacobi symbol $J_N(x) = \left(\frac{x}{p}\right)\left(\frac{x}{q}\right)$ (product of Legendre symbols) can be computed without knowing $p$ and $q$.

• If $J_N(x) = -1$: $x$ is definitely a QNR.

• If $J_N(x) = +1$: $x$ is either a QR or a QNR with “fake” Jacobi symbol (called a pseudo-square).

For $N = pq$ with $p \equiv q \equiv 3 \pmod{4}$, exactly half of the elements with $J_N(x)=1$ are genuine QRs and half are pseudo-squares.

Key multiplicative structure.

QR $\times$ QR $=$ QR; QR $\times$ QNR $=$ QNR; QNR $\times$ QNR $=$ QR.
Multiplication in $\mathbb{Z}_N^*$ corresponds to XOR of the “squareness bit.”

Goldwasser–Micali Probabilistic Encryption

Why it is probabilistic.

Different random choices of $r$ produce different ciphertexts for the same message. This is necessary: a deterministic PKE scheme is never IND-CPA secure (the adversary simply encrypts both challenge messages and compares).

Homomorphic property.

If $c_1 = \mathrm{Enc}(b_1)$ and $c_2 = \mathrm{Enc}(b_2)$ (with independent randomness), then $$c_1 \cdot c_2 \bmod N \;=\; \mathrm{Enc}(b_1 \oplus b_2),$$ since $r_1^2 y^{b_1} \cdot r_2^2 y^{b_2} = (r_1 r_2)^2 y^{b_1 + b_2}$ and the QR/QNR parity of $y^{b_1+b_2}$ corresponds to $b_1 \oplus b_2$. GM is thus a homomorphic encryption scheme with respect to XOR.

Chosen-Ciphertext Attacks

The IND-CPA model gives the adversary access to an encryption oracle. A stronger model gives access to a decryption oracle as well.

Why CCA-post?

Giving the adversary a decryption oracle even after seeing the challenge may seem like overkill. The motivation is that in practice we rarely know exactly what capabilities an attacker has. By proving security against the strongest plausible adversary—one who can decrypt anything except the exact ciphertext they are trying to break—we get a guarantee that holds regardless of how the attacker acquires auxiliary decryption power.

Implication chain.

$\text{CCA-post} \Rightarrow \text{CCA-pre} \Rightarrow \text{IND-CPA}$. Each implication is strict: there exist schemes secure under the weaker model but broken by the stronger.

Malleability and Non-Malleability

Malleability is a problem because in a CCA setting the adversary can: (1) receive challenge ciphertext $\alpha$ encrypting unknown $m$, (2) produce a related $\beta$ via the malleability attack, (3) submit $\beta \ne \alpha$ to the decryption oracle, (4) learn $\mathrm{Dec}(\beta)$, which reveals information about $m$.

Non-malleability is a stronger guarantee than semantic security: any function $f(m)$ that the adversary could learn under a semantic-security break can be recast as a relation $R(m, m') = \mathbf{1}[f(m) = f(m')]$, so non-malleability implies semantic security. The converse fails: a semantically secure scheme can be malleable (as GM demonstrates below).

The Six Notions of Security

Combining adversary power with break type yields six standard notions:

These are ordered by strength: NM-CCA2 is the strongest and IND-CPA the weakest. For most practical protocols (e.g., TLS), IND-CCA2 security is the target.

The GM Scheme is Malleable

Goldwasser–Micali is IND-CPA secure (Theorem [th:gm-sec]), but it is malleable under CCA, because the multiplicative structure of $\mathbb{Z}_N^*$ is public.

Attack: produce another encryption of the same bit.

Given challenge $\alpha = r^2 \cdot y^b \bmod N$ (an encryption of bit $b$): choose a fresh random $s \in \mathbb{Z}_N^*$ and set $\beta = s^2 \cdot \alpha \bmod N$. Since $s^2$ is a QR, multiplying by it preserves quadratic residuosity: $$\beta = (sr)^2 \cdot y^b \bmod N,$$ which is a fresh, independently distributed encryption of $b$. The adversary can submit $\beta \ne \alpha$ to the decryption oracle and learns $b$.

Attack: produce an encryption of the flipped bit.

Set $\beta = (-1) \cdot \alpha \bmod N$. Since $-1$ is a pseudo-square (QNR with Jacobi symbol $+1$) by the choice of $p \equiv q \equiv 3 \pmod{4}$, multiplying flips QR $\leftrightarrow$ QNR: $$\beta \text{ is an encryption of } 1-b.$$ Decrypting $\beta$ via the CCA oracle reveals $1-b$, hence $b$.

Zero Knowledge

From Classical Proofs to Interactive Proofs

Classical proofs.

A classical mathematical proof is a checkable sequence of statements: fix axioms and rules of inference, and every line is either an axiom or the result of applying a deduction rule to earlier lines. This is the setting of Euclidean geometry, Peano arithmetic, and so on. (By Gödel’s incompleteness theorem, no such system can be simultaneously complete and consistent — but this will not concern us here.)

NP and polynomial witnesses.

The complexity class NP formalizes classical proofs: a language $L$ is in NP if membership has a polynomial-length, efficiently checkable proof. Formally, $x \in L$ iff $\exists\, w$ with $|w| = \mathrm{poly}(|x|)$ and $R(x, w) = 1$ (where $R$ is polynomial-time).

• 3-SAT: $w$ is a satisfying variable assignment; checking is linear time.

• 3-coloring: $w$ is a coloring; checking (no edge monochromatic) is linear.

• Graph isomorphism: $w$ is the map $\varphi: V(G)\to V(H)$; checking is easy.

• Hamiltonicity: $w$ is the Hamiltonian cycle; checking is linear.

The witness $w$ may not be unique: many satisfying assignments may exist for the same formula.

The limitation: co-NP.

Proving that a statement is false — a formula is unsatisfiable, two graphs are non-isomorphic, a graph has no Hamiltonian cycle — amounts to a “for all” quantifier. There is no known short proof of such statements (that would imply P = NP or NP = co-NP). Intuitively, it is easier to demonstrate a satisfying assignment than to argue that none exists.

Interactive proofs.

In an interactive proof system, the verifier is not passive. Instead of receiving a proof and checking it line by line, the verifier asks questions. This is particularly powerful for statements outside NP.

By repeating the protocol $k$ times and accepting only if all rounds accept, completeness can be boosted to $1 - 2^{-\Omega(k)}$ and soundness error reduced to $2^{-\Omega(k)}$.

Graph Non-Isomorphism: An Interactive Proof

Graph isomorphism (GI) is in NP: prove $G \cong H$ by exhibiting the isomorphism. But graph non-isomorphism (GNI) is not known to be in NP — there is no known short proof that two graphs are not isomorphic. Nevertheless, a powerful prover can convince a verifier interactively.

Protocol (one round).

1. $V$ picks $X \in \{G, H\}$ uniformly at random, computes a uniformly random isomorphic copy $Y = \varphi(X)$, and sends $Y$ to $P$.

2. $P$ identifies which of $G$ or $H$ the graph $Y$ was derived from, and sends its guess $\hat{b}$ to $V$.

3. $V$ accepts iff $\hat{b}$ equals its original choice.

Repeat $k$ times independently.

Analysis.

• Completeness. If $G \not\cong H$, a computationally powerful $P$ can always determine which graph $Y$ came from (since $\varphi(G)$ and $\varphi(H)$ are non-isomorphic). Accepts with probability 1.

• Soundness. If $G \cong H$, then $\varphi(G)$ and $\varphi(H)$ have the same distribution. Any prover guesses correctly with probability at most $\frac{1}{2}$ per round; after $k$ rounds, a cheating prover wins with probability at most $2^{-k}$.

Zero-Knowledge Proofs: Definition and Motivation

In practice, the prover often holds a secret witness — a satisfying assignment, a graph coloring, a Hamiltonian cycle, a private key — and wants to convince the verifier that the statement is true without revealing the witness.

Why keep the witness secret?

• A satisfying assignment for a hard formula can serve as a password. The account holder wants to prove they know it without transmitting it.

• A graph coloring or Hamiltonian cycle may contain proprietary information.

• In lattice-based and other cryptographic settings, the witness is the private key; revealing it would break the system entirely.

Interpretation.

The simulator has no access to the prover or the witness $w$, yet it produces transcripts computationally indistinguishable from real interactions. Since the verifier can generate equally good transcripts on its own, real transcripts cannot be leaking anything about $w$. This is the exact analogue of semantic security: seeing the ciphertext (or the transcript) gives the adversary no advantage.

The Lady Tasting Tea

The statistician Muriel Bristol claimed to distinguish tea poured milk-first from tea-first. In a blind test with 8 cups, she identified all 8 correctly — an event with probability $2^{-8}$ if guessing at random. The test proves she has the ability, but reveals nothing about how: no information about her taste physiology, sensitivity, or method is ever disclosed.

This is an informal zero-knowledge proof of capability: the verifier is convinced of the fact, but learns nothing about the witness behind it.

Commitment Schemes

Information-theoretic vs. computational.

Each of hiding and binding can hold either information-theoretically (no algorithm, regardless of power, can break it) or computationally (no PPT algorithm can break it under a hardness assumption).

Example (QR-based). Commit to bit $b$ by sending a random QR (if $b=0$) or QNR with $J_N = 1$ (if $b=1$) modulo $N$. Binding is information-theoretic (a number is or is not a square; this cannot be changed). Hiding is computational: under the QR assumption, QRs and pseudo-squares are indistinguishable in poly time.

Interactive Proof for Quadratic Non-Residuosity

Both $P$ and $V$ know $X \in \mathbb{Z}_N^*$ with $J_N(X) = 1$. The prover claims $X \in \mathrm{QNR}_N$ and knows the factorization of $N$.

Protocol (one round).

1. $V$ picks $S \leftarrow \mathbb{Z}_N^*$ and $b \leftarrow \{0,1\}$ uniformly. Sends: $$Y = \begin{cases} S^2 \bmod N & b = 0 \\ S^2 X \bmod N & b = 1 \end{cases}$$

2. $P$ identifies $b$ (using the factorization to test whether $Y \in \mathrm{QR}_N$) and sends $\hat{b}$ to $V$.

3. $V$ accepts iff $\hat{b} = b$.

Analysis.

• Completeness. If $X$ is a QNR: $S^2$ is a QR; $S^2 X$ is a QNR. A powerful $P$ always identifies $b$ correctly.

• Soundness. If $X$ is a QR: $S^2$ and $S^2 X$ are both QRs, identically distributed. No prover can distinguish them; cheating succeeds with probability $\frac{1}{2}$ per round. After $k$ rounds: $2^{-k}$.

Zero-Knowledge Proof for Quadratic Residuosity

Now $P$ claims $X \in \mathrm{QR}_N$ and knows $s$ with $s^2 \equiv X \pmod{N}$. The goal is to prove this without revealing $s$.

Protocol (one round).

1. $P$ picks $T \leftarrow \mathbb{Z}_N^*$ uniformly. Sends $\alpha = T^2 X \bmod N$.

2. $V$ picks $b \leftarrow \{0,1\}$ and sends $b$ to $P$.

3. $P$ sends: $$Y = \begin{cases} TS \bmod N & b = 0 \\ T \bmod N & b = 1 \end{cases}$$

4. $V$ checks: $$\begin{cases} Y^2 \equiv \alpha \pmod{N} & b = 0 \\ Y^2 X \equiv \alpha \pmod{N} & b = 1 \end{cases}$$

Correctness.

• $b=0$: $Y = TS$, so $Y^2 = T^2 S^2 = T^2 X = \alpha$.

• $b=1$: $Y = T$, so $Y^2 X = T^2 X = \alpha$.

Zero knowledge via the rewind simulator.

The real transcript distribution is:

• $b=0$: $(Y^2,\; 0,\; Y)$ for uniform $Y = TS$ (which is uniform since $T$ is uniform).

• $b=1$: $(T^2 X,\; 1,\; T)$ for uniform $T$.

The secret $s$ is always multiplied by a fresh uniform $T$; the verifier never sees $s$ directly.

The simulator proceeds:

1. Flip a coin to guess $\hat{b} \in \{0,1\}$.

2. Pick uniform $Y' \in \mathbb{Z}_N^*$.

3. If $\hat{b}=0$: set $\alpha' = (Y')^2$; prepare to send $Y'$.
   If $\hat{b}=1$: set $\alpha' = (Y')^2 X$; prepare to send $Y'$.

4. Send $\alpha'$ to $V^*$ and receive $b_{\mathrm{actual}}$.

5. If $b_{\mathrm{actual}} = \hat{b}$: output the transcript $(\alpha', b_{\mathrm{actual}}, Y')$.

6. Otherwise: rewind $V^*$ to its state before step 4 and retry.

In expectation, only 2 attempts suffice per round. In either case, the produced transcript is identically distributed to a real interaction: $b=0$ gives $(Y^2, 0, Y)$ for uniform $Y$; $b=1$ gives $(Y^2 X, 1, Y)$ for uniform $Y$.

Zero-Knowledge Proof of Hamiltonicity

A graph $G = (V, E)$ is Hamiltonian if it contains a cycle visiting every vertex exactly once. Hamiltonicity is NP-complete, so the Hamiltonian cycle $C$ is the witness. The following protocol (from Barak’s notes, with the commitment scheme abstracted) convinces the verifier that $G$ is Hamiltonian without revealing $C$.

Protocol (one round)

1. Commit. $P$ picks a uniformly random permutation $\pi$ of $V(G)$ and forms $H = \pi(G)$ (same edges, vertices relabeled by $\pi$). $P$ sends a commitment to each entry of the $|V|\times|V|$ adjacency matrix of $H$, one bit per entry.

2. Challenge. $V$ picks $b \leftarrow \{0,1\}$ and sends $b$ to $P$.

3. Response.

   • $b=0$: $P$ opens all commitments and reveals $\pi$. $V$ checks that $H$ is a valid permutation of $G$.

   • $b=1$: $P$ opens only the entries of the adjacency matrix of $H$ corresponding to the permuted cycle $\pi(C)$ (i.e., the $n$ edges $\pi(c_1)\pi(c_2),\;\pi(c_2)\pi(c_3),\;\ldots$). $V$ checks these entries form a Hamiltonian cycle in $H$.

Repeat $k$ times with fresh randomness from $P$ each round.

Correctness and Soundness

• Completeness. An honest $P$ with cycle $C$ passes both checks.

• Soundness. If $G$ has no Hamiltonian cycle, no $P^*$ can simultaneously prepare commitments that pass both checks. Passing $b=0$ requires a valid permutation of $G$ (which contains no Hamiltonian cycle); passing $b=1$ requires opening a Hamiltonian cycle — which does not exist. A cheating prover passes at most one check per round: soundness error $\le \frac{1}{2}$ per round, $2^{-k}$ after $k$ rounds.

Zero Knowledge: The Rewind Simulator

Zero-Knowledge Proof for 3-Colorability

The canonical theoretical example: every NP language has a zero-knowledge proof.

Protocol.

Given graph $G = (V, E)$ and a 3-coloring $\chi$ known to the prover:

1. $P$ picks a uniformly random permutation $\pi$ of $\{1,2,3\}$, applies it to get coloring $\pi\circ\chi$, and commits to each vertex’s color: sends $\{\mathrm{Commit}(\pi(\chi(v)))\}_{v\in V}$.

2. $V$ challenges with a random edge $(u,w) \in E$.

3. $P$ opens the commitments for $u$ and $w$, revealing $\pi(\chi(u))$ and $\pi(\chi(w))$.

4. $V$ accepts iff the two revealed colors are distinct.

Repeat $|E|\cdot k$ times.

Analysis.

• Completeness. A valid coloring always passes (adjacent vertices have distinct colors; $\pi$ preserves distinctness).

• Soundness. If $G$ is not 3-colorable, some edge must be monochromatic; the verifier catches it with probability $\ge 1/|E|$ per round. After $|E|\cdot k$ rounds, soundness error is $\le (1-1/|E|)^{|E|k} \le e^{-k}$.

• Zero knowledge. The simulator (without knowing $\chi$) generates a random pair of distinct colors and fake commitments for the challenged edge, producing an identically distributed transcript. The random permutation $\pi$ ensures the revealed colors look fresh and uniform.

This follows from 3-colorability having a ZK proof, combined with the NP-completeness of 3-coloring (via Cook–Levin and reduction): any NP language reduces to 3-coloring in polynomial time.

Connection to commitment schemes.

The ZK protocols above rely on commitments: binding ensures soundness (the prover cannot change the committed coloring or permutation after the challenge); hiding ensures zero knowledge (unopened commitments reveal nothing). Commitment schemes can be constructed from one-way functions.

Post-Quantum Cryptography: Lattice-Based Schemes

The cryptographic constructions discussed in this course — factoring-based (Goldwasser–Micali) and discrete-log-based systems — are not post-quantum secure. Shor’s algorithm solves both integer factorization and discrete logarithm in polynomial time on a quantum computer.

Lattice problems offer a post-quantum alternative. Ajtai (1996) introduced lattice problems with a remarkable worst-case to average-case reduction: solving random instances efficiently would imply solving the hardest instances efficiently. This gives a provable guarantee that factoring lacks: random instances are provably as hard as the worst case. Moreover, no efficient quantum algorithm for lattice problems is known.

ZK-SNARKs: Succinct Non-Interactive Zero Knowledge

Motivation: Privacy in Distributed Systems

Bitcoin introduced a pseudonymous transaction model: every user operates under a public key rather than a name. But pseudonymity is not anonymity. Because the blockchain is a public ledger, an observer can link transactions to the same pseudonym, and then link pseudonyms to identities via auxiliary information — precisely the linkage-attack strategy that defeated Netflix’s “anonymous” ratings (see Chapter 11).

ZK-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) were developed, in part, to provide genuinely private transactions: a user proves they are authorized to spend funds without revealing which funds, in which wallet, at what time.

The SNARK Acronym Unpacked

Zero-Knowledge (ZK):

the verifier learns nothing beyond the truth of the statement (the simulator paradigm of Goldwasser–Micali–Rackoff).

Succinct (S):

the proof has size $\mathrm{poly}\log N$, where $N$ is the length of the witness, rather than $\mathrm{poly}(N)$.

Non-Interactive (NI):

no back-and-forth between prover and verifier; a single message suffices (achieved via the Fiat–Shamir heuristic).

Argument (A):

soundness holds only against computationally bounded provers (under cryptographic assumptions), not information-theoretically.

of Knowledge (K):

the prover does not merely show a witness exists; the protocol extracts the witness from any successful prover, proving that the prover genuinely “knows” it.

Construction: PCP + Merkle Tree + Fiat–Shamir

The construction proceeds in three steps:

Step 1: Probabilistically Checkable Proof (PCP).

By the PCP theorem, any NP witness $w$ of length $N$ can be encoded into a probabilistically checkable proof $\pi$ of length $\mathrm{poly}(N)$ such that a verifier who reads only $\mathrm{poly}\log N$ randomly chosen positions of $\pi$ can check validity with high probability. This is remarkable: the verifier does not read the whole proof.

Step 2: Merkle Tree for Commitment and Selective Opening.

Naively, the prover would send all of $\pi$ to the verifier, which is $\mathrm{poly}(N)$ bits. Instead:

1. The prover commits to $\pi$ by building a Merkle tree over the leaves $\pi_1,\ldots,\pi_{\mathrm{poly}(N)}$ and sending only the root hash $h = \mathrm{MerkleRoot}(\pi)$.

2. The verifier requests $\mathrm{poly}\log N$ leaf positions.

3. The prover opens each requested leaf with an authentication path (a sequence of sibling hashes of length $O(\log N)$).

Each opening is itself a proof of membership in the Merkle tree, which can be verified against the root $h$ in $O(\log N)$ hash evaluations. The prover then gives a zero-knowledge interactive proof for each opening, ensuring no information about the unopened leaves is revealed.

Step 3: Fiat–Shamir Heuristic.

The protocol so far is interactive (the verifier sends random challenges). The Fiat–Shamir heuristic replaces every verifier message with the output of a cryptographic hash function applied to the transcript so far: $$c_i \;=\; H(\text{transcript up to round }i).$$ This makes the protocol non-interactive: the prover computes the “challenges” herself using the hash, then sends the entire transcript in one message. Security holds in the random oracle model, where $H$ is modeled as a truly random function.

Why this is remarkable.

For NP statements with witnesses of length, say, $N = 10^9$ bits, a classical interactive ZK proof would require the verifier to process $\mathrm{poly}(10^9)$ data. A ZK-SNARK reduces this to $\mathrm{poly}\log(10^9) \approx 900$ bits. The verifier’s work is essentially independent of the witness size.

Proofs of Work: Origins and Design

The Original Problem: Spam Deterrence

Proofs of work were invented in 1992 by Dwork and Naor for a purpose entirely unrelated to cryptocurrency: combating email spam.

The core observation: sending an email is essentially free for the sender but costly (in attention) for the recipient. If sending a single email required even a small amount of computation — say, 10 seconds of CPU time — then legitimate users would barely notice, but a spammer sending millions of emails would face an insurmountable computational burden.

Moderately Hard Functions

The technical object is a moderately hard function: a function $f$ such that

• Computing $f(x)$ requires a specified amount of work (not too easy, not too hard).

• Verifying $f(x) = y$ is fast (much cheaper than computing $f$).

• The work is per-message, per-recipient: the solution to one puzzle cannot be reused for a different message or a different recipient. This non-reusability is essential — without it, a spammer could solve one puzzle and send to a million recipients.

The Puzzle Structure

In Dwork and Naor’s scheme, the puzzle for a message $m$ sent to recipient $r$ is: $$\text{find } x \text{ such that } H(\underbrace{m, r,}_{\text{binding}} x) < T,$$ where $H$ is a hash function and $T$ is a difficulty threshold. The message $m$ and recipient $r$ are bound into the puzzle, preventing reuse.

Trapdoor for legitimate bulk mailers.

Dwork and Naor’s original scheme included a trapdoor: a trusted authority could issue “puzzle masters” who can solve puzzles in $O(1)$ time using a private key. This allowed legitimate bulk mailers (e.g., newsletters) to send efficiently while still imposing cost on unauthorized spammers.

Bitcoin Diverges from the Original Design

Bitcoin’s proof-of-work mechanism shares the high-level structure (find a nonce $x$ such that $H(\text{block header}, x) < T$) but differs in two important ways:

1. No trapdoor. Bitcoin’s hash-based PoW has no shortcut: every miner, including the protocol’s creators, must perform full brute-force search. This is a deliberate design choice for decentralization.

2. Environmental cost. Without a trapdoor, all computation is wasted work. Bitcoin’s global mining network consumes electricity comparable to small countries. The Dwork–Naor design explicitly avoids this: legitimate senders with the trapdoor pay negligible cost; only spammers pay.

Implementation: Microsoft Outlook

Microsoft implemented a proof-of-work filter in Outlook: outgoing emails would include a small computational certificate, computed silently in the background. Mail servers could weight incoming mail higher or lower based on whether a valid certificate was present. This is a direct descendant of the Dwork–Naor design.

Paper Readings

Goldwasser, Micali, Rackoff (1989) — The Knowledge Complexity of Interactive Proof Systems.

Introduces interactive proof systems and defines zero knowledge via the simulator paradigm: a proof is zero-knowledge if a polynomial-time simulator, without access to the prover or the witness, can produce transcripts computationally indistinguishable from real interactions. The paper proves that graph isomorphism has a zero-knowledge proof and introduces the notion of “knowledge complexity” to quantify how much information a proof leaks. The simulator paradigm established here is now the standard framework for defining security in virtually every area of modern cryptography, from encryption to multi-party computation.

Kilian (1992) — A Note on Efficient Zero-Knowledge Proofs and Arguments.

Combines probabilistically checkable proofs, Merkle tree commitments, and zero-knowledge proofs of knowledge into the first succinct argument system: the prover Merkle-commits to a PCP encoding of the witness, the verifier queries a polylogarithmic number of positions, and the prover responds with a ZK proof that the PCP verifier would accept the committed values — without ever revealing the PCP itself. Communication is $\mathrm{polylog}(|T|)$ rather than polynomial, a dramatic improvement over raw ZK proofs. This construction is the conceptual ancestor of SNARKs, STARKs, and the shielded transaction system of Zcash discussed in Chapter 18.

Bridging Fairness and Privacy

Bitcoin and Blockchain: A Case Study in Distributed Trust

The Double-Spend Problem

Digital money faces a fundamental problem that physical cash does not: a digital file representing a coin can be copied. Alice could send Bob a digital coin and simultaneously send Carol the same coin. Digital signatures solve part of the problem — they prove Alice authorized a transaction — but they do not prevent Alice from signing two conflicting transactions.

Prior attempts.

Pre-Bitcoin digital currency schemes (e-cash, DigiCash) relied on a trusted central server to maintain a “spent coins” list. This is exactly what a bank does. Nakamoto’s insight was to eliminate the trusted central party entirely.

Blockchain as a Distributed Timestamp Server

A blockchain is an append-only linked list of blocks, where each block

1. Contains a batch of transactions,

2. Contains the cryptographic hash of the previous block (creating a chain: modifying any past block changes all subsequent hashes), and

3. Contains a proof-of-work certificate.

Because blocks are linked by hashes, an adversary who wants to alter a historical transaction must recompute all subsequent blocks’ proofs of work — an infeasible task if the adversary controls less than half the network’s compute power.

Proof of Work as Byzantine Fault Tolerance

The core mechanism is the proof of work (see Section 17.12 for the 1992 origins). Miners compete to extend the chain: the first to find a valid nonce broadcasts the new block and receives the block reward. By the longest-chain rule (Nakamoto consensus), nodes accept the chain with the most cumulative work as the canonical history.

Why this prevents double-spend.

Suppose Alice broadcasts conflicting transactions $T_1$ (to Bob) and $T_2$ (to Carol). Both transactions propagate through the network, but only one can appear in the canonical chain. Nakamoto consensus resolves the conflict: whichever transaction gets mined first into the longest chain wins; the other is discarded. Alice would need to out-mine the honest network (controlling $>50\%$ of compute power) to retroactively rewrite history — a 51% attack.

Security via gambler’s ruin.

If an attacker controls fraction $q < 1/2$ of compute power and an honest transaction has been confirmed with $k$ blocks of work on top of it, the probability that the attacker can reverse the transaction converges to $(q/(1-q))^k$, which is negligible for modest $k$ (e.g., Bitcoin conventionally waits for 6 confirmations $\approx$ 60 minutes).

Incentive Mechanism

Nakamoto designed a self-sustaining incentive structure:

• Block reward: the miner who finds a valid block creates new coins (initially 50 BTC, halving every 210,000 blocks), funding their own computational cost.

• Transaction fees: users can attach fees to transactions; miners prioritize high-fee transactions, creating a market for block space.

This aligns rational miners’ interests with honest participation: cheating (e.g., accepting double-spends) would undermine confidence in Bitcoin and destroy the value of the very coins they just earned.

Merkle Trees for Efficient Verification

Each block header commits to its transaction set via a Merkle tree: transactions are leaves; each internal node is the hash of its two children; the root hash is stored in the block header (a single 32-byte value regardless of how many transactions are in the block).

Practical benefit.

A light client (e.g., a mobile wallet) does not store the full blockchain. To verify that transaction $T$ is in block $B$, it only needs the root hash (already stored in the block header) and the $O(\log n)$ sibling hashes along the path from $T$’s leaf to the root — an authentication path. Full transaction data can be pruned after a block is sufficiently buried.

Privacy Limitations: Pseudonymity vs. Anonymity

Bitcoin’s white paper describes a “privacy model” based on pseudonymity: instead of using real names, users operate under public keys. But this is not anonymity.

Linkage attacks.

Because the blockchain is a public ledger, every transaction is visible. An adversary who can link one public key to a real identity (e.g., via an exchange that requires KYC, or via IP address logging when a transaction is first broadcast) can trace the graph of all that key’s transactions. Further, inputs to a transaction are often assumed to belong to the same wallet, allowing clustering.

Connection to Netflix de-anonymization.

This is the same structural problem as the Netflix Prize dataset (Chapter 11): releasing “anonymous” records with rich structure provides sufficient auxiliary information for re-identification. The blockchain is maximally rich in structure — a permanent, global, perfectly accurate record of every transaction ever made.

ZK-SNARKs as a Privacy-Preserving Upgrade

The pseudonymity failure of Bitcoin motivated the design of privacy coins such as Zcash, which use ZK-SNARKs (Section 17.11) to allow shielded transactions: a user proves in zero knowledge that

1. They own a valid coin (i.e., know a secret key for a coin in the Merkle tree of unspent outputs), and

2. They are not double-spending (the nullifier for this coin has not been revealed before),

without revealing which coin, which key, or how much is being transferred. The SNARK proof is succinct ($\mathrm{poly}\log N$) and non-interactive, making it compatible with blockchain’s trust model.

Selfish mining.

One known attack on Nakamoto consensus is selfish mining: a miner with fraction $q > 1/3$ of compute power can earn disproportionate rewards by strategically withholding found blocks and releasing them to fork the honest chain. This violates the assumption that rational miners always broadcast blocks immediately, and is an active research area connecting mechanism design to cryptographic protocols.