Differential privacy in BigQuery

SELECT WITH DIFFERENTIAL_PRIVACY adds noise to aggregates and drops small groups, so a result can't reveal one person. How the parameters work, what clamping does to your numbers, and the simpler aggregation threshold rule.

Differential privacy in BigQuery is a query clause, SELECT WITH DIFFERENTIAL_PRIVACY. BigQuery computes each aggregate per person (the privacy unit), caps how much one person can contribute, adds random noise to the totals, and drops groups with too few people. The result is close to the true answer for large groups, and it is built so that it doesn’t reveal whether any one person is in the data. Every run returns slightly different numbers, so the examples below print only values that don’t change from run to run.

A differentially private query

SELECT WITH DIFFERENTIAL_PRIVACY
  OPTIONS (epsilon = 1, delta = 1e-5, max_groups_contributed = 1, privacy_unit_column = user_id)
  region,
  COUNT(*, contribution_bounds_per_group => (0, 1)) AS visitors
FROM visits
GROUP BY region;

The rules for a valid query:

• Exactly one privacy_unit_column, a column that identifies the person (or company, or device) you protect. It can appear in many groups, and its type must be groupable.
• epsilon and delta are required numbers. Leaving out delta fails with Differential privacy option DELTA must be set and non-NULL. Leaving out the privacy unit fails with A SELECT WITH DIFFERENTIAL_PRIVACY query must query data with a specified privacy unit column. A negative epsilon fails with Epsilon must be finite and positive.
• Only differentially private aggregates in the select list. Google lists COUNT, SUM, AVG and PERCENTILE_CONT. DISTINCT isn’t available:

-- DISTINCT is not available in differentially private aggregates.
WITH visits AS (
  SELECT 1 AS user_id, 'north' AS region
)
SELECT WITH DIFFERENTIAL_PRIVACY
  OPTIONS (epsilon = 1, delta = 1e-5, privacy_unit_column = user_id)
  region, COUNT(DISTINCT user_id) AS n
FROM visits
GROUP BY region

What BigQuery does to the numbers

For each query, in this order:

1. Compute the aggregate for each privacy unit in each group. A unit that appears in more groups than max_groups_contributed is cut down to that many groups.
2. Clamp each unit’s value to the bounds, so one person can’t move the total far.
3. Add the clamped values for each group.
4. Add noise to each group’s total. The noise size depends on the bounds and on epsilon.
5. Compute a noisy count of units per group and remove groups with few units.

Two parameters set the noise. Epsilon is the privacy budget: a higher epsilon means less noise and less privacy. Delta is the probability that a row in the result fails to be epsilon-private. It is a small number like 1e-5. Epsilon is split between all aggregates in the query, plus one more share for the hidden count that removes small groups. With n aggregates each one gets epsilon / (n + 1), and if you use max_groups_contributed the share is divided again by that number. A query with four aggregates and an epsilon of 1 has noise for each aggregate as if its epsilon were 0.2.

Because of this, a differentially private query is not the same query with noise on top. It changes what is counted, as the next two sections show.

Noisy, but close for large groups

With a real epsilon the output moves a little with each run. We counted visitors in two regions with 10,000 users each, and rounded the noisy result to the nearest thousand, which hides the noise:

-- A real epsilon adds noise to each count. Rounding to thousands hides it here, because 20,000 users make the noise tiny by comparison.
WITH visits AS (
  SELECT user_id, IF(MOD(user_id, 2) = 0, 'north', 'south') AS region
  FROM UNNEST(GENERATE_ARRAY(1, 20000)) AS user_id
)
SELECT WITH DIFFERENTIAL_PRIVACY
  OPTIONS (epsilon = 1, delta = 1e-5, privacy_unit_column = user_id)
  region,
  ROUND(COUNT(*, contribution_bounds_per_group => (0, 1)), -3) AS visitors_to_nearest_thousand
FROM visits
GROUP BY region
ORDER BY region

Both rows showed 10000 in every run we made. The noise depends on the bounds and on epsilon, not on how many users are in the group, so counts for large groups are accurate in relative terms and counts for small groups are not.

Turning the noise off to check the logic

Google documents epsilon = 1e20 as the setting that removes the noise, useful when you build a query and want to see the true result. Extremely large values such as 1e308 make the query fail. Use it to test, and never in a query you share.

