Deploying Differential Privacy for the2020 Census of Population and Housing
Simson L. Garfinkel
Senior Scientist, Confidentiality and Data Access
U.S. Census Bureau
July 16, 2019
Privacy Enhancing Technologies Symposium
Stockholm, Sweden 2019
The views in this presentation are those of the author,
and not those of the U.S. Census Bureau.

1Abstract
When differential privacy was created more than a decade ago, the motivating example was statistics published by an official
statistics agency. In theory there is no difference between theory and practice, but in practice there is.
In attempting to transition differential privacy from the theory to practice, and in particular for the 2020 Census of Populationand Housing, the U.S. Census Bureau has encountered many challenges unanticipated by differential privacy's creators.
Many of these challenges had less to do with the mathematics of differential privacy and more to do with operational
requirements that differential privacy’s creators had not discussed in their writings. These challenges included obtaining
qualified personnel and a suitable computing environment, the difficulty of accounting for all uses of the confidential data, thelack of release mechanisms that align with the needs of data users, the expectation on the part of data users that they will
have access to micro-data, the difficulty in setting the value of the privacy-loss parameter, ε (epsilon), and the lack of tools
and trained individuals to verify the correctness of differential privacy, and push-back from same members of the data user
community.
Addressing these concerns required developing a novel hierarchical algorithm that makes extensive use of a highperformance commercial optimizer; transitioning the computing environment to the cloud; educating insiders about differential
privacy; engaging with academics, data users, and the general public; and redesigning both data flows inside the Census
Bureau and some of the final data publications to be in line with the demands of formal privacy.

2

Acknowledgments
This presentation incorporates work by:
Dan Kifer (Scientific Lead)John Abowd (Chief Scientist)
Tammy Adams, Robert Ashmead, Aref Dajani, Jason Devine, NathanGoldschlag, Michael Hay, Cynthia Hollingsworth, Meriton Ibrahimi,
Michael Ikeda, Philip Leclerc, Ashwin Machanavajjhala, ChristianMartindale, Gerome Miklau, Brett Moran, Ned Porter, Anne Ross,
William Sexton, Lars Vilhuber, and Pavel Zhuravlev

3

Outline
Motivation
The flow of census response data
Disclosure Avoidance for the 2010 census
Disclosure Avoidance for the 2018 census End-to-End test
Disclosure Avoidance for the 2020 census
Conclusion

4

Motivation
The 2020 Census ofPopulation andHousing

Count everyone once,
only once, and in the right place.

5Motivation
Article 1, Section 2“…The actual
Enumeration shall bemade within three Years
after the first Meeting of
the Congress of theUnited States, and withinevery subsequent Term of
ten Years, in such Manneras they shall by Law
direct…”

6

Article 1, Section 2
The House of Representatives shall be composed of Members chosen every second Year by the People of the several States, and the Electors ineach State shall have the Qualifications requisite for Electors of the most numerous Branch of the State Legislature.
No Person shall be a Representative who shall not have attained to the Age of twenty five Years, and been seven Years a Citizen of the UnitedStates, and who shall not, when elected, be an Inhabitant of that State in which he shall be chosen.
Representatives and direct Taxes shall be apportioned among the several States which may be included within this Union, according to theirrespective Numbers, which shall be determined by adding to the whole Number of free Persons, including those bound to Service for a Term of

The actual Enumeration shall bemade within three Years after the first Meeting of the Congress of
the United States, and within every subsequent Term of ten Years,
in such Manner as they shall by Law direct.
Years, and excluding Indians not taxed, three fifths of all other Persons.

The Number of Representatives shall not exceed one for every thirty Thousand, but each State shall have at Least one Representative; and until
such enumeration shall be made, the State of New Hampshire shall be entitled to chuse three, Massachusetts eight, Rhode-Island and Providence
Plantations one, Connecticut five, New-York six, New Jersey four, Pennsylvania eight, Delaware one, Maryland six, Virginia ten, North Carolina five,
South Carolina five, and Georgia three.
When vacancies happen in the Representation from any State, the Executive Authority thereof shall issue Writs of Election to fill such Vacancies.
The House of Representatives shall chuse their Speaker and other Officers; and shall have the sole Power of Impeachment.

“in such Manner as they shall by Law direct.”Public Law 94-171

http://uscode.house.gov/statutes/pl/94/171.pdf

