COE526 / Lecture 07 / Differential Privacy I
Activity 1 of 8
EXPLORE · CALCULATE · EXPLAIN

Differential privacy,
one person at a time.

See how one record changes a statistic, calibrate random noise, and account for what repeated releases reveal.

01 · Neighbors and a differencing attack

A clinic publishes how many patients have a disease. See how two exact counts can reveal one patient’s secret.

Lab setup. Every dataset and numerical scenario in the experiments is synthetic. No patient, salary, or census microdata is used. True answers are visible to help you learn; a real private release would expose only its protected output.
Key idea. Subtract two exact answers that differ by one person and you learn that person’s data. Differential privacy (DP) stops this by adding random noise.

Words you need

  • D · the real dataset
  • D′ (“D prime”) · the same dataset with one person removed or changed
  • Query f · a question about the data, such as a count
  • Sensitivity Δf · the most one person can change the answer
  • ε (epsilon) · the privacy budget; smaller means more private
  • Noise · a random number added to the true answer
  • Release A(D) · the noisy answer that is published
Synthetic clinic · six people

Dataset D

Choose a target patient and change disease indicators. Each row represents one person.

PatientAgeDisease?Target

Attack view

Two counts, one sensitive bit

has the diseasedoes nottarget✕ excluded from the query

count(D) − count(D \ {target}) = target’s disease indicator

The attacker knows the target belongs to this clinic and can request a count excluding that person. Removing names from the published counts does not stop this attack.

What changed in the neighbor?

The attack always compares the two filters “all patients” and “all except target.” The neighbor selector separately illustrates the privacy definition.

Try it.
  1. Select patient A as the target. Read the attack result: what does the attacker learn?
  2. Select patient F. Why does removing F change the number of people but not the disease count?
  3. Switch the neighbor definition to “Replace one person’s record”. Compare the sizes of D and D′.
Worked explanation and attack terminology

Initially D has six people and three disease-positive records. Removing A gives five people and two positive records; removing F gives five people and three positive records. Both are neighboring pairs. Replacing one record keeps six people and can change the disease count by at most one.

Differencing isolates one person’s contribution. Linkage connects an anonymous record to an identity using other information. Reconstruction recovers many records from many accurate statistics. Membership inference asks whether someone contributed data. DP bounds the effect of participation; it does not prevent all inference about population patterns.

02 · One matching output is not enough

DP asks one question: does any output become much more likely because of one person? Matching at one output (4) is not enough. Every output must be checked.

Key idea. For every output y, the chance with the person and the chance without them must stay within a factor of eε.
Pr[M(D) = y] ≤ eε · Pr[M(D′) = y]

This must hold for every neighboring pair, in both directions. Going further: the general form is Pr[M(D) ∈ S] ≤ eε Pr[M(D′) ∈ S] + δ for every set of outputs S. Pure DP uses δ = 0; this lab uses δ = 0 unless you open the optional δ control. With continuous outputs, compare densities, because the chance of one exact real number is zero.

Compare complete distributions

M(D), true count 3M(D′), true count 2
Output yPr[M(D)=y]Pr[M(D′)=y]Largest directional ratio

These distributions are explicitly defined teaching examples, not a claimed DP mechanism over all datasets. They are not centered on the true counts; only the comparison between the two columns matters for the bound.

Test the bound

Optional: allow a small δ (approximate DP)
eε
Pure ε needed
δ needed here

Each bar is ln(Pr[M(D)=y] / Pr[M(D′)=y]). Pure ε-DP (δ = 0) needs every bar inside the shaded ±ε band. With δ > 0, a coral bar can still be allowed if the total excess probability is at most δ.

δ is additive slack in an event-probability bound. It is not, in general, a simple probability that the system “leaks everything.”

The tool checks all event bounds exactly by finding the maximizing subset of {2,3,4,5,6} in each direction for this selected pair. Passing this comparison does not prove DP over every neighboring pair.

Try it.
  1. Keep the first example. Move ε slowly up until the result turns green. Write down that ε.
  2. In the table, which output has the largest ratio? (It is not output 4.)
  3. Choose “An output possible in only one dataset”. Why can no ε make it pass? Think about dividing by 0.