-- epsilon = 1e20 turns the noise off, which Google documents for exploring a query. Real queries use a small epsilon.
WITH students AS (
  SELECT * FROM UNNEST([
    STRUCT(1 AS id, 'pencil' AS item, 5 AS quantity),
    (1, 'pen', 2), (2, 'pen', 1), (3, 'pen', 4), (4, 'pen', 3), (5, 'pen', 9)
  ])
)
SELECT WITH DIFFERENTIAL_PRIVACY
  OPTIONS (epsilon = 1e20, delta = 1e-5, max_groups_contributed = 2, privacy_unit_column = id)
  item,
  COUNT(*, contribution_bounds_per_group => (0, 10)) AS students,
  SUM(quantity, contribution_bounds_per_group => (0, 10)) AS total_quantity
FROM students
GROUP BY item
ORDER BY item

Five students bought pens and one bought pencils. COUNT returned 5 and 1, and SUM returned 19 and 5, the true values. At a real epsilon the pen count would be a number near 5, and the pencil row, with one student, would probably be missing.

Clamping changes the answer

contribution_bounds_per_group => (0, 1) limits each person’s contribution to a group to between 0 and 1. For COUNT(*) that means each person counts once however many rows they have. We took 20,000 users with five page views each:

-- 20,000 users with 5 page views each. Clamping each user's count to 1 turns "rows" into "users".
WITH page_views AS (
  SELECT user_id, page
  FROM UNNEST(GENERATE_ARRAY(1, 20000)) AS user_id, UNNEST(['a', 'b', 'c', 'd', 'e']) AS page
),
dp AS (
  SELECT WITH DIFFERENTIAL_PRIVACY
    OPTIONS (epsilon = 1e20, delta = 1e-5, privacy_unit_column = user_id)
    COUNT(*, contribution_bounds_per_group => (0, 1)) AS clamped_count
  FROM page_views
)
SELECT
  (SELECT COUNT(*) FROM page_views) AS true_rows,
  (SELECT clamped_count FROM dp) AS counted_with_bounds_0_1

The query counted 20,000, the number of users, and not 100,000 rows. This is the point of the bound: no one person can add more than 1. If you wanted rows, set the upper bound to 5 or more, and know that the noise grows with the bound.

If you leave the bounds out, BigQuery picks them from the data in a differentially private way. Google warns this works only on large data: with few privacy units it can return no rows, or clamp many normal values and under-report. For small data, give explicit bounds. Half of the aggregate’s epsilon goes to finding the implicit bounds.

A person is counted in only one group by default

max_groups_contributed defaults to 1, even if you don’t write it. A person with rows in two groups is counted in one of them, chosen by BigQuery. We had a student in both the pencil and pen groups:

-- Student 1 is in two groups (pencil and pen). With the default max_groups_contributed = 1 only one of them counts.
WITH students AS (
  SELECT * FROM UNNEST([
    STRUCT(1 AS id, 'pencil' AS item, 5 AS quantity),
    (1, 'pen', 2), (2, 'pen', 1), (3, 'pen', 4), (4, 'pen', 3), (5, 'pen', 9)
  ])
),
default_limit AS (
  SELECT WITH DIFFERENTIAL_PRIVACY
    OPTIONS (epsilon = 1e20, delta = 1e-5, privacy_unit_column = id)
    item, COUNT(*, contribution_bounds_per_group => (0, 10)) AS n
  FROM students
  GROUP BY item
),
two_groups AS (
  SELECT WITH DIFFERENTIAL_PRIVACY
    OPTIONS (epsilon = 1e20, delta = 1e-5, max_groups_contributed = 2, privacy_unit_column = id)
    item, COUNT(*, contribution_bounds_per_group => (0, 10)) AS n
  FROM students
  GROUP BY item
)
SELECT
  (SELECT COUNT(DISTINCT id) FROM students) AS students,
  (SELECT SUM(n) FROM default_limit) AS counted_with_default_limit,
  (SELECT SUM(n) FROM two_groups) AS counted_with_limit_2

With the default, the group counts add up to 5, the number of students. With max_groups_contributed = 2 they add up to 6, since the student is counted in both groups. If you group by something that people span, such as month or product, the default under-counts some groups, and which group loses the person changes between runs. Set max_groups_contributed to the number of groups a person can really be in, knowing that noise scales with it. Setting it to NULL removes the limit, and then Google says BigQuery can’t guarantee that the results are differentially private.

Small groups disappear

The hidden noisy count drops groups with few privacy units. On 5 users with explicit bounds, a grouped query at epsilon = 1, delta = 1e-5 returned no rows in our test, and so did an ungrouped one. The threshold is itself random, so we can’t give you a number of users that always survives. A query that returns nothing doesn’t mean there was an error. Check how many users are in each group before blaming the query. When the grouping column is the privacy unit column itself, every group has one person and the query returns no rows.

Aggregation threshold: the simpler rule