Federal Register / Vol. 82, No. 215 / Nov 8, 2017 / Notices(for the 2018 End-to-End test)
Dec. 31, 2018
We will report (per block):
P1. RACE/ETHNICITY
Universe: Total population
Group by: BLOCK

P2. RACE/ETHNICITY

Universe: Total population age 18 and over

H1. OCCUPANCY STATUS
P42. GROUP QUARTERS POPULATION
Universe: Population in Group Quarters

We need to protect privacy!
13 U.S. Code § 9 - Information as confidential; exception(a) Neither the Secretary, nor any other officer or employee of the Department of Commerce or bureau or
agency thereof, or local government census liaison may, except as provided in section 8 or 16 or chapter 10 of thistitle or section 210 of the Departments of Commerce, Justice, and State, the Judiciary, and Related Agencies Appropriations Act,
1998.

(1) Use the information furnished under the provisions of this title for any purpose other than thestatistical purposes for which it is supplied; or(2) Make any publication whereby the data furnished by any particular establishment or individual
under this title can be identified; or(3) Permit anyone other than the sworn officers and employees of the Department or bureau or agency
thereof to examine the individual reports. No department, bureau, agency, officer, or employee of theGovernment, except the Secretary in carrying out the purposes of this title, shall require, for any
reason, copies of census reports which have been retained by any such establishment or individual.
Copies of census reports, which have been so retained, shall be immune from legal process, and shallnot, without the consent of the individual or establishment concerned, be admitted as evidence or used
for any purpose in any action, suit, or other judicial or administrative proceeding.
(b) The provisions of subsection (a) of this section relating to the confidential treatment of data for particular individuals andestablishments, shall not apply to the censuses of governments provided for by subchapter III of chapter 5 of this title, nor tointerim current data provided for by subchapter IV of chapter 5 of this title as to the subjects covered by censuses ofgovernments, with respect to any information obtained therefore that is compiled from, or customarily provided in, public records.

Statistical agencies collect data under apledge of confidentiality.
We pledge:
Collected data will be used only for statistical purposes.
Collected data will be kept confidential.
Data from individuals or establishments

won’t be identifiable in any publication.

11

12

Disclosure Avoidance for the 2010 Census

13

“Disclosure Avoidance”
means
preventing improper disclosures.

14

“This is theofficial form for
all the people atthis address.”“It is quick andeasy, and youranswers areprotected by
law.”
15

The 2010 Census collected data on 308,745,538 people.
DRF
Raw data from
respondents:
Decennial
Response File

HDF

Statistical
Processes

Pre-specified
tabularsummaries:
PL94-171, SF1,SF2 (SF3, SF4,
… in 2000)

Hundred-percent
Detail File
Specialtabulations andpost-census
research

Confidential data

Public data

16

DRF
Raw data from
respondents:
Decennial
Response File

Selection &unduplication:
CensusUnedited File

Edits, imputations:Census Edited
File

Confidentiality Mechanism

The 2000 and 2010 Confidentiality Mechanism
operated as a filter on the Census Edited File:
HDF

Pre-specified tabularsummaries:
PL94-171, SF1, SF2(SF3, SF4, … in 2000)

Hundred-percent
Detail File
Special tabulations
and post-census
research

Public data

17

For each person, we collected 6 variables(44 bits of data)
Variable

Range

Bits

Block

6,207,027 inhabited blocks

23

Sex

2 (Female/Male)1

Age

103 (0-99 single age year categories,
100-104, 105-109, 110+)

7

Race

63 allowable race combinations

7

Ethnicity

2 (Hispanic/Not)

1

Relationship17 values

5

Total

44

308,745,538 people x 6 variables = 1,852,473,228 measurements
308,745,538 people x 44 bits
= 13,584,803,672 bits ≈ 1.7 GB18

2010 Census: Summary of Publications(approximate counts)
Publication
PL94-171 Redistricting
Balance of Summary File 1
Summary File 2
Public-use micro data sample
Lower bound on published statistics
Published Statistics/person
Recall: Collected variables/person:
Published Statistics/collected variable

Released counts
2,771,998,263
2,806,899,669
2,093,683,376
30,874,554
7,703,455,86225
625 ÷ 6 ≈ 4.2
19

Question:
Is it possible to run the statistical process in reverse?
Pre-specified
tabularsummaries:
PL94-171,
SF1, SF2

DRF
Raw data from
respondents:
Decennial
Response File

Reconstruction
Processes
1,852,473,228 collected values

Specialtabulations andpost-census
research(308,745,538 people x 6 variables/person)
Public data20

