Miranda Christ* & Sarah Radway^

Steven M. Bellovin*

*Columbia University, ^Tufts University

Comparative Analysis of Differential Privacy and Swapping Methods In The Context of The U.S. Census

Background

What are swapping and DP? Why is privacy important?

Theoretical results

In a theoretical model, how do we expect swapping to behave?

Experimental approach

Our method for empirically comparing swapping and DP

Experimental findings

For swapping, good privacy means poor accuracy, especially for diverse counties. DP performs better across varying diversity levels.

Roadmap

‹#›

Background

U.S. Decennial Census: Demographic info collected every 10 years

Data uses: redistricting, funding decisions (Medicaid, Head Start, SNAP, more...)

Statutory Requirement (13 U.S.C. §9(a)(2)): Census data must not be personally identifiable

Furthermore, lack of privacy may hurt participation and thus accuracy

In 2010, data was de-identified using swapping

In 2020, data was de-identified using differential privacy

Background: Census

How can we balance data utility and privacy?

‹#›

The U.S. Decennial Census occurs every 10 years and involves collecting demographic information pertaining to Americans such as age, sex, and race. This data is used for a variety of important decisions, including redistricting and allocation of funds in programs such as Medicaid. The U.S. Census Bureau is statutorily mandated to ensure that this data is not personally identifiable. This privacy is important for accuracy as well– a lack of privacy may hurt participation and thus accuracy. In 2010, the Census Bureau de-identified its data using swapping. In 2020, it used differential privacy. In both of these methods, higher accuracy comes with lower privacy.

Given the importance of both accuracy and privacy in census data, this begs the question: how can we balance data utility and privacy?

Swapping

‹#›

Exchange of data about individuals between groups, in order to de-identify

Swap selection can be random or based upon a threshold of similarity

swap rate: proportion of 

data to be swapped

Prioritizes unique entries

Swapping, the de-identification method used by the Census Bureau in 2010, involves the exchange of data about individuals between groups. In the figure on the right, the green house in the bottom group is being swapped with the yellow house in the top group. 

When we swap the green house and the yellow house, we exchange some subset of their data. For example, we may swap their ages and races.

Add random noise (parametrized by ε) to make dataset private

Usually mean 0 noise, with variance depending on ε

Privacy guarantee: changing one person’s data only changes the de-identified data by “a little bit”

“A little bit” depends on ε

Lower ε: lower accuracy; higher privacy. Higher ε: higher accuracy; lower privacy

Differential Privacy
| Age range | Sex | Race  | Pop. count |
|-----------|-----|-------|------------|
| 15-30     | F   | White | 126        |
| 30-45     | M   | Asian | 89         |
| ... | Pop. count |
|-----|------------|
| ... | 131        |
| ... | 83         |

add noise

‹#›

Differential privacy, the de-identification method used by the Census Bureau in 2020, involves adding random noise parametrized by a variable epsilon to counting queries over a dataset. This random noise usually has mean 0, with variance depending on epsilon. If the noise is structured a certain way, we can achieve a mathematical privacy guarantee known as differential privacy. This means that changing one person’s data only changes the de-identified data by “a little bit,” where “a little bit” depends on epsilon. The figure below shows an example of a DP algorithm operating on demographic data. On the left, we have a table with the population counts of various groups. The first group has age range 15-30, sex F, race White, and population count 126. The de-identified data for this subgroup has count 131. Here, the DP mechanism adds small random noise. These de-identified counts are close to the true counts, but far enough to prevent learning about any individual.

There is a clear tradeoff between accuracy and privacy, parametrized by epsilon. Lower epsilon means lower accuracy and higher privacy, whereas higher epsilon means higher accuracy and lower privacy.

Privacy Concerns

Researchers reconstructed 46% of (swapped) 2010 census data 

Accuracy Concerns

Effect of DP on minority groups and small towns 

National Congress of American Indians

Utility of DP for redistricting (Alabama v. U.S. Dept of Commerce)

Court case brought by Alabama arguing that DP-produced data is too inaccurate

Privacy and Accuracy Concern: How should the epsilon value be chosen for the Census Bureau’s DP implementation (TopDown Algorithm)?

Controversy and Context

‹#›

Be up to date on alabama (possibly new) case

Report published by NCAI

Just say court case not district court case

We especially focus on minority groups

There is ongoing debate surrounding the Census Bureau’s recent decision to switch from swapping to differential privacy. On one hand, the privacy provided by swapping has been shown to be insufficient. Researchers at the census bureau were able to reconstruct 46% of 2010 census data, which was de-identified using swapping. On the other hand, there are numerous concerns about the accuracy of differential privacy. We were especially interested in addressing a concern raised in a report published by the National Congress of American Indians about the effect of DP on minority groups and small towns. You’ll see later that we designed our experiments with underrepresented minorities in mind. The accuracy of DP has also been questioned in its use for redistricting; this is the focus of a court case brought by Alabama against the U.S. Dept of Commerce. 