If what you need is that no group shows fewer than N people, and noise is more than you want, BigQuery has SELECT WITH AGGREGATION_THRESHOLD. It does no noise: it counts the distinct privacy units in each group and returns only groups that reach the threshold. The numbers that appear are exact.

-- A group is kept when at least 2 different users are in it. Page x has 5 rows, but all from user 1.
WITH page_views AS (
  SELECT * FROM UNNEST([
    STRUCT(1 AS user_id, 'a' AS page), (2, 'a'), (3, 'a'),
    (1, 'b'), (2, 'b'),
    (1, 'c'),
    (1, 'x'), (1, 'x'), (1, 'x'), (1, 'x'), (1, 'x')
  ])
)
SELECT WITH AGGREGATION_THRESHOLD
  OPTIONS (threshold = 2, privacy_unit_column = user_id)
  page, COUNT(*) AS views
FROM page_views
GROUP BY page
ORDER BY page

Page a has 3 users, b has 2, and both appear. c has 1 user and is dropped. Page x has five rows, but all from one user, so it is dropped too: the threshold counts people, not rows.

Rules we saw:

• Grouping by the privacy unit column gives every group one unit. Inline, that returns no rows, and no error:

  grouping by the privacy unit column returns nothing

  123456789

  -- Grouping by the privacy unit column puts each user in a group of one, so every group is dropped. No error, no rows.
  WITH page_views AS (
    SELECT * FROM UNNEST([STRUCT(1 AS user_id, 'a' AS page), (2, 'a'), (3, 'a')])
  )
  SELECT WITH AGGREGATION_THRESHOLD
    OPTIONS (threshold = 2, privacy_unit_column = user_id)
    user_id, COUNT(*) AS views
  FROM page_views
  GROUP BY user_id

  Result in BigQuery

  	user_id	views

  0 rows

• Only some aggregates work. SUM, AVG, COUNT and COUNT(DISTINCT ...) ran for us. MAX fails, because it would return one user’s value:

  MAX in an aggregation threshold queryBigQuery rejects this query

  123456789

  -- Only some aggregates are allowed. MAX could return one user's value.
  WITH page_views AS (
    SELECT * FROM UNNEST([STRUCT(1 AS user_id, 'a' AS page, 10 AS ms), (2, 'a', 20), (3, 'a', 30)])
  )
  SELECT WITH AGGREGATION_THRESHOLD
    OPTIONS (threshold = 2, privacy_unit_column = user_id)
    page, MAX(ms) AS slowest
  FROM page_views
  GROUP BY page

  Error in BigQuery

  max is not supported in a SELECT WITH AGGREGATION_THRESHOLD query.

• threshold must be above 0. An ungrouped query with a threshold above the number of users returns no rows, not a zero.

• Without a table that has a policy, you must give both threshold and privacy_unit_column, or you get must query at least one table with privacy policy or specify threshold and privacy_unit_column options.

Aggregation threshold gives less protection than differential privacy. Exact numbers from several overlapping queries can still reveal a person, for example COUNT of a group with and without them. Use it to stop obviously small groups, and use differential privacy when you can’t rule out those comparisons.

Making the rule mandatory on a view

A data owner can attach the rule to a view with the privacy_policy option, so anyone who queries the view must use it. This statement needs a permanent view, so it is not runnable here:

CREATE OR REPLACE VIEW shared.page_views
OPTIONS (
  privacy_policy = '''{
    "aggregation_threshold_policy": {"threshold": 2, "privacy_unit_column": "user_id"}
  }'''
) AS
SELECT user_id, page FROM raw.page_views;

We created a view like this and queried it:

A reader can raise the threshold, not lower it. The error here is clearer than the inline form: on a policy view, grouping by the privacy unit column is refused, where the inline query silently returns nothing. Google’s analysis rules page also covers a differential privacy rule for views, which enforces a privacy budget across queries, and a join restriction policy. We didn’t test those.

Cost and limits

Differential privacy has no extra charge; the query is billed as usual. It runs slower than the plain query, because BigQuery first groups by the privacy unit as well as by your groups, and a column with many distinct units makes that grouping large. Google compares it to GROUP BY column_a, id. Google says that narrower contribution bounds help.

Google lists limits that matter if you share results with people you don’t trust:

• BigQuery doesn’t promise that a result has particular privacy properties. It applies the published algorithm, and an analyst writing queries in bad faith can still probe it.
• A query can fail with a runtime error on private data, and an attacker who can control the data or the queries can use that.
• Noise added to FLOAT64 values is open to floating-point attacks. Noise on integers isn’t.

Treat differential privacy as one control, next to access control, row-level security and column-level security, and not a replacement for them.