2003:
Database Reconstruction

Attacking statistical databases

22

Statistical agencies are trusted curators.
Respondents

Confidential
Database

Published Statistics

Age Sex Race/MS#

Median
Age

Mean
Age

8 FBS

Total

7

30

38

18 MWS

Women

4

30

33.5

24 FWS

Male

3

30

44

30 MWM

Black

4

51

48.5

36 FBM

White

3

24

24

66 FBM

Married4

51

54

84 MBM

Black F

3

36

36.7
23

This is the trusted curator model

Respondents

Confidential
Database

Published
Statistics

24

We now know “trusted curator” model is more complex.
Every data publication results in some privacy loss.

Respondents

Confidential
Database

Published
Statistics

Publishing too many statistics results in the compromise of
the entire confidential database.
25

Consider the statistics from a single household

Count

Median

Mean

Total

1

24

24

# Female

1

24

24

# white1

24

24Single12424White F1

24

24

24 yrs Female White Single (24 FWS)
26

Publishing statistics for this household alone would result in
an improper disclosure.

24 yrs Female White Single (24 FWS)CountMedian

Mean

Total

(D)

(D)

(D)

# Female

(D)

(D)

(D)

# white

(D)

(D)

(D)

Single

(D)

(D)

(D)

White F

(D)

(D)

(D)

(D) Means suppressed toprevent an improper disclosure.
27

In the past, statistical agencies aggregated data frommany households together into a single publication.

Count

Median
Age

Mean
Age

Total

7

30

38

# Female

4

30

33.5

# male330

44# black

4

51

48.5

# white3

24

24

Married4

51

54Black F

3

36

36.7

28

We now know that this publication can bereverse-engineered to reveal the confidential database.

66 FBM & 84 MBM

30 MWM & 36 FBM

8 FBS

18 MWS

24 FWSCountMedian

Mean

Total

7

30

38

# Female

4

30

33.5

# male330

44# black

4

51

48.5

# white3

24

24

Married4

51

54Black F

3

36

36.7

This table can be expressed by 164 equations.
Solving those equations takes
29
0.2 seconds on a 2013 MacBook Pro.

The problem with publishing fewer statistics:
it’s hard to know how many statistics is “too many.”
Count

Median

Mean

Total

7

30

38

12 MWS# Female

4

30

33.5

24 FWS

24 FWS# male330

4430 MWM

30 MBM# black

4

51

48.5

36 FBM

36 FWM# white3

24

24

66 FBM

72 FBM

Married4

51

54

84 MBM

90 MBM

Black F

3

36

36.7

Solution #1

Solution #2

8 FBS

2 FBS

18 MWS

30

Here’s what the system looks like:
Variables:

Constraints:#define FEMALE 0#define MALE
1;; there are three males(= (+ (if (= S1 MALE) 1 0)

(int S1 FEMALE MALE)(int S2 FEMALE MALE)(if (= S2 MALE) 1 0)

(int S3 FEMALE MALE)(int S4 FEMALE MALE)(if (= S4 MALE) 1 0)

(if (= S3 MALE) 1 0)
(if (= S5 MALE) 1 0)
(if (= S6 MALE) 1 0)

(int S5 FEMALE MALE)(int S6 FEMALE MALE)(int S7 FEMALE MALE)(if (= S7 MALE) 1 0))
3)31

2010 Census: Summary of Publications(approximate counts)
Publication
PL94-171 Redistricting
Balance of Summary File 1
Summary File 2
Public-use micro data sample
Lower bound on published statistics
Published Statistics/person
Recall: Collected variables/person:
Published Statistics/collected variable

Released counts
2,771,998,263
2,806,899,669
2,093,683,376
30,874,554
7,703,455,86225
625 ÷ 6 ≈ 4.2
32

We performed a database reconstruction and re-identification
attack for all 308,745,538 people in 2010 Census
1. Reconstructed 308,745,538 microdata records.
2. Used 4 commercial databases of the 2010 US populationacquired 2009-2011 in support of the 2010 Census
Commercial database had: NAME, ADDRESS, AGE, SEX

3. Linked reconstructed records to the commercial database records
Linked database has: NAME, ADDRESS, AGE, SEX , ETHNICITY & RACE
Link rate:45%

4. Compared linked database to Census Bureau confidential data

Question: How often did the attack get the all variables including race andethnicity right?
Answer:38% (17% of US population)
33