Calculate the minimum ε for the first pair

Hint

Find the largest number in the table’s last column, then take its natural log: ε = ln(largest ratio).

Show calculation

The largest ratio is 0.2 / 0.1 = 2, so ε must be at least ln(2) ≈ 0.693 for this pair. At output 4, the ratio is 0.4 / 0.4 = 1. That one ratio tells us nothing about the worst output elsewhere.

03 · Sensitivity comes before noise

Sensitivity is the most one person can change the answer, over every possible dataset. It decides how much noise to add.

Δ1f = maxD ∼ D′ ‖f(D) − f(D′)‖1
Key idea. Count: one person changes it by at most 1, so Δf = 1. Sum of salaries: one person can add up to the cap B, so Δf = B. The cap must be public and chosen before looking at the data.

Choose a bounded query

Public lower bound = 0 SAR. One salary or one category per person. Bounds must be set before examining private data.

A salary outlier changes the sum

Synthetic salaries (SAR): 6,000; 9,000; 14,000; 7,500; 4,500; 11,000.

clip(x) = min(B, max(0, x))

value used by the queryoriginal salary above BUpdates when you change B.

EmployeeOriginal salaryAfter clipping

Contribution limits matter. If one person can add many records, row-level sensitivity does not automatically protect that person. The lab assumes one record per person.
Try it.
  1. Choose “Sum of clipped monthly salaries”. Note Δf.
  2. Change B from 10,000 to 20,000. What happens to Δf? What happens to the 14,000 salary in the table?
  3. A bigger B means less clipping but more noise (b = Δf / ε). Which B would you choose, and why?
  4. Optional: choose the histogram and compare the two adjacency options.

Check your calculation

For a fixed public n = 6, salaries in [0, 10,000] SAR, and replacement adjacency, what is the sensitivity of the mean?

Hint

Replacing one salary changes the sum by at most B. The mean is the sum divided by n.

Show calculation

Replacing one salary can change the sum by at most 10,000 SAR. Dividing by the fixed public n = 6 gives Δf = 10,000 / 6 ≈ 1,666.67 SAR. This formula does not cover an add/remove mean with a changing private denominator.

04 · Step by step: one private release

Follow one query from the dataset to the published number. Each step says why it is needed, gives the equation, and then repeats the equation with real numbers. There are three examples: work through all three.

Key idea. Published answer = true answer + random noise. The noise is just big enough to hide any one person: its size is b = Δf / ε.
Choose an example · 3 to try

Everything below, the charts and all ten steps, updates for the example you pick. Examples 1 and 2 are from the lecture. Example 3 shows what happens when one person can change the answer a lot.

Example 1 of 3 · Lecture count

True answer f(D) · kept secret
Noise x
Published y

The lecture’s starting values: p = 0.7863 gives the slide’s release 121.7; the hospital value gives the output S = 4; the salary value gives 15,433 SAR.

Picture of the release

density of A(D), centered at f(D)density of A(D′), centered at f(D′) (dashed)published y

Laplace CDF F(x)go across from p to the curve, then down to the noise x (steps 6–7)