In addition to these privacy and accuracy issues, there is concern about how the epsilon value of the census bureau’s DP mechanism should be chosen to satisfy both privacy and accuracy needs. 

We work towards better understanding these issues by analyzing the privacy and accuracy of DP and swapping.

Two flavors of analysis:

Theory

Analyze how we expect swapping to behave

Not implementation dependent; results generalize beyond the U.S. census

Experiments

Recreate census-like data and simulate their swapping and DP algorithms

Compare the accuracy and privacy of DP and swapping

Our Approach

‹#›

“Filling in a gap of communication” 

Mention that CB can’t publish swapping implementation bc of privacy concerns

Theoretical Results

For swapping: if a subpopulation differs more from global pop., then there is a higher expected error for counting queries

This expected error increases further as swap rate increases

Generally: smaller, more diverse subpopulations have exponentially more unique entries than larger or more homogeneous subpopulations

Theoretical Results

higher expected error

lower expected error

‹#›

This means that we expect that: 

Under-representation created by swapping should be more extreme in subpopulations with more different race distributions (compared to US distr.)

Swapping methods that prioritize unique entries will result in further accuracy degradation in minority subpopulations

These are theorems! With proofs

Experimental Approach

 Why do we need synthetic data?

Census data releases de-identified query data, not true data

How did we make our synthetic data?

Used de-identified 2010 US Census block group data

Fit true distribution for sex, age, household size & tenure

Used exact de-identified data for race (to represent minorities effectively)

Synthetic Data
| Age | Sex | Race | Household Size | Household Tenure |
|-----|-----|------|----------------|------------------|
|     |     |      |                |                  |

‹#›

Method: Replications of Swapping and DP algorithms to the best of our ability

Why? Swapping algorithm can’t be disclosed, DP algorithm is too expensive 

Several implementations (swapping similarity thresholds & DP-buckets) of each algorithm for comprehensiveness

Metrics: For minority and overall population representation

Accuracy: two metrics that show minority and overall representation

Privacy: Linkage attack with public dataset

Method & Metrics

‹#›

Explain threshold and group size

Experimental Findings

Why is it hard to directly compare privacy of DP and swapping?

DP: Provides privacy guarantee, can only learn about the group

“I know that most people with the zip code 10027 were white. Because your zip code is 10027, you are probably white.”

Swapping: Does not provide privacy guarantee

“I see that there is only one person with a zip code of 10027 in both datasets. Thus, if your zip code is 10027, this must be your data, and you must be white.” 

Privacy attacks of this type fundamentally CANNOT WORK against DP

DP Privacy

‹#›

X-axes: de-identification mechanism metrics

L → R represents most → least private

Y-axis: represents accuracy (or privacy)

Closer to 0 represents better accuracy (or privacy)

Breaking Down The Figures 

‹#›

Privacy

NOT DIVERSE COUNTY

DIVERSE COUNTY

We simulate a linkage attack, matching entries from a de-identified database to a public database.

We try to determine whether an individual has some attribute (e.g. is Hispanic)

‹#›

Privacy

MINORITY POPULATION

TOTAL POPULATION

‹#›

MEAN SQUARED ERROR (MSE)

Considers total population

Accuracy

MU-SMOOTHED KL-DIVERGENCE (μ-KL)

Weighs minority populations; see Cummings et al.

‹#›

NOT DIVERSE COUNTY (μ-KL)

Accuracy

DIVERSE COUNTY (μ-KL)

‹#›

For swapping, good privacy means poor accuracy, especially for diverse counties. 

DP, however, performs better across varying diversity levels.

Privacy & Accuracy

‹#›

While both swapping & DP mechanisms could produce comparable accuracy:

Swapping mechanisms:	

Posed a significant risk of re-identification

No privacy guarantee: bad utility != good privacy, and vice versa

Diverse groups suffered worse accuracy AND privacy, disproportionately impacting minorities

Differentially private mechanisms:

Provide a direct relationship/guarantee between utility and privacy

Performed consistently across groups of varying diversity 

Final Remarks

Sarah Radway, sarah.radway@tufts.edu

Miranda Christ, mchrist@cs.columbia.edu

‹#›

Example

‹#›

TRUE DATA
| 2 |  |
|---|--|
| 1 |  |
| 2 |  |
| 2 |  |
| 3 |  |
|---|--|
| 0 |  |
| 1 |  |
| 3 |  |

SWAPPING
| 2 |  |
|---|--|
| 1 |  |
| 2 |  |
| 2 |  |

DP
| 3 |  |
|---|--|
| 0 |  |
| 1 |  |
| 3 |  |

Mention that we look at data in QUERY FORMAT (show that those are kind of queries, but looking at multiple variables)

# image1.png

# image2.png

# image4.png

# image7.png

# image5.png

# image3.png

# image8.png

# image6.png