Our attack is good, but not perfect.
An outside attacker would have a harder time.
We confirmed re-identification of 38% (17% of US population)
We did not reconstruct families.
We did not recover detailed self-identified race codes

An outside attacker:
Would not know which re-identifications are correct.
An outside attacker would need to confirm with another external data source.

34

The protection system used in 2000 and 2010
relied on swapping households.
Some households were swapped with other households
Swapped households had the same size.
Swapping limited to within each state.

Confidentiality Mechanism

Disadvantages:

Town 1

Swap rate and details of swapping not disclosed.
Privacy protection was not quantified.
Impact on data quality not quantified.

Swapping is called a “Disclosure Avoidance” technique.
It’s job is to prevent improper disclosures.

Town 2
Any State35

We now know that the disclosure avoidance techniques
we used in the 2010 Census were flawed
We released exact population counts for blocks, tracts and counties.
We did not swap 100% of the households
We released ≈25 statistics per person,
but only collected six pieces of data per person:
Block • Age • Sex • Race • Ethnicity • Relationship to Householder

The Census Bureau did the best possible in 2010.
The math for protecting a decennial census using formal privacy
did not [yet] exist.
36Faced with “database reconstruction,”
statistical agencies have just two choices

Option #1: Publish fewer statistics.
Option #2: Publish statistics with less accuracy.

37

Faced with “database reconstruction,”
statistical agencies have just two one choice

Option #1: Publish fewer statistics.
Option #2: Publish statistics with less accuracy.

38

39

Cynthia Dwork1 , Frank McSherry1 , Kobbi Nissim2 , and Adam Smith3?
Microsoft Research, Silicon Valley. {dwork,mcsherry}@microsoft.com
2006:
Ben-Gurion University. kobbi@cs.bgu.ac.il
Weizmann Institute of Science. adam.smith@weizmann.ac.il
Differential Privacy
1

Calibrating Noise to Sensitivity in Private Data
Analysis2

Cynthia Dwork1 , Frank McSherry1 , Kobbi Nissim2 , and Adam Smith3?

3

Abstract. We continue a line of research initiated in [10, 11] on privacypreserving statistical databases. Consider a trusted server that holds a
database of sensitive information. Given a query function f mapping
databases to reals, the so-called true answer is the result of applying
f to the database. To protect privacy, the true answer is perturbed by
the addition of random noise generated according to a carefully chosen
distribution, and this response, the true answer plus noise, is returnedto the user.
P Previous work focused on the case of noisy sums, in which f =i g(xi ), where xi denotes the ith row of the database and g maps
database rows to [0, 1]. We extend the study to general functions f ,proving that privacy can be preserved by calibrating the standard deviation of the noise according to the sensitivity of the function f . Roughly
speaking, this is the amount that any single argument to f can change its
output. The new analysis shows that for several particular applications
substantially less noise is needed than was previously understood to be
the case.
The first step is a very clean characterization of privacy in terms ofindistinguishability of transcripts. Additionally, we obtain separation results showing the increased value of interactive sanitization mechanisms
over non-interactive.

1

Introduction

1

Microsoft Research, Silicon Valley. {dwork,mcsherry}@microsoft.com
2
Ben-Gurion University. kobbi@cs.bgu.ac.il
3
Weizmann Institute of Science. adam.smith@weizmann.ac.il

Abstract. We continue a line of research initiated in [10, 11] on privacypreserving statistical databases. Consider a trusted server that holds a
database of sensitive information. Given a query function f mapping
databases to reals, the so-called true answer is the result of applying
f to the database. To protect privacy, the true answer is perturbed by
the addition of random noise generated according to a carefully chosen
distribution, and this response, the true answer plus noise, is returnedto the user.
P Previous work focused on the case of noisy sums, in which f =i g(xi ), where xi denotes the ith row of the database and g maps
database rows to [0, 1]. We extend the study to general functions f ,proving that privacy can be preserved by calibrating the standard deviation of the noise according to the sensitivity of the function f . Roughly
speaking, this is the amount that any single argument to f can change its
output. The new analysis shows that for several particular applications
substantially less noise is needed than was previously understood to be
the case.
The first step is a very clean characterization of privacy in terms ofindistinguishability of transcripts. Additionally, we obtain separation results showing the increased value of interactive sanitization mechanisms
over non-interactive.

1

Introduction