Two letters, two jobs. In step 7, p (and u = p − ½) is the flat random number the computer draws. x is the Laplace noise computed from it. Some slides write the density as g(u), with u meaning the noise value; that u is the same as x here.

    Finished example 1 of 3? The next one changes the numbers in every step.

    Try it.
    1. Keep the lecture example. Press “Draw a random p” five times. Watch the published y in step 8 change.
    2. Look at step 9 each time. The ratio is often exactly eε (when y is outside both true answers) and smaller when y is between them, but it never goes above eε.
    3. Tick “Make a deliberate mistake” and draw again. When does step 9 show > eε ✗? Why does too little noise break the guarantee?
    4. Go to example 2 (hospital count). Which steps change, and which stay the same?
    5. Go to example 3 (six salaries). Compare step 10 with example 1: same steps, very different accuracy. Why?

    Check the slide example

    Lecture count: f(D) = 120, Δf = 1, ε = 0.5. The computer draws u = +0.2863 (p = 0.7863). What value is published?

    Hint

    First find b = Δf / ε. Then use noise = −b · sign(u) · ln(1 − 2|u|), and add the noise to 120.

    Show calculation

    b = 1 / 0.5 = 2. Since u ≥ 0, noise = −2 · ln(1 − 2 × 0.2863) = −2 · ln(0.4274) = −2 × (−0.8500) ≈ +1.70. Published value = 120 + 1.70 = 121.70. The draws u = −0.2753 and u = +0.0476 give the slide’s other examples, 118.4 and 120.2.

    05 · Calibrate and sample Laplace noise

    Now release many noisy answers and look at the pattern. Smaller ε means wider noise: more privacy, less accuracy.

    Key idea. Each release is true value + Laplace noise with scale b = Δf / ε. About 95% of releases land within ±3b of the truth. Activity 04 shows every step of one release.

    A statistic with a private release

    Sensitivity Δf
    Scale b = Δf / ε
    95% error radius
    M(D) = f(D) + Z,   Z ∼ Laplace(0, b)
    —

    Draw a sample to see true value + noise = release.

    No samples yet.

    Bars: simulated releases. Coral curve: the count expected from the Laplace density. Shaded band: the 95% error radius around the true value. The plot shows ±5b; tail draws stay in the statistics and are counted below the plot.

    Could the same output come from D′?

    density of M(D)density of M(D′)inspected output yShaded: 95% of M(D)’s noise mass
    pD(y) / pD′(y)
    = exp((|y − f(D′)| − |y − f(D)|) / b)

    Where does the 95% radius come from?

    For Laplace noise, Pr[|Z| ≤ r] = 1 − exp(−r/b). Set this to 0.95: r = b ln(20) ≈ 2.996b. This is a probability statement before sampling; it does not guarantee that every realized error falls in the range. E[|Z|] = b and SD(Z) = √2 b.

    Try it.
    1. Choose “Lecture count”. Set ε = 0.25 and press “Simulate 1,000 answers”. Note the mean absolute error and b.
    2. Set ε = 1 (this clears the samples) and simulate again. Is the error smaller or bigger?
    3. Check: the mean absolute error should be close to b both times.
    Simulation is not a protected data service. These independent experiments reveal their synthetic truth. Each fresh release on a real dataset would consume privacy budget; seeing 1,000 outputs is not the same as seeing one output. Changing parameters clears this module’s sample display.

    Check the lecture example

    Count sensitivity Δf = 1 and ε = 0.5. What is the Laplace scale b?

    Hint

    b = Δf / ε.

    Show calculation

    b = 1 / 0.5 = 2. A release of 118.4 corresponds to a sampled noise value of −1.6. The examples 118.4, 121.7, and 120.2 are possible releases; they are not special or predetermined probabilities. Activity 04 shows how each one is computed, step by step.

    06 · Release a histogram as one vector

    A city publishes population counts by age band. Each person belongs to exactly one of four public categories.

    Key idea. Add noise to every bin. Because each person is in only one bin, the whole histogram costs ε once, not once per bin.
    Synthetic city · 30 people

    Original and noisy counts

    True synthetic countDisplayed outputRaw noisy value ± 95% noise radius
    Age bandTrueRaw noisyDisplayed

    Public bins, bounded contribution

    Removing one person changes one bin by 1. A replacement can move a person between two bins, changing the vector’s L₁ norm by 2. Independent Laplace noise with scale Δ₁/ε is added to every coordinate.

    Changing this display option reuses the same noisy vector. It does not query the original records again.

    Changing ε or adjacency starts a new synthetic histogram sandbox. In a real release system, changing these settings would not erase earlier privacy loss. The categories are fixed publicly. Clamping and rounding are post-processing, but they may introduce bias. The displayed total need not equal 30. Forcing it to match a private true total is not free post-processing.

    Why not charge ε once for each bin?

    The whole histogram is analyzed as one vector query with global L₁ sensitivity. Under add/remove adjacency, a person changes only one coordinate, so scale 1/ε protects the full vector. Under replacement, a person can change two coordinates, so scale 2/ε is used.

    Try it.
    1. Press “Release a new histogram”. Compare the true and noisy columns.
    2. Untick “Round and clamp”. Raw values can be negative or decimals. Tick it again: the noise is the same, only the display changes.
    3. Switch to “Replace one record”. Why does b double?

    07 · Spend, reuse, and compose

    Fresh noise does not give free repeated queries. A privacy accountant tracks releases made about the same people.

    Key idea. Every fresh noisy answer spends ε, and the costs add up: 4 releases at ε = 0.3 cost 1.2. Reusing an answer you already published is free.

    A release ledger

    Independent classroom sandbox: disease count = 3, Δf = 1, total public budget = 3.00. Uses basic sequential composition.

    Fresh releases0
    ε spent0.00
    ε remaining3.00
    01.53.00 total ε
    Ready to release. Reusing a stored answer costs no additional ε.
    ReleaseεbNoisy answerTotal ε

    Reset starts a new synthetic demonstration. In a real system, deleting a ledger or changing a webpage does not erase previous privacy loss.

    What if an analyst averages q releases?

    Purple (left axis): theoretical standard deviation of the average of q independent Laplace releases. Coral dashed (right axis): the basic sequential-composition ε bound. Neither line estimates a real attack.

    SD(average) = √2 b / √q

    Basic composition and post-processing

    For releases on the same people, basic sequential composition gives an upper bound εtotal = Σεi. For approximate DP it also gives δtotal = Σδi. Averaging released answers does not add further privacy loss beyond the releases themselves.

    When mechanisms act on disjoint groups of people, parallel composition can use the largest group ε rather than the sum, under the corresponding person-level adjacency. Disjoint rows are insufficient if a person appears in several groups.

    Try it.
    1. Press “Make fresh release” six times with ε = 0.5. Watch the budget bar fill.
    2. Try a seventh release. What happens? Then press “Reuse last release”: does ε spent change?
    3. On the right, switch to “Share fixed total ε”. Does averaging more releases still help?

    Check the total budget

    A count is released four times on the same people, each with ε = 0.3. What is the basic sequential-composition ε bound?

    Hint

    Basic composition: add up the ε of every release.

    Show calculation

    εtotal ≤ 4 × 0.3 = 1.2. Reformatting or averaging those four stored outputs does not require another query and adds no further ε.

    08 · Real applications and your lab report

    Connect the experiments to documented uses of differential privacy, then record your choices and observations.

    Key idea. Central DP: a trusted server adds noise once, so answers are accurate. Local DP: each device adds its own noise, so no one needs to be trusted, but answers are noisier.

    Where is the noise added?

    Central versus local trust modelsCentral model: people send raw records to a trusted curator, who adds Laplace noise to a statistic before publishing. Local model: each device randomizes its own report; an untrusted aggregator only sees randomized reports and estimates the statistic. Central modelActivities 01–07 · U.S. Census 2020 Local modelRandomized response · Apple emoji ABC ABC raw records Trusted curatorsees every raw record +Znoise added once,to the statistic Published noisy statistic +++on device Untrusted aggregatorsees only randomized reports debias & aggregate Estimated statistic

    Central DP needs a trusted curator but adds noise once, so it is usually more accurate. Local DP removes that trust assumption at the cost of much more noise. The protected unit also matters: the lab’s central examples protect one person’s record, while Apple’s documented system protects each donation, with a daily limit.

    Documented deployment · central model

    U.S. Census · 2020 statistics

    The 2020 Census used a disclosure-avoidance system based on DP. Its TopDown algorithm takes noisy measurements of key queries and post-processes them into consistent tabulations across a geographic hierarchy.

    Two differences from Activity 06: TopDown accounts for privacy loss with zero-concentrated DP (zCDP), not the pure ε used here, and some statistics were designated invariants by policy, published without noise and excluded from the privacy-loss accounting. This is a historical 2020 example, not a claim about future census policy.

    [S3] TopDown algorithm paper ↗
    Documented deployment · local model

    Apple · popular emoji

    Apple’s technical overview describes estimating popular emoji with local DP. Each device privatizes its contribution with a Count Mean Sketch before sending it; the server only aggregates the randomized reports.

    The overview lists a per-donation budget of ε = 4 for emoji and one donation per day. The guarantee therefore protects each donation; under composition, many days of donations add up. The sketch is more involved than the two-coin classroom procedure, and these documented parameters may not be current.

    [S4] Apple technical overview ↗
    Practical software · bounded aggregates

    Google · DP libraries

    Google publishes open-source libraries for private counts, sums, means, variances and quantiles with Laplace or Gaussian noise. The low-level libraries assume each user contributes a bounded number of rows, but they do not enforce that bound.

    The caller, or an end-to-end framework such as Privacy on Beam or PipelineDP4j, must group by user and limit contributions first. Activity 03 makes this visible: clipping a salary does not limit how many salary records one person contributes.

    [S5] Official library and caveats ↗
    Continue in the existing course lab

    Randomized response

    Practice client-side randomization in the existing activity. For the fair two-coin version in this lecture, truthful response has probability ½ and the other branch answers using a fair second coin.

    Pr[Yes | Yes] = ¾
    Pr[Yes | No] = ¼
    ε = ln(3)

    Only participants taking the randomized branch flip a second coin. Compare its local trust model with the central Laplace experiments above.

    Open the existing randomized-response lab ↗
    Mechanisms beyond this first lab

    Gaussian mechanism: commonly supports approximate (ε,δ)-DP with noise calibrated to L₂ sensitivity and an appropriate accountant. Report noisy max: releases the selected index rather than all noisy scores. Exponential mechanism: selects an outcome using a sensitivity-bounded utility score. DP-SGD: clips per-example or per-person gradients and adds calibrated noise during training. These require their own assumptions and accounting; adding arbitrary noise to a model or prompt does not establish DP.

    Your observations

    Use the experiment displays to record exact parameters and observed outputs. Your text remains in this page until you close or reload it; download your report to keep it.

    Sources and lecture alignment

    Adapted from the attached COE526-L07-Differential Privacy I(2).pptx: neighboring datasets and attacks (slides 4–10), randomized outputs and the definition (12–17), noise and sensitivity (19, 21, 23), applications (20, 30), and the link to randomized response (25–28). Accounting extends the lecture’s stated learning objectives. Advanced ML topics remain a preview.

    1. [S1] Dwork, C. & Roth, A. (2014). The Algorithmic Foundations of Differential Privacy. Definition 2.4; Proposition 2.1; Sections 3.2, 3.3 and 3.5. Supports the formal definition, post-processing, randomized response, Laplace mechanism and basic composition.
    2. [S2] Karmitsa, N., Airola, A., Pahikkala, T. & Pitkämäki, T. (2025; v3 revised 2026). A Comprehensive Guide to Differential Privacy: From Theory to User Expectations. arXiv:2509.03294v3. Background reading used by the lecture.
    3. [S3] Abowd, J. M. et al. (2022). The 2020 Census Disclosure Avoidance System TopDown Algorithm. arXiv:2204.08986. Supports the Census deployment example, including zCDP accounting and policy invariants.
    4. [S4] Apple. Differential Privacy Overview. Supports the local-DP emoji example (Count Mean Sketch, ε = 4 per donation, one donation per day); describes its documented system, not a guarantee that its historical parameters remain current.
    5. [S5] Google. Differential privacy libraries, algorithms and caveats. Supports the software example, the contribution bound that the building-block libraries assume but do not enforce, and their stated floating-point caveats. Sources checked 12 October 2026.
    6. [S6] Mironov, I. (2012). On Significance of the Least Significant Bits for Differential Privacy. In Proceedings of the 2012 ACM Conference on Computer and Communications Security (CCS ’12), pp. 650–661. ACM. doi:10.1145/2382196.2382264. Supports the floating-point warning below: naive floating-point Laplace sampling can leak information through low-order bits. Checked 14 October 2026.

    Educational simulation with JavaScript floating-point sampling. Naive floating-point Laplace sampling like this is known to leak information through its low-order bits (Mironov, 2012 [S6]); production libraries use secure noise generation. This page illustrates mathematical mechanisms and is not an audited production DP implementation.

    COE526 · Differential Privacy I · Synthetic experiments, documented applications. Each activity is an independent learning sandbox.