We continue a line of research initiated in [10, 11] on privacy in statistical
databases. A statistic is a quantity computed from a sample. Intuitively, if thedatabase is a representative sample of an underlying population, the goal ofa privacy-preserving statistical database is to enable the user to learn properties of the population as a whole while protecting the privacy of the individual
contributors.
We assume the database is held by a trusted server. On input a query function
f mapping databases to reals, the so-called true answer is the result of applying f
to the database. To protect privacy, the true answer is perturbed by the addition?

Supported by the Louis L. and Anita M. Perlman Postdoctoral Fellowship.

Differential privacy gives us a mathematical approachfor balancing accuracy and privacy loss
Tradeoff between Accuracy and Privacy Loss
Accuracy 0-100%

100%
90%
80%
70%

No privacy

60%
50%
40%
30%
20%
10%
0%

No accuracy
Privacy Loss (epsilon): 0 to ∞

“Differential privacy” is really two things
1 – A mathematical definition of privacy loss.
2 – Specific mechanisms that allow us to:üAdd the smallest amount of noise necessary for a given privacy outcomeüStructure the noise to have minimal impact on the more important statistics

42

24 yrs Female White Single (24 FWS)NOISE BARRIER

Differential privacy — the big idea:
Use “noise” to create uncertainty about private data

35 yrs Female Black Single (35 FBS)
Impact of the noise ≈ impact of a single person
Impact of noise on aggregate statistics
decreases with larger population.
43

1 person age 22

1 person age 22

1 person age 22

NOISE BARRIER

Each time we go through the noise barrier,
we get a different number

Age

Count

25

3

17

1

27

-1
44

1 person age 22

1 person age 22

1 person age 22

NOISE BARRIER

Epsilon controls the amount of noise

Epsilon

Age

100

22

1.0

24

0.1

-115
45

1 person age 22

10 people, all age 22

100 people, all age 22

NOISE BARRIER

Understanding the impact of “noise:”
Statistics based on 10,000 experiments, epsilon=1.0
5,000 (50%) runs

9,500 (95%) runs

Median(age): 9 → 73

Median(age): 0→ 104

Median(age): 17 → 61

Median(age): 0→ 103

Median(age): 21 → 22

Median(age): 21→ 22
46

1 person age 22

10 people, all age 22

100 people, all age 22

NOISE BARRIER

The noise also impacts the person counts
5,000 (50%) runs

9,500 (95%) runs

Median(age): 9 → 73
# people: -9 → 11

Median(age): 0→ 104# people: -29 → 30

Median(age): 17 → 61
# people: 0 → 20

Median(age): 0→ 103# people: -19 → 38

Median(age): 21 → 22
# people: 90 → 110

Median(age): 21→ 22# people: 71 → 129
47

The 2020 census and differential privacy

48

BARRIERDAS allows the Census Bureau to enforce
global confidentiality protections

CensusUnedited
File

CensusEdited File

Microdata
Detail File

Disclosure
Avoidance System

NOISE

Decennial
Response
File

GlobalConfidentiality
Protection Process

Pre-specified
tabularsummaries:
PL94-171, DHC,
DDHC, AIANNH

Privacy-loss Budget,
Accuracy Decisions

Specialtabulations andpost-census
research

49

The Census disclosure avoidance system uses differential
privacy to defend against an accurate reconstruction attack
Provable bounds on the accuracyof the best possible databasereconstruction given the released
tabulations.
Algorithms that allow policy
makers to decide the trade-off
between accuracy and privacy.

Data accuracy

Differential privacy provides:

Privacy loss budget (ε)

Final privacy-loss budget determined by Data Stewardship Executive Policy Committee (DSEP)
with recommendation from Disclosure Review Board (DRB)
Pre-Decisional

50

The Disclosure Avoidance System relies on injects
formally private noise
Advantages of noise injection with formal privacy:
Transparency: the details can be explained to the public
Tunable privacy guarantees
Privacy guarantees do not depend on external data
Protects against accurate database reconstruction
Protects every member of the population

Challenges:

GlobalConfidentiality
Protection Process
Disclosure
Avoidance SystemεEntire country must be processed at once for best accuracy
Every use of confidential data must be tallied in the privacy-loss budget
51

There was no off-the-shelf system for applying
differential privacy to a national census
We had to create a new system that:
Produced higher-quality statistics at more densely populated geographies
Produced consistent tables
We created new differential privacy algorithms and processing systems that:
Produce highly accurate statistics for large populations (e.g. states, counties)
Create protected microdata that can be used for any tabulation without
additional privacy loss
Fit into the decennial census production system
52

How the 2020 System Works:
High-level Overview
Every record in the population may be modified
But modifications are bounded by the global privacy budget.

Records in the tabulation data have no exact counterpart in theconfidential data
There is no one-to-one mapping between CEF and MDF records.

Explicitly protected tabulations (PL-94 and SF-1) have provable,
public accuracy levels
53Basic approach for a DP Census
Treat the entire census as a set of queries on histograms.
Select the specific queries to measure
Six geolevels (nation, state, county, tract, block group, block)Thousands of queries per geounit
Billions of queries overall
Histogram has billions of cells

54Protecting the data
Measurements

εNOISE BARRIER

Confidential
records

Noisy
Measurements

Microdata55

First effort: The block-by-block algorithm
Independently protect each block (parallel composition)

Disclosure
Avoidance System

8 million protected
blocksNOISE BARRIER

8 million blocks

Measure queries for each block; privatize queries; convert results back to microdata
56

Tested withdata from 1940
1940 hierarchy:• Nation• State• County• Enumeration
District
Download fromusa.ipums.org
57

Block-by-block algorithm (also called bottomUp)
Mechanism:
Select, Measure, Reconstruct separately on each block

Advantages:

Simple and easy to parallelize
Privacy cost does not depend on # of blocks
Releasing DP for one block has same cost as releasing for all

Disadvantages

Significant error at higher level
Error adds up
Variance of each geounit is proportional to the number of blocks it contains
58

New algorithm: the top-down mechanism
Step 1: Generate national histogram without geographic
identifiers.
Step 2: Allocate counts in histogram to each geography“top down.”
National-level measurements - ℇnat
State-level histograms - ℇstate
County-level histograms - ℇcounty
Tract-level histograms - ℇtract
Block-group level histograms - ℇblockgroup
Block-level histograms - ℇblockℇ= ℇnat + ℇstate + ℇcounty + ℇtract + ℇblockgroup + ℇblock59

The top-down algorithm…
Using ℇstate generate state histograms:
&
&
&
"$%
"$'
"()
𝐻
,𝐻
,… 𝐻
All histograms are consistent:0&""∑+∈+-.-/+ 𝐻+ = 𝐻

Repeat for each geolevel60New algorithm: the top-down mechanism

330M records

1 National
histogram
52 “state”
Histograms

Note: block groups are omitted for clarity

National
Histogramεε3142 “county”
histograms

ε75,000 tract
histogramsε

8 M block grouphistogramsε

8 M blockhistogramsε

BARRIER

Tabulated
Confidential data

52 state
histograms
3,142 county
histograms
75,000 census tract
histograms

NOISE

EditedConfidential data

1 M block group histograms

8 M block histograms

61

Post-process for non-negativity andTabulatedconsistency
EditedConfidential data

Confidential data

52 “state”
Histograms

Note: block groups are omitted for clarity

National
Histogramεε3142 “county”
histograms

ε75,000 tract
histogramsε

8 M block grouphistogramsε

8 M blockhistogramsε

BARRIER

1 National
histogram

52 state
histograms
3,142 county
histograms
75,000 census tract
histograms

NOISE

330M records

1 M block group histograms

8 M block histograms

62

Top-down framework: alternative view
National histogram equivalent to table of records:
Age

Race

Sex

Ethnicity

HHGQ

Extend to state-level histograms:
Age

Race

Sex

Ethnicity

Sex

Ethnicity

HHGQ

State

Add county:
Age

Race

HHGQ

State

CountyThen add tract, block group, block63

Top-Down Framework
Advantages:
Easy to parallelize
Each geo-unit can have its own strategy selection
We use High Dimensional Matrix Mechanism [MMHM18]
Parallel composition at each geo-level
Reduced variance for many aggregate regions
Sparsity discovery• e.g. very few 100+ aged people who combine 5 races• Once to—down decide a region has no such records in county A, no subregion

will have them.

64Post-processing
Each distribution involves (at least) two runs of an optimizer
L2 solve:
Generates nonnegative fractional demographics histogram
State histograms must add up to National histogram (etc.)

L1 solve:

Converts fractional histogram to non-negative integer histogram
Maintain consistency: child histograms must add up to parent
Integer solutions are fast to find65

Evaluating the algorithm
We released runs of the top-down algorithm on data from the 1940 Census.
Epsilon values 0.25 .. 8.0
Multiple runs at each value of epsilon.

Caveats:
1940 data had 4 geography levels: Nation, State, County, Enumeration District.
2020 data has 6 levels: Nation, State, County, Tract, Block Group and Block.
1940 data has 6 races races / 2020 data has 63 race combinations
1940 data has no citizenship (Citizen or non-Citizen)

66Top-Down: much
more accurate!

67

68

69

Note: The simulator
uses hypothetical(fake) data provided
by the user.
70

Two public policy choices:

What is the correct value of epsilon?
Where should the accuracy be allocated?

71

Managing the Tradeoff

72

Policy Issue: Setting Epsilon
Production Possibilities for Alternative Mechanisms
1.0
0.9
0.8

Mechanism 3

Data Accuracy

0.7
0.6
0.5

Mechanism 2

0.4
0.3
0.2

Mechanism 1

0.1
0.0
0.0

0.5

1.0

1.5

2.0

2.5

3.0

3.5

4.0

4.5

5.0

5.5

6.0

Privacy-loss Budget73

Marginal Social
Benefit Curve

Social Optimum:
MSB = MSC
(0.25, 0.64)

Production
Technology

74

Policy Decisions: Setting privacy loss budget (𝝴)Global privacy loss budget
Geographic levels
Fraction of 𝝴 allocated to each level

TablesFraction of 𝝴 allocated to each table or relationship75

Policy Issues for the 2020 Census:
Invariants
For the 2018 End-to-End test, policy makers wanted exact counts:
Number of people on each block
Number of people on each block of voting age
Number of residences & group quarters on each block

We implemented invariants before we understood their mathematical impact on
differential privacy semantics. We then scaled back to four invariants:
C1: Total population (invariant at the county level for the 2018 E2E)
C2: Voting-age population (population age 18 and older) (eliminated for the 2018 E2E)
C3: Number of housing units (invariant at the block level)
C4: Number of occupied housing units (invariant at the block level)
C5: Number of group quarters facilities by group quarters type (invariant at the block level)

76

Scientific Issues for the 2020 Census:
Person-Household Joins
The Census creates two kinds of tables:
Person tables
Household tables

We can create P & H today.
We are working on P x H and Detailed P, H
Q(P): # of men living on a block.
Q(H): # of occupied houses on a block.
Q(P x H): # of children in houses headed by a single man.
77

Scientific Issue for any use of DP:
Quality Metrics
What is the measure of “quality”
or “utility” in a complex data
product?
Options:
L1 error between “true” data set
and “protected” data set
Impact on an algorithm that uses
the data (e.g., redistricting andVoting Rights Act enforcement)
78

The Choice Problem for Redistricting Tabulations
Is More Challenging
In the redistricting application, the fitness-for-use is based on :Supreme Court one-person one-vote decision (All legislative districts must haveapproximately equal populations; there is judicially approved variation)

Is statistical disclosure limitation a “statistical method” (permitted by Utah v.
Evans) or “sampling” (prohibited by the Census Act, confirmed in Commerce v.
House of Representatives)?
Voting Rights Act, Section 2: requires majority-minority districts at all levels,
when certain criteria are met

The privacy interest is based on:
Title 13 requirement not to publish exact identifying information
The public policy implications of uses of detailed race, ethnicity and citizenship
79Organizational Challenges
Process documentation
All uses of confidential data need to be tracked and accounted.

Workload identification
All desired queries on MDF should be known in advance.
Required accuracy for various queries should be understood.
Queries outside of MDF must also be pre-specified

Correctness and Quality control
Verifying implementation correctness.
Data quality checks on tables cannot be done by looking at raw data.
80Data User Challenges
Differential privacy is not widely known or understood.
Many data users want highly accurate data reports on small areas.
Some are anxious about the intentional addition of noise.
Some are concerned that previous studies done with swapped data might not
be replicated if they used DP data.

Many data users believe they require access to Public Use Microdata.
Users in 2000 and 2010 didn’t know the error introduced by swapping andother protections applied to the tables and PUMS.
81

Concerns and Responses

82Redistricting and Exact Counts
In the US, legislative districts must have equal size.
Decennial Census counts of each block are the “official counts.”

Some data users are concerned that adding noise to thecounts will make them unfit for use.
However:

Evaluation of districts is based on official decennial counts; thesedata are used for 10 years.
Noise added by DP is significantly less than noise added by otherstatistical methods currently in use
83

Ruggles Concerns
Differential privacy is not a measure of identifiability
Differential privacy does not measure disclosure risk
“Differential Privacy is not concerned with re-identification of
respondents•••“DP prohibits revealing characteristics of an individual even if theidentity of that individual is effectively concealed“This is a radical departure from established census law andprecedent“The Census Bureau has been disseminating individual-level
characteristics routinely since the first microdata in 1962
84

Organized attack on the move todifferential privacy
Concerns:• “Differential privacy will degrade the quality of data available
about the population, and will probably make scientificallyuseful public use microdata impossible• The differential privacy approach is inconsistent with thestatutory obligations, history, and core mission of the Census
Bureau”

85Analysis of population variancesDavid Van Riper & Tracy Kugler, IPUMS (APDU 2019)86

Analysis of population variancesDavid Van Riper & Tracy Kugler, IPUMS (APDU 2019)87

Analysis of population variancesDavid Van Riper & Tracy Kugler, IPUMS (APDU 2019)88

practice
For more
information…

DOI:10.1145/3287287

Article development led byqueue.acm.org

These attacks on statistical databases
are no longer a theoretical danger.
BY SIMSON GARFINKEL, JOHN M. ABOWD,
AND CHRISTIAN MARTINDALE

Understanding
Database
Reconstruction
Attacks on
Public Data
IN 2020, THE U.S. Census Bureau will conduct theConstitutionally mandated decennial Census ofPopulation and Housing. Because a census involves
collecting large amounts of private data under thepromise of confidentiality, traditionally statistics
are published only at high levels of aggregation.
Published statistical tables are vulnerable to databasereconstruction attacks (DRAs), in which the underlying
microdata is recovered merely by finding a set of
microdata that is consistent with the publishedstatistical tabulations. A DRA can be performed by using
the tables to create a set of mathematical constraints
and then solving the resulting set of simultaneous
equations. This article shows how such an attack can beaddressed by adding noise to the published tabulations,46

COMMUNICATIONS OF THE ACM

so the reconstruction no longer resultsin the original data. This has implications for the 2020 census.
The goal of the census is to countevery person once, and only once, andin the correct place. The results areused to fulfill the Constitutional requirement to apportion the seats in
the U.S. House of Representatives
among the states according to theirrespective numbers.
In addition to this primary purposeof the decennial census, the U.S. Congress has mandated many other uses
for the data. For example, the U.S. Department of Justice uses block-byblock counts by race for enforcing the
Voting Rights Act. More generally, theresults of the decennial census, combined with other data, are used tohelp distribute more than $675 billion in federal funds to states and local organizations.
Beyond collecting and distributing
data on U.S. citizens, the Census Bureau is also charged with protecting theprivacy and confidentiality of survey responses. All census publications must
uphold the confidentiality standard
specified by Title 13, Section 9 of the
U.S. Code, which states that Census Bureau publications are prohibited fromidentifying “the data furnished by any
particular establishment or individual.” This section prohibits the Census
Bureau from publishing respondents’names, addresses, or any other information that might identify a specificperson or establishment.
Upholding this confidentiality requirement frequently poses a challenge, because many statistics caninadvertently provide information in
a way that can be attributed to a particular entity. For example, if a statistical agency accurately reports there
are two persons living on a block andthe average age of the block’s residents is 35, that would constitute an
improper disclosure of personal information, because one of the residents could look up the data, subtract their contribution, and infer
the age of the other.

Can a set of equations keep
U.S. census data private?
By Jeffrey Mervis
ScienceJan. 4, 2019 , 2:50 PM| MARCH 2019 | VOL. 62 | NO. 3

Communications of ACM March 2019
Garfinkel & Abowd

http://bit.ly/Science2019C1
89

More Background on the 2020 Disclosure Avoidance
SystemSeptember 14, 2017 CSAC (overall design)
https://www2.census.gov/cac/sac/meetings/2017-09/garfinkel-modernizing-disclosureavoidance.pdf
August, 2018 KDD’18 (top-down v. block-by-block)https://digitalcommons.ilr.cornell.edu/ldi/49/
October, 2018 WPES (implementation issues)
https://arxiv.org/abs/1809.02201
October, 2018 ACMQueue (understanding database reconstruction)
https://digitalcommons.ilr.cornell.edu/ldi/50/ or
https://queue.acm.org/detail.cfm?id=3295691
Memorandum 2019.13: Disclosure Avoidance System Design Parameters
https://www.census.gov/programs-surveys/decennial-census/2020-census/planningmanagement/memo-series/2020-memo-2019_13.html
90