AA YYYY

# Statistical Data Privacy: A Song of Privacy and Utility

Aleksandra Slavković1 and Jeremy Seeman2 1Department of Statistics, The
Pennsylvania State University, University Park, PA, 16802; email:
<EMAIL_ADDRESS>2Department of Statistics, The Pennsylvania State University,
University Park, PA, 16802, email<EMAIL_ADDRESS>ORCID: 0000-0003-3526-3209

###### Abstract

To quantify trade-offs between increasing demand for open data sharing and
concerns about sensitive information disclosure, statistical data privacy
(SDP) methodology analyzes data release mechanisms which sanitize outputs
based on confidential data. Two dominant frameworks exist: statistical
disclosure control (SDC), and more recent, differential privacy (DP). Despite
framing differences, both SDC and DP share the same statistical problems at
its core. For inference problems, we may either design optimal release
mechanisms and associated estimators that satisfy bounds on disclosure risk,
or we may adjust existing sanitized output to create new optimal estimators.
Both problems rely on uncertainty quantification in evaluating risk and
utility. In this review, we discuss the statistical foundations common to both
SDC and DP, highlight major developments in SDP, and present exciting open
research problems in private inference.

###### doi:

10.1146/((please add article doi))

###### keywords:

statistical data privacy, statistical disclosure control, formal privacy,
differential privacy, inference

††journal: Xxxx. Xxx. Xxx. Xxx.

###### Contents

  1. 1 INTRODUCTION
    1. 1.1 Statistical data privacy
    2. 1.2 Notation and Problem Formulation
  2. 2 Statistical disclosure control (SDC)
    1. 2.1 SDC methods
    2. 2.2 Disclosure risk measures (DRMs)
  3. 3 Differential privacy (DP)
    1. 3.1 General setup
    2. 3.2 DP Release Mechanisms
      1. 3.2.1 Primitive Elements
      2. 3.2.2 Post-processing and Composition Techniques
  4. 4 Data Utility under SDP
    1. 4.1 Specific utility and the design approach
    2. 4.2 General utility and the adjustment approach
    3. 4.3 Statistical properties of RMs
    4. 4.4 Risk and model misspecification
  5. 5 The Fable of the Westerosi Census
    1. 5.1 Counting queries with SDC
    2. 5.2 Counting queries with DP
  6. 6 The Morals of Our Fable
  7. 7 Discussion & Future Directions
    1. 7.1 Comparing SDC and DP: Quantifying Risk
    2. 7.2 Comparing SDC and DP: Quantifying Utility and Uncertainty
    3. 7.3 Challenges in Schema Choice and Data Generation
    4. 7.4 Privacy and other ethical dimensions of data sciences
    5. 7.5 Closing the Gap Between Theory and Practice
  8. 8 Conclusion

##  1 INTRODUCTION

###  1.1 Statistical data privacy

Privacy and confidentiality (which we, in this review, synonymously refer to
as “privacy”) are widely viewed as an essential component of free societies
(Westin, 1968, Cohen, 2012). As large-scale data collection becomes more
commonplace, threats to individual’s data privacy grow ever more prominent
(e.g., see Dwork et al. (2017) for a survey of common attacks). Despite these
threats, many statisticians and data users, have a limited understanding of
what data privacy is and how it affects our work. Data privacy is often
synonymous with boilerplate procedures required to satisfy compliance
obligations (e.g., HIPPA, IRBs), an inconvenience to our normal operating
procedures. We may think that the solution is always anonymization, or the act
of removing personally identifying information (PII) from a database. Yet
statistical outputs (such as summary statistics and parameter estimates) pose
threats to individual disclosure, just as their inputs do through access to
confidential databases; this makes data privacy a methodological problem
beyond the known failures of anonymization alone (Ohm, 2009). Not all
statistics reveal the same information about individuals, and negotiating to
find the proper balance between privacy and utility (via uncertainty
quantification) is precisely where statistics has much to offer.

Statistical data privacy (SDP) aims to develop provable and usable data
privacy theory and methodology, by integrating tools from computer science and
statistics, to enable broad sharing of data across many different data context
and domains where it is desired or required that individual’s identities or
sensitive attributes are protected; e.g., census, health, genomic data, social
networks. SDP methods need to minimize privacy loss/disclosure risk of
sensitive information while at the same time preserve sufficient statistical
integrity of data in order to support valid inference (i.e., maximize data
utility). Two dominant frameworks in SDP, defined by different units of
analysis, make different conceptual trade-offs about adversarial assumptions,
disclosure risks that is privacy definitions, and their effects on downstream
inference. Statistical disclosure control (SDC) or limitation (SDL) methods
(e.g., Hundepool et al. (2012)) typically analyze individual databases,
whereas differential privacy (DP) methods (Dwork et al., 2014) analyze pairs
of databases in a shared schema (space of possible databases).

Despite good-faith attempts to unify these perspectives, some dating back to
the onset of DP, as discussed in Slavkovic (2013), SDC and DP research
perspectives still diverge. SDP scholars, data administrators, and
quantitative social scientists, it seems, have become more polarized as
proponents of one perspective or the other. In particular, the U.S. Census
Bureau’s decision to use DP has led to debates about the merits of either
approach (Abowd, 2021, Domingo-Ferrer et al., 2021). Furthermore, this
insularity has lead to growing gaps between theoretical developments, now
dominated by DP research, and applied methodology, now dominated by SDC
research. Such debates remain important, as they highlight the inherently
political nature of privacy-preserving data stewardship (Rogaway, 2015, Boyd &
Sarathy, 2022) and the way mathematical formalisms frame discussions about
privacy (Seeman, 2022). Still, SDC and DP share more similarities than
differences, and unifying these ideas can help mutually enrich future SDP
research.

In this article, we have three main goals: first, we highlight how SDC and DP
methods are built upon common statistical foundations that make different but
necessary compromises in conceptualizing privacy. Second, we discuss how SDP
is inseparable from the study of data generating processes in both designing
optimal private estimators and adjusting inferences for privacy preservation
given sanitized outputs. Third, we showcase open statistical problems
typically left unarticulated by theoretical SDP research, such as valid
statistical inference, computational tractability, and compatibility with
probability models. The paper is organized as follows: Sections 2 and 3 review
privacy quantification and release mechanisms/methods using SDC and DP,
respectively. Section 4 reviews inferential problems common to all SDP.
Section 5 presents a fabulistic case study applying SDP methodology to a small
population of the Westerosis. Finally, Section 7 discusses current research
practices and proposes future research directions to improve SDP research.

###  1.2 Notation and Problem Formulation

Throughout this paper, we use the following notation and terminology. Let
$\mathcal{X}$ be the sample space for one individual’s contributions to a
database, and let $\mathcal{D}=\mathcal{X}^{n}$ be the sample space for a
confidential database of $n$ individuals who have contributed their data. We
refer to $\mathcal{D}$ as the schema, or the space of possible databases. For
the purposes of this review, we assume the unit of observation refers to one
individual; however, similar methodology may be applied to groups, businesses,
or organizations.

Schemathe space of all possible confidential databases, $\mathcal{D}$. Output
space$\mathcal{S}$, the space of all possible statistical outputs. Release
mechanism (RM)a randomized function $S$ from $\mathcal{D}$ to $\mathcal{S}$
which sanitizes a database $D$’s output. Sanitized output$S(D)$, a statistical
output from a confidential database that has undergone some form of privacy
preservation.

In SDP, we release a statistic from a set of possible statistical outputs,
which we call the output space, $\mathcal{S}$. A release mechanism (RM),
defined by $S:\mathcal{D}\mapsto\mathcal{S}$, is a transformation of the
confidential data which produces the sanitized output, $S(D)$. SDP
characterizes the privacy risk and data utility properties of different RMs in
different scenarios. RMs may be either deterministic, i.e., $S(D)$ transforms
the confidential database $D$ according to a fixed function such as
aggregation, or randomized, i.e., $S(D)$ is a random variable that varies
conditionally on $D$ such as a statistic with randomized noise. Moreover,
$\mathcal{S}$ can take many forms, ranging from synthetic or tabular microdata
releases to summary statistics and model parameter estimates. SDC and DP
typically ask two different questions about the relationship between the RM
$S$ and the database $D\in\mathcal{D}$ with respect to disclosure risk:
MicrodataRecord-level data, either directly from the confidential database, or
synthetically generated from a model.

  1. 1.

SDC perspective: how does a particular statistical release $S(D)$ for a
particular database $D\in\mathcal{D}$ limit a particular measure of disclosure
risk, with respect to an individual or sub-population, dependent on existing
adversary knowledge?

  2. 2.

DP perspective: how can a statistical RM $S$ limit the ability for adversaries
to distinguish between similar databases $D,D^{\prime}\in\mathcal{D}$, such as
by only changing one individual’s contribution, within the same schema
$\mathcal{D}$?

In asking these questions, SDC and DP frame the problem of data privacy with
different conceptual compromises. SDC defines a narrow set of adversarial
contexts with the goal of quantifying a risk measure on a particular database,
which we refer to as an absolute measure of disclosure risk. Alternatively, DP
defines a broader set of adversarial contexts with the goal of quantifying a
measure of disclosure risk differences for any two similar databases within
the schema, which we refer to as a relative measure of disclosure risk.

SDC and DP are both on a spectrum of many possible ways to reason about SDP,
but both require negotiating between privacy and utility. As the number of
statistics released about any database increases, one can increasingly
reconstruct individual records contained in that database (Dinur & Nissim,
2003), (this problem, in part, motivated the start of DP research). At the
same time, assumptions about data generation processes and context-specificity
are necessary to provide meaningful data utility for any such statistical data
release (Kifer & Machanavajjhala (2011), A.K.A. ”no free lunch in data
privacy). Therefore it behooves us to investigate both SDC and DP
simultaneously.

For historical context, SDC methods have been used in official statistics
since the 1960s (McKenna, 2019). Early attempts to mathematically formalize
SDP date back to the seminal works of Tore Dalenius (Dalenius, 1977), who
viewed privacy as striving to reduce the harms of population-level statistical
inferences on individuals:

“If the release of the statistics $T(D)$ makes it possible to determine the
value [of confidential statistical data] more accurately than is possible
without access to $T(D)$, a disclosure has taken place.”

However, modern literature in both SDC and DP has shown that we cannot learn
anything about a population without also learning something about individuals
within that population (Dwork & Naor, 2010), and thus, the above definition is
unobtainable. As an oft-cited counterexample from Dwork et al. (2017),

“Releasing the fact that smoking and lung cancer are strongly correlated
reveals sensitive information about any individual known to smoke; however, we
do not consider this to be a privacy violation, as learning this correlation
has nothing to do with the use of that individual’s data.” Such concerns have
become a point of confusion due to misinterpretations of DP (Kenny et al.,
2021), leading some in DP to recently restate this commitment (Ullman, 2021).
Here, we further clarify that such a feature is central to the entire project
of SDP, not solely DP.

So, how does SDP becomes part of the broader project of statistical inference?
Figure 1 graphically illustrates where privacy preservation sits in
statistical inference, with a special focus on the social science context.
Because we are working with human data, we are prone to many error sources, as
often systematized by survey methodology (Groves et al., 2011). These errors
shape the structure of our confidential database records, even before any
sanitization is introduced.

Figure 1: Flowchart of SDP modeling for privacy risk and data utility
assessment

Note that we have two kinds of errors due to privacy, which enter the data
generating process at different stages and correspond to different database
trust models (Stoller, 2011). In the local model, privacy protecting errors
are introduced into the way users contribute to the confidential database
(Evfimievski et al., 2003). Alternatively, in the central model (Dwork et al.,
2014), user contributions are combined and transformed into sanitized
releases. Local models confer stronger privacy guarantees, because unlike the
central model, certain information about users is inaccessible even to the
data curator.

We argue that the statistical perspective is essential because both risk
assessment and inference on statistical output relies on the probabilistic
transformations throughout the data generating process that influence said
statistical output. Much of the focus on SDP research narrowly considers only
the privacy model, i.e., only the relationships between the confidential
database and the statistical outputs. By taking a bird’s eye view of this
process in Figure 1, we see many possible avenues for statistically motivated
privacy research. These research avenues depend on where we as statisticians
are involved in the process. Namely, do we have any say in choosing RM?
Depending on the answer, we can consider two different broad classes of
problems.

  1. 1.

Design problem: if $\mathcal{Q}$ is a class of RMs with the same privacy
guarantees, how do we find an optimal RM $S^{*}\in\mathcal{Q}$, associated
optimal estimator $\hat{\theta}^{*}(S^{*}(D))$ for some $\theta\in\Theta$, and
what is the uncertainty in $\hat{\theta}^{*}$?

  2. 2.

Adjustment problem: given a sanitized statistical result $S(D)$, how do we
find an optimal estimator $\hat{\theta}^{*}(S(D))$ for some $\theta\in\Theta$,
and what is the uncertainty in $\hat{\theta}^{*}$?

Both approaches will require different means of uncertainty quantification, as
we have more flexibility when we get to decide the form of $S$. Still, both
problem classes are equally important, since we as statisticians may be
working directly with confidential data, or we may be working with private
synthetic data.

##  2 Statistical disclosure control (SDC)

SDC operationalizes the trade-off between risk and utility within the context
of a single observed database $D\in\mathcal{D}$. Data curators construct RMs
$S(D)$, and analyze their privacy properties using a disclosure risk measure
(DRM), $R:\mathcal{S}\mapsto\mathcal{R}$. The RM $S$ is then altered depending
on both the data utility offered by $S(D)$ compared to $D$, and the risk
$R(S(D))$ compared to $R(D)$. In doing so, the confidential data is reused by
the data curator multiple times in order to calibrate the balance between
privacy and data utility. Disclosure risk measure (DRM)a function $R$ from
$\mathcal{S}$ to $\mathcal{R}$ which quantifies the disclosure risk of a
sanitized output, $R(S(D))$

###  2.1 SDC methods

As originally formulated by Duncan & Pearson (1991), SDC methods for matrix-
valued databases often belong to a class of linear transformations, i.e.,
$S(D)\triangleq ADB+C.$ Here, $A$ describes a record-level transformation, $B$
describes variable-level transformations, and $C$ describes additional
displacement or randomized noise. Note that in practice, these transformations
need not be linear, nor randomized. Regardless, each of these transformation
classes introduces baise and variance to the confidential data, and thus new
considerations into the data analysis process, which we briefly review:

  * •

Record-level transformations include members of confidential database in the
released statistics with varying probabilities. Common approaches involve
random sampling, outlier removal, and special unique removal (Willenborg & De
Waal, 1996).

  * •

Variable transformations typically shrink $\mathcal{S}$ relative to
$\mathcal{D}$. For tabular data, cell suppression, recoding, top-coding, and
aggregation are all examples of schema reduction techniques that reduce
$\mathcal{S}$ (Hundepool et al., 2012).

  * •

Randomized masking injects randomized noise into quantitative statistics to
prevent direct inference on any statistic exactly calculated from individual
records. Note that even though randomization is a central component of DP,
randomized SDC methods date back to the 1960s with randomized response
(Warner, 1965).

As a generalization of Duncan et al’s approach, synthetic data generation
methods produce sanitized output similar to $D$ but with records randomly
sampled. This sampling can occur for part of any individual record or for the
entire record, and we could produce partially or fully synthetic data. For
more details, see Drechsler & Reiter (2010), Snoke et al. (2018b), and a
recent Annual Review article by Raghunathan (2021).

###  2.2 Disclosure risk measures (DRMs)

Given these methods, we now turn to what $R(S(D))$ means in practice. The DRM
$R$ captures information about individuals that can be inferred from the
statistical release $S(D)$. Choices for $R$ make different implicit and
explicit assumptions about what adversaries know in advance, what constitutes
statistical disclosure, and how to quantify the probability of those potential
disclosures. In general, there are three broad categories of DRMs:

  1. 1.

Quasi-identifiability measures: Quasi-identifiability is the ability for
combinations of certain covariates to isolate individuals in the dataset. As
an example, $S$ satisfies $k$-anonymity (Sweeney, 2002) if:

$R(S(D))=\min_{X\in\mathcal{X}}\\#\\{i\in[n]\mid X_{i}=X\\}\geq k.$ (1)

Notable variants include $\ell$-diversity (Machanavajjhala et al., 2007) and
$t$-closeness (Li et al., 2007), which extend $k$-anonymity to capture the
heterogeneity of sensitive user contributions within quasi-identifying
categories. For databases with non-discrete entries, alternative approaches
may be used based on clustering, microaggregation, or outlier detection
(Domingo-Ferrer & Mateo-Sanz, 2002).

  2. 2.

Model-based reidentification measures: SDC methods often involve modeling
whether particular entries are reidentifiable under various modeling
assumptions in the worst-case scenario (but still within the context of a
single database, unlike DP). We define this event as $r_{i}=1$ for $i\in[n]$
based on a probability model $\operatorname{\mathbb{P}}_{\theta}$ for
$\theta\in\Theta$. This allows us to construct reidentification rates of the
form:

$R(S(D))=\frac{1}{n}\sum_{i=1}^{n}\sup_{\theta\in\Theta}\operatorname{\mathbb{P}}_{\theta}(r_{i}=1\mid
S(D)).$ (2)

The effectiveness of the measure depends on the model accuracy for
$\operatorname{\mathbb{P}}(r_{i}=1\mid S(D))$. When $\mathcal{X}=k$, different
techniques can be used to model the joint distribution of frequencies for
categories in the population and sample (Franconi & Polettini, 2004); e.g.,
these can be based on log-linear models (Fienberg & Steele, 1998, Skinner &
Shlomo, 2008) or survey estimation techniques (Skinner, 2009). The formula in
Equation 2 calculates an average reidentification rate; however we may
interested in other summary statistics of the individual reidentification
probabilities $\operatorname{\mathbb{P}}(r_{i}=1\mid S(D))$, such as their
maximum in a worst-case analysis.

  3. 3.

Data-based reidentification measures: while theoretical models can upper bound
DRMs, we can alternatively lower bound these risks by attempting such database
reconstruction attacks with external data sources (Domingo-Ferrer & Torra,
2003, Winkler, 2004). The DRM is then a linkage rate, or:

$R(S(D))=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\\{\text{Record $X_{i}\in D$
successfully linked to a record $Z_{j}\in Z$}\\}.$ (3)

Such an approach depends on multiple factors: how are potential records
$X_{i}\in D$ extracted from $S(D)$? What determines a successfully linked
record? And how does the external data $Z$ relate to the population? Such
questions are answered by fundamental connections between database
reconstruction and record linkage (Dobra et al., 2009, Vatsalan et al., 2013,
Garfinkel et al., 2019).

In the current data landscape, however, there are systemic downsides to using
SDC that could be viewed as weaknesses of the framework. First, data curators
often cannot disclose the mathematical form of the RM $S$ without leaking
additional confidential information (e.g., see Drechsler & Reiter (2010) on
data swapping, or Slavković (2004) for cell suppression, which also shows how
lack of transparency negatively impacts statistical inference). Next, SDC
methods are not robust to post-processing: there could be transformations of
our releases $h$ where $h(S(D))$ and $S(D)$ have different DRMs. Finally, SDC
methods do not easily compose, in that if we have two release strategies
$S_{1}(D)$ and $S_{2}(D)$ and we know their risks, it may be difficult to
quantify the risk of the joint release $(S_{1}(D),S_{2}(D))$.

##  3 Differential privacy (DP)

Differential privacy (DP) is a framework which mathematically formalizes the
privacy properties of data release strategies and addresses the above
shortcomings. By starting with a privacy definition and necessitating
additional randomness, DP methods are provably consistent with the privacy
definition and able to satisfy these three properties.

  1. 1.

Methodologically transparent: knowledge of $S$ preserves $S(D)$’s privacy
risk.

  2. 2.

Robust to post-processing: $h(S(D))$ has, at most, the same privacy risk as
$S(D)$.

  3. 3.

Composable: we can analytically express the privacy risk of two DP releases
$S_{1}(D)$ and $S_{2}(D)$ when jointly released.

###  3.1 General setup

DP was first introduced by Dwork et al. (2006b) which defined the concept of
an $\epsilon$-indistinguishable RM, now commonly known as $\epsilon$-DP or
“pure” DP RM. Since then, DP as a framework has spawned a massive number of
new privacy definitions (Desfontaines & Pejó, 2019). Because of this, it is
often unclear and debated what makes any particular property emblematic of
“DP.” Here, we restrict ourselves to the most common privacy definitions and
properties associated with the majority of DP implementations (Dwork et al.,
2014).

DP methods aim to limit the probabilistic influence of any individual’s
database contribution on sanitized outputs $S(D)$ (again, $S(D)$ could be any
summary statistic, parameter estimation, or synthetic microdata sample). In
doing so, DP methods heuristically limit what can be inferred about an
individual’s contribution to an output, regardless of whether they contribute
to the database or not, in excess of what an adversary might know a priori.
Ideally, whether individuals choose to contribute to a database should not
substantively change the overall statistical results. This demonstrates a
close connection between DP and robust statistics (Dwork & Lei, 2009, Avella-
Medina, 2021, Slavkovic & Molinari, 2021).

Formally, let $D,D^{\prime}$ be two databases. Let $d_{H}$ be the Hamming
distance between the databases, i.e., the number of elements in the databases
that differ:

$d_{H}(D,D^{\prime})=\\#\\{i\in[n]\mid D_{i}\neq D_{i}^{\prime}\\}.$ (4)

For $d_{H}$, we say $D,D^{\prime}$ are adjacent if $d_{H}(D,D^{\prime})=1$. We
refer to this case as bounded DP, but we may alternatively consider statistics
on databases whose size differ by 1 (known as unbounded DP).

The overall goal of DP is to ensure $S(D)$ and $S(D^{\prime})$ are close
together with high probability when $D$ and $D^{\prime}$ are adjacent. This is
done by parameterizing the distance between $S(D)$ and $S(D^{\prime})$ with
functions of scalar parameters known as privacy loss budgets (PLB), which
leads to different DP definitions. Typically, PLBs are positive, real-valued
numbers that capture the trade-off between privacy and data utility; as PLBs
increase, more informative statistical results may be released with weaker
privacy guarantees. Different definitions have different PLB accounting
systems (ex: $\epsilon$ for $\epsilon$-DP, $\rho$ for $\rho$-zCDP):

Privacy loss budget (PLB)a scalar parameter that quantifies DP guarantees,
with smaller values conferring stronger privacy (ex: $\epsilon$ in
$\epsilon$-DP).

  * •

$\epsilon$-DP (Dwork et al., 2006b): define the log max-divergence as,

$D_{\infty}(S(D)\mid\mid
S(D^{\prime}))\triangleq\sup_{B\in\mathcal{F}}\log\left(\frac{\operatorname{\mathbb{P}}(S(D)\in
B)}{\operatorname{\mathbb{P}}(S(D^{\prime})\in B)}\right).$ (5)

If $S$ satisfies $\epsilon$-DP for some PLB $\epsilon\in[0,\infty)$, then for
all $B\in\mathcal{F}$ and databases, $D,D^{\prime}$ with
$d_{H}(D,D^{\prime})=1$:

$\operatorname{\mathbb{P}}(S(D)\in
B)\leq\operatorname{\mathbb{P}}(S(D^{\prime})\in B)e^{\epsilon}.$ (6)

This is equivalent to bounding $D_{\infty}(S(D)\mid\mid
S(D^{\prime}))\leq\epsilon$ for all adjacent $D,D^{\prime}$.

  * •

$(\epsilon,\delta)$-DP (Dwork et al., 2006a): similarly, we can relax
$\epsilon$-DP by incorporating a relaxation parameter, $\delta\in[0,1)$.

$\operatorname{\mathbb{P}}(S(D)\in
B)\leq\operatorname{\mathbb{P}}(S(D^{\prime})\in B)e^{\epsilon}+\delta.$ (7)

  * •

$\rho$-zCDP (Bun & Steinke, 2016): Define the Rényi divergence:

$D_{\alpha}(S(D)\mid\mid
S(D^{\prime}))\triangleq\frac{1}{\alpha-1}\int\log\left(\frac{p(S(D))^{\alpha}}{p(S(D^{\prime}))^{\alpha-1}}\right)\
d\mathcal{S},$ (8)

where $p(\cdot)$ is the density of the mechanism, and the integral is taken
over the statistical output space $\mathcal{S}$. Then a RM satisfies
$\rho$-zero-concentrated DP (or $\rho$-zCDP) if for all $\alpha\in(1,\infty)$,

$D_{\alpha}(S(D)\mid\mid S(D^{\prime}))\leq\alpha\rho.$ (9)

Next, we present some of the nice statistical interpretations of
$\epsilon$-DP, the strongest of the three definitions above (in that
satisfying $\epsilon$-DP implies satisfying the other two definitions). In the
same setup, consider the hypotheses:

$H_{0}:X_{1}=x_{0},\quad X_{1}\neq x_{1},\quad x_{0},x_{1}\in\mathcal{X}.$

Note that we assume database rows are exchangeable, in that any user’s
contribution may serve as $X_{1}$. Wasserman & Zhou (2010) show that if $S(D)$
is an $\epsilon$-DP result, then any procedure for testing $H_{0}$ above based
on $S(D)$ with type I error $\alpha$ has power bounded above by $\alpha
e^{\epsilon}$. Extending this interpretation, Dong et al. (2019) consider a
functional analogue of the PLB and its connections to the trade-off between
Types I and II errors. Similar testing interpretations exist for $\rho$-zCDP
as sub-Gaussian concentration equalities on the log-likelihood ratio for this
test. From a Bayesian perspective, if $\pi$ is any prior distribution on the
hypotheses, then if $S(D)$ satisfies $\epsilon$-DP:

$\frac{\operatorname{\mathbb{P}}(H_{1}\mid
S(D))}{\operatorname{\mathbb{P}}(H_{0}\mid
S(D))}\Big{/}\frac{\pi(H_{1})}{\pi(H_{0})}\in[e^{-\epsilon},e^{\epsilon}].$
(10)

All these interpretations capture the important property that DP only protects
against relative disclosure risks. For example, Equation 10 suggests that
under $\epsilon$-DP, an adversary’s prior odds of learning information about
someone is similar to their posterior odds. Therefore, the adversary’s Bayes
factor is close to 1 when the PLB is sufficiently small, suggesting that the
$\epsilon$-DP result does little to change the adversary’s knowledge.

###  3.2 DP Release Mechanisms

Release mechanisms which satisfy DP rely on randomization to ensure the
distance between the two distributions of the output are close. Below is but a
small sample of the many possible RMs used to satisfy DP. In this section, we
consider properties of a statistic $T(\mathcal{D})\in\mathcal{T}$ that we aim
to release. Central to many different DP definitions is the concept of
sensitivity, defined as $\Delta$ where for some norm on $\mathcal{S}$,
$||\cdot||$:

$\Delta\triangleq\sup_{D,D^{\prime}\in\mathcal{D},d_{H}(D,D^{\prime})=1}||T(D)-T(D^{\prime})||.$

Sensitivitythe largest possible change, $\Delta$, in a statistic, $T(D)$, by
altering one entry in the database $\mathcal{D}$, as measured by a norm
$||\cdot||$.

Sensitivity captures the worst-case influence of one individual on $T$, which
depends on $||\cdot||$. Notably, the optimal choice of norm for any particular
$T(D)$ can be inferred by the geometric properties of the sensitivity space
$\mathcal{S}_{T}$ (Awan & Slavković, 2020):

$\mathcal{S}_{T}\triangleq\\{T(D)-T(D)^{\prime}\mid
D,D^{\prime}\in\mathcal{D},d_{H}(D,D^{\prime})=1\\}.$

For many statistics of interest, the sensitivity space (and thus $\Delta$) is
bounded by construction. As an example, count data within a single cell (i.e.,
the number of database users with a particular attribute), has a sensitivity
of 1. However, for more complex statistics, $\Delta$ may be unbounded (ex: a
parameter in a linear regression). The most common approach to address this
problem is to introduce enforced bounds, either by bounding the output space
$\mathcal{S}$, database input space $\mathcal{D}$, or the parameter space in a
potential model for the data, $\Theta$. This implementation choice has
important consequences for validity and consistency of downstream statistical
inference (see Section 4.4). We also note that some (e.g., Wang et al. (2015),
Minami et al. (2016)) use regularity conditions induced from posterior
sampling to sidestep the problem of unbounded sensitivity.

####  3.2.1 Primitive Elements

Most DP algorithms rely on a few primitive components that are subseqently
post-processed and composed in complete algorithms. Here, we review the most
common primitives. The simplest way to satisfy DP is to add independent noise
to $T(D)$, i.e., $S(D)\triangleq T(D)+\gamma$, where $\gamma$ is a random
variable with mean 0 and variance that increases as $\Delta$ increases and the
PLB decreases. Notable examples for $\epsilon$-DP include the Laplace
mechanism (Dwork et al., 2006a), its discrete analogue (Ghosh et al., 2012),
and the family of $K$-norm mechanisms (Hardt & Talwar, 2010, Awan & Slavković,
2020). Examples for $(\epsilon,\delta)$ and $\rho$-zCDP include the Gaussian
mechanism (Dwork et al., 2006a) and its discrete analogue (Canonne et al.,
2020).

Alternatively, we can consider solving an optimization problem based on
confidential data while simultaneously satisfying $\epsilon$-DP. This is
canonically associated with the $\epsilon$-DP exponential mechanism (McSherry
& Talwar, 2007), in which a loss function
$L:\mathcal{S}\times\mathcal{D}\times[0,\infty]$ is minimized while respecting
$\epsilon$-DP. When

$\sup_{s\in\mathcal{S}}\sup_{D,D^{\prime}\in\mathcal{D}}||L(s,D)-L(s,D^{\prime})||\leq\Delta_{L},$
(11)

we can satisfy $\epsilon$-DP by releasing one sample from the density

$f(s)\propto\exp\left(-\frac{\epsilon}{2\Delta}L(s,D)\right)\nu(s),$ (12)

where $\nu(\cdot)$ is a base measure which does not depend on $D$. Notable
choices which allow for nice asymptotic properties include the inverse
sensitivity mechanism (Asi & Duchi, 2020) and $K$-norm gradient mechanism
(Reimherr & Awan, 2019), which are equivalent for some common classes of
learning problems.

Some optimization problems in statistics and machine learning can be solved by
perturbing the input to the problem, i.e.:

$S(D)=\mathrm{argmin}_{s\in\mathcal{S}}\left[L_{D}(s)+\gamma\right],$ (13)

where the form of $\gamma$ is chosen based on the problem constraints and the
PLB. These have been used in empirical risk minimization (Chaudhuri et al.,
2011), convex optimization (Kifer et al., 2012), and robust $M$-estimation
(Slavkovic & Molinari, 2021), to name a few.

####  3.2.2 Post-processing and Composition Techniques

DP’s properties enable flexibility in constructing complex algorithms from
primitive building blocks. First, post-processing allows us to construct DP
statistics by transforming DP microdata under the same PLB. Second, we can
generate DP parameter estimates for two different models and understand their
privacy guarantees using sequential composition (e.g., from the same data
release $S_{1}(D)$ with $\epsilon_{1}$ and $S_{2}(D)$, $\epsilon_{2}$, and the
total PLB will be cumulative). Third, we can apply a DP method to different
sub-populations of interest in a database, and maintain the same privacy
guarantees through parallel composition (McSherry, 2009).

Thus, given the primitives and the properties, there are countless ways to
engineer more complex DP algorithms. Here, we highlight common clusters of
techniques. First, because the primitive mechanisms depend so heavily on
sensitivity, artificial regularity is often induced on $D$ to reduce this
sensitivity. While this can be done using SDC techniques (truncation,
discretization, clipping, etc.), more advanced methods exploit dimension
reduction to effectively reduce the sensitivity of correlated statistics, such
as the high-dimensional matrix mechanism for large counting query collections
(McKenna et al., 2018) or private PCA for linear dimension reduction
(Chaudhuri et al., 2012, Awan et al., 2019).

For large data sets, subsampling provides a natural way to reduce the
effective PLB for different mechanisms (often referred to as “subsample-and-
aggregate” in DP) (Nissim et al., 2007, Li et al., 2012). For example, if
$\eta$ * 100% of a population is subsampled from an $\epsilon$-DP result, then
the resulting effective $\epsilon^{*}$ is $O(\eta\epsilon)$. Natural
extensions of subsampling include private bagging and boosting (Dwork et al.,
2010, Jordon et al., 2019).

Private synthetic data generation can be viewed as resampling from a model
with parameters privately estimated from confidential data. While the
regularity introduced by Bayesian priors offers some inherent privacy
protections (Wang et al., 2015), other approaches involve samples privately
weighted by synthetic data utility (Snoke & Slavković, 2018, Vietri et al.,
2020), modeling with Bayesian networks (McKenna et al., 2019) and GAN modeling
(Torkzadehmahani et al., 2019). Each of these methods offer different
empirical (Bowen & Snoke, 2019) benefits.

As an aside, private building blocks can be used to reconstruct most machine
learning methods while satisfying DP. As one example, private stochastic
gradient descent (Song et al., 2013) and its countless variants has allowed
for the mass proliferation of DP deep learning methods (Boulemtafes et al.,
2020). These methods frequently use $\rho$-zCDP, which has gained popularity
in the machine learning community since it relies on Gaussian noise, and
learning-theoretic properties of sub-Gaussian distributions form the
foundations for statistical learning theory (Bousquet et al., 2003, Vershynin,
2018). We point readers to Vadhan (2017) for a review on the sample complexity
of DP.

##  4 Data Utility under SDP

In both approaches to SDP, we release sanitized statistics $S(D)$ out into the
wild. What happens next? In the previous sections, we discussed the privacy
properties of $S(D)$ under SDC and DP independently; now, we consider the data
utility properties of arbitrary sanitized outputs $S(D)$, regardless of their
privacy semantics.

“Data utility” is itself ambiguous, so we need to unpack the term. We again
let $T(D)\in\mathcal{T}$ be our statistic of interest without any privacy
preservation applied (i.e., our “unsanitized” or confidential statistic). Our
goal is to perform inference on a parameter $\theta\in\Theta$. In doing so, we
can ask many different questions:

  * •

Data-based utility: how close is my sanitized output $S(D)$ to the
confidential output $T(D)$?

  * •

Comparative inferential utility: how close is a sanitized estimator
$\hat{\theta}(S(D))$ to a confidential estimator $\hat{\theta}(T(D))$?

  * •

Estimator inferential utility: how is my uncertainty for $\theta$ using
$\hat{\theta}(S(D))$ different from my uncertainty for $\theta$ using
$\hat{\theta}(T(D))$?

Our ability to address these questions depends on whether we are designing the
RM $S$ (e.g., release a consistent and asymptotically unbiased sanitized
parameter estimate), or adjusting for the effect of RM $S$ which we did not
choose (e.g., adjust the length of the confidence interval given the sanitized
statistic). When we design a RM for a specific inferential task, all three of
these should yield the same relative comparisons between estimators (i.e., if
a mechanism offers better data-based utility, it also offers better estimator
inferential utility). However, when we adjust for an existing RM, these
utility definitions do not offer the same relative comparisons between RMs,
and can even be conflicting! As an example from $\epsilon$-DP count data, the
Geometric mechanism (Ghosh et al., 2012) can optimize data-based utility, but
it requires post-processing that is sub-optimal for estimator inferential
utility on binomial data (Awan & Slavković, 2018). Therefore, we need to
address these two problem classes differently.

Here, we express the design and adjustment problems as two different minimax
estimation problems (though we could easily pick another loss aggregating
convention) (Slavković & Karwa, 2019). Suppose we want to minimize some loss
function $L:\Theta\times\Theta\mapsto\mathbb{R}^{+}$ in the worst-case
scenario over a space of possible data generating distributions $\mathcal{P}$
indexed by $\operatorname{\mathbb{P}}\in\mathcal{P}$. For any release
mechanisms $S(D)$, this requires us to think about the marginal distributions
for $S(D)$ for a given data generating distribution
$\operatorname{\mathbb{P}}\in\mathcal{P}$, i.e.:

$\mathcal{M}_{S}(\operatorname{\mathbb{P}})=\sum_{D\in\mathcal{D}}\mathrm{Pr}(S(D)\mid
D)\ \operatorname{\mathbb{P}}_{\theta}(D)$ (14)

From the design perspective, we are given a space of RMs $\mathcal{Q}$ which
satisfies some privacy guarantee. Our goal is to find the optimal RM
$S^{*}\in\mathcal{Q}$ and estimator $\hat{\theta}_{\mathrm{Design}}(S^{*}(D))$
that satisfies:

$\hat{\theta}_{\mathrm{Design}}=\operatorname*{arg\,min}_{\tilde{\theta},S\in\mathcal{Q}}\max_{\operatorname{\mathbb{P}}\in\mathcal{P}}\operatorname{\mathbb{E}}_{\mathcal{M}_{S}(\operatorname{\mathbb{P}})}[L(\tilde{\theta}(S(D)),\theta)].$
(15)

This problem has been analyzed in the local DP setting (Duchi et al., 2018)
and similarly in central DP (Smith, 2011). Alternatively, suppose we are only
given a sample $S(D)$ from an RM we did not design ourselves. Then our
inference problem requires us to find the optimal adjusted estimator
$\hat{\theta}_{\mathrm{Adjust}}(S(D))$ that satisfies:

$\hat{\theta}_{\mathrm{Adjust}}=\operatorname*{arg\,min}_{\tilde{\theta}}\max_{\operatorname{\mathbb{P}}\in\mathcal{P}}\operatorname{\mathbb{E}}_{\mathcal{M}_{S}(\operatorname{\mathbb{P}})}[L(\tilde{\theta}(S(D)),\theta)].$
(16)

Regardless of whether we choose $S$ or not, statistical inference requires
that we account for the transformation $S(D)$, meaning we CANNOT treat
inference given $T(D)$ the same as inference given $S(D)$, as the two
variables have entirely different sampling distributions; on a related issues
of approximating sanitized sampling distributions, see Wang et al. (2018).
This is true for all SDP methods, those from SDC and DP. Not only can the
distribution of $S(D)\mid D$ introduced randomized errors due to privacy, the
sample spaces of $S(D)$ and $T(D)$ can be entirely different, even for SDC
methods involving no randomization. This demonstrates that the de facto
practice of naively substituting $T(D)$ with $S(D)$ can produce invalid
statistical inferences, with incorrect interpretations of significance,
coverage, or other properties of statistical estimators; e.g., for these in a
network setting see (Karwa & Slavković, 2016, Karwa et al., 2017).

###  4.1 Specific utility and the design approach

First, we consider the design problem, in which our goal is to perform
inference for $\theta\in\Theta$ and design a valid estimator
$\hat{\theta}=S(D)$, where the RM satisfies some privacy guarantees. In the
SDC literature, data utility is frequently quantified by measures that capture
statistical information lost due to $S$ (Hundepool et al., 2012). In the DP
literature, the evaluation of randomized mechanisms relies on concentration
inequality results to bound probabilistic distances between $S(D)$ and $T(D)$,
or equivalently $\hat{\theta}(S(D))$ and $\hat{\theta}(T(D))$ (Boucheron et
al., 2013). Under consistency or other oracle assumptions, these will give us
estimator inferential utility measures as well.

Focusing on uncertainty quantification directly offers a few advantages.
First, we can design optimal estimators based on the degree to which they
specifically influence our statistical uncertainty. Examples include power and
sample size analysis for experimental data (Vu & Slavkovic, 2009), confidence
interval width (Karwa & Vadhan, 2017), the power of finite-sample hypothesis
testing procedures (Awan & Slavković, 2018), and asymptotically correct
inference from central limit theorem approximations (Awan et al., 2019).
Second, these procedures are more user-friendly, as they account for
uncertainty in $\hat{\theta}$ due to privacy preservation. When we strictly
measure how close $\hat{\theta}(S(D))$ is to $\hat{\theta}(T(D))$, we cannot
draw the same conclusions, because such a comparison does not account for
other sources of error in the data generating process.

###  4.2 General utility and the adjustment approach

Alternatively, we consider the adjustment problem, in which we must account
for a RM we did not design specifically for our inferential problem. This is
the setting most often associated with private synthetic microdata or
collections of sanitized statistics, suggesting different kinds of utility
measures for general purpose inference and inference on specific tasks (Snoke
et al., 2018b, Arnold & Neunhoeffer, 2020).

Importantly, different methods for generating $S(D)$ may be compatible or
incompatible with different probability models for $\theta$. For example, if
we generate sanitized estimates of sufficient statistics for $\theta$, then we
would say this model is compatible with the RM because we can account for
measurement error in a way that still produces asymptotically consistent
statistics (see Foulds et al. (2016) for an example in Bayesian inference).
However, if this is not the case, i.e., if the confidential target of our
private statistics $T(D)$ is not sufficient for the model, there are certain
inferences we cannot perform at all.

For inference on general purpose data, we need to characterize the likelihood
of $S(D)$ given $\theta$ by integrating out the confidential data. This can be
done from the frequentist perspective, i.e.,:

$\operatorname{\mathbb{P}}_{\theta}(S(D))=\sum_{\mathcal{D}}\operatorname{\mathbb{P}}(S(D)\mid
D)\ \operatorname{\mathbb{P}}_{\theta}(D),$ (17)

or from the Bayesian perspective, i.e., with prior $\pi(\theta)$,

$\operatorname{\mathbb{P}}(\theta\mid
S(D))\propto\pi(\theta)\sum_{\mathcal{D}}\operatorname{\mathbb{P}}(S(D)\mid
D)\operatorname{\mathbb{P}}(D\mid\theta).$ (18)

Because of this necessity, DP offers a particular advantage over SDC. If $S$
satisfies DP, then the privacy mechanism is transparent (i.e., the form of
measurement errors are publicly known), and the problem reduces to a classical
“error-in-variables” problem. For common models, we can readily rely on
techniques from the existing measurement error literature, such as techniques
based on generalized linear models and estimating equations (Tsiatis, 2006,
Carroll et al., 2006, Hardin & Hilbe, 2002).

Still, incorporating these errors is easier said than done, as the integration
in Equations 17 and 18 can be quite computationally difficult. In some cases,
connections between approximate Bayesian computation (Beaumont, 2019) and
inference on noisy estimates can be used for posterior inference. Fearnhead &
Prangle (2012) showed that exact inference from perturbed statistics uses the
same inferential sampling procedure as ABC with normal summary statistics.
This allows Gong (2019) and Seeman et al. (2020) to produce valid inference
from statistical results. Note that different privacy mechanisms are more or
less amenable to probability models, which we will see in the next section.

###  4.3 Statistical properties of RMs

In this section, we compare a few different DP mechanisms for counting queries
and discuss their statistical properties; specifically, we discuss how these
choices for $S(D)$ affect the ease of downstream inference through probability
models. Suppose we are interested in releasing a count of events
$T(D)\in\mathbb{Z}^{+}$, in which our sensitivity $\Delta$ is 1. We consider
different ways of releasing $T(D)$ satisfying different DP formalisms:

  1. 1.

DiscLaplace: Discrete Laplace mechanism for $\epsilon$-DP (Ghosh et al.,
2012):

$S(D)=T(D)+\varepsilon,\varepsilon\sim\mathrm{DiscreteLaplace}(\epsilon^{-1}).$
(19)

  2. 2.

DiscGaussian: Discrete Laplace mechanism for $\rho$-zCDP (Canonne et al.,
2020):

$S(D)=T(D)+\varepsilon,\varepsilon\sim\mathrm{DiscreteGaussian}(\rho^{-2}).$
(20)

  3. 3.

Exponential: Exponential mechanism for $\epsilon$-DP (McSherry & Talwar,
2007):

$\operatorname{\mathbb{P}}(S(D)=k)\propto\exp\left(-\frac{\epsilon}{2}|k-T(D)|\right)\mathbbm{1}\left\\{k\in\\{0,1,\dots,n\\}\right\\}.$
(21)

  4. 4.

RandResp: Randomized Response for local $\epsilon$-DP:

$S(D)=\sum_{i=1}^{n}\mathrm{RR}(X_{i}),\quad\begin{cases}\operatorname{\mathbb{P}}(\mathrm{RR}(X_{i})=X_{i})=\frac{\exp(\epsilon)}{1+\exp(\epsilon)}\\\
\operatorname{\mathbb{P}}(\mathrm{RR}(X_{i})=1-X_{i})=\frac{1}{1+\exp(\epsilon)}.\end{cases}$
(22)

Note that not all privacy guarantees are the same: local $\epsilon$-DP is
stronger than $\epsilon$-DP, which is stronger than $\rho$-zCDP. Furthermore,
each mechanism has different statistical properties, which we summarize in
Table 1 and describe here:

  1. 1.

Error independence: can randomized errors due to privacy be expressed as a
perturbation, where for some norm $||\cdot||$,
$||S(D)-T(D)||\operatorname{\perp\\!\\!\\!\perp}D$?

  2. 2.

Unbiased: does the mechanism introduce bias into the estimate of the
confidential data, i.e., does $\operatorname{\mathbb{E}}[S(D)]=T(D)\ ?$

  3. 3.

Mode unbiased: is the maximum likelihood output of the mechanism the
confidential response? i.e., is it true that:

$\max_{S^{*}\in\mathcal{S}}\operatorname{\mathbb{P}}(S(D)=S^{*})=T(D)\ ?$ (23)

(NB: result assumes the existence of a PMF for $S(D)$, with analogous results
for arbitrary measures or densities).

  4. 4.

Domain-constrained: does the space of $T(D)$ conform to the space of $S(D)$?
i.e., is it true that for all $B\in\mathcal{F}$:

$\operatorname{\mathbb{P}}(T(D)\in
B)=0\implies\operatorname{\mathbb{P}}(S(D)\in B)=0\ ?$ (24)

Mechanism | DiscLaplace | DiscGaussian | Exponential | RandResp
---|---|---|---|---
Trust model | Central | Central | Central | Local
Formalism |  $\epsilon$-DP |  $\rho$-zCDP |  $\epsilon$-DP |  $\epsilon$-LDP
ErrorDist $\operatorname{\perp\\!\\!\\!\perp}D$? | Yes | Yes | No | No
Unbiased? | Yes | Yes | No | No
Mode unbiased? | Yes | Yes | Yes | No
Domain-constrained? | No | No | Yes | Yes
Table 1: Counting mechanisms and their statistical properties

Note that we could post-process either DiscLaplace or DiscGaussian to restrict
the domain, i.e.:

$S_{\mathrm{post}}(D)=\begin{cases}0&T(D)+\varepsilon<0\\\
n&T(D)+\varepsilon>n\\\ T(D)+\varepsilon&\mathrm{Otherwise.}\end{cases}$ (25)

This post-processing transformation, proposed in Ghosh et al. (2012), offers a
uniform improvement in utility as measured by the distance between $S(D)$ and
$T(D)$, i.e.:

$\operatorname{\mathbb{E}}[|S_{\mathrm{post}}(D)-T(D)|]\leq\operatorname{\mathbb{E}}[|S(D)-T(D)|].$
(26)

However, $S_{\mathrm{post}}(D)$ is no longer unbiased, and the errors are now
data-dependent. This demonstrates that post-processing changes the statistical
properties of RMs, and improving utility compared to confidential results can
have unintended consequences for the statistical properties of these
estimators. In fact, post-processing can degrade the power of resulting
statistical inferences, sometimes uniformly (Seeman et al., 2020, 2022).
Therefore, it is essential that we consider which mechanisms are amenable to
downstream inference and which make it prohibitively difficult or
computationally expensive.

###  4.4 Risk and model misspecification

As one last important caveat, we remind ourselves that whenever we make
modeling assumptions, there is always the potential to be wrong. SDP
introduces new opportunities for different kinds of misspecification that we
briefly discuss here.

SDP relies on the properties of the database schema $\mathcal{D}$ being
correctly specified. When this is not the case, SDP risk and utility can both
suffer. Unanticipated records falling outside the expected schema could result
in weaker DRMs (e.g., negative counts being dropped); if those records are
systematically excluded due to processing errors, then we could be subject to
an unknown form of unaccounted missing data. As another example, we may
incorrectly specify the sensitivity of a statistic $T(D)$, meaning our privacy
guarantees are realized at a larger PLB than intended.

SDP risk measures may be based on implicit assumptions on independence between
records which may not hold in practice. For an example with DP, the framework
is colloquially seen as demonstrating “robustness to arbitrary side
information,” as formalized in Kasiviswanathan & Smith (2008). However, when
DP is treated as a property of probability distributions, as in Pufferfish
privacy by Kifer & Machanavajjhala (2014), we only maintain $\epsilon$-DP
style privacy semantics when the entries of the database are independent. In
other words, when there is dependence between database records, $\epsilon$-DP
guarantees may be degraded (Liu et al., 2016). This has motivated methods for
the private analysis of correlated data (Song et al., 2017, Karwa et al.,
2017, Seeman et al., 2022).

##  5 The Fable of the Westerosi Census

Many of the core research problems in SDP rely on translating statistical
notions into practical commitments to privacy protections and data utility
goals. Here, we do not focus on the newest, nor the most advanced mechanisms
by modern publishing standards. Instead, the goal of this section is to
showcase that there is complex interplay between different privacy formalisms,
the underlying data structure, and data generating assumptions, all of which
affect risk and utility, that is valid statistical inference. To the end, we
turn to a fabulistic case study on our data.

We consider a dataset based on the population of fictional characters from the
world of Westeros in the fantasy series “Game of Thrones” (GoT) (Martin,
2011); data were gathered by mining the text of the fan-written Wikipedia, “A
Wiki of Ice and Fire” (Westeros.org, 2014, Technical University of Munich,
2019). Variables are described in Table 2. Note that in working with this
dataset, we do not intend to make light of the very real harms caused by
privacy violations. Instead, we use a dataset where such harms are impossible
by construction, and the worst possible harms for readers are minor story
spoilers. And to the best of our knowledge, it is impossible to violate the
privacy of a fictional character.

Our data curator, Lord Varys (henceforth LV) is tasked with conducting a
census of the citizens of Westeros, in order to count and report which citizes
have survived the politically tumultuous events of GoT. However, he is
concerned about an adversary, Littlefinger (henceforth LF), learning
information about vulnerable members of the royal family whose data may be
contained in the Census. For this case study, we consider whether or not a
character survives the events of GoT to be a sensitive attribute. We
demonstrate, how LV’s assessment of risk and utility changes in different
scenarios.

Variable | Kind | Description
---|---|---
title | Nominal | Title (ex: Ser, Lord) (261 levels)
title_reduced | Nominal | Major Title Categories (11 levels)
culture | Nominal | Culture (ex: Dornish, Braavosi, Dothraki) (35 levels)
culture_reduced | Nominal | Major Culture Categories (14 levels)
house | Nominal | House (ex: Stark, Lannister, Tyrell) (326 levels)
house_reduced | Nominal | Major Houses (27 levels)
gender | Binary | Male or Female
nobility | Binary | Noble or Peasant
alive | Binary | Alive or Dead
Table 2: Data variable description

###  5.1 Counting queries with SDC

First, LV considers different contingency tables aggregated based on different
quasi-identifiers, (i.e., combinations of different nominal and binary
variables). For example, he could create a Culture+Nobility table, which lists
the number of nobles and peasants from every culture. He soon realizes that
too many respondents have unique combinations of titles, cultures, and/or
houses; for example, there is only one Dornish princess in the data, and LF
could learn attributes about the Dornish princess if the database is released
as-is. Therefore, to address these issues, he creates simplified versions of
all these categorical random variables, only keeping categories with at least
10 respondents (as shown in Table 2) and grouping all others into a separate
category. We refer to these as the reduced versions of these nominal
variables, e.g., CultureReduced.

Next, LV considers two SDC risk measures for different contingency tables.
First, he looks at $k$-anonymity (Eq. 1), which captures the smallest number
of census respondents with any given quasi-identifier; LV desires larger $k$
values for stronger privacy protections. In the top panel of Figure 2, he
plots the $k$-anonymity of the first $s$ rows on the $y$-axis with $s$ on the
$x$-axis, and sees that different combinations of quasi-identifiers offer
different protections; CultureReduced generally has the best $k$-anonymity
guarantees, and these increase as the database size increases. However, LV
notices that some of the cultures, even after aggregating, have only one
noble, meaning that using CultureReduced+Nobility offers $1$-anonymous
privacy, regardless of the database size. This means for any database size, if
LV releases CultureReduced+Nobility, LF will be able to reidentify anyone with
a unique reduced culture and nobility status, and at least one such person
exists in the database.

LV is also concerned about what LF might do if he learns which kinds of people
are most affected by the events in GoT. So he measures $t$-closeness based on
survival, or the largest difference in survival rate between any quasi-
identifying group and the overall sample. In the bottom panel of Figure 2, he
sees that the $t$-closeness is small for Gender (blue line); that means he can
release information about the survival rates for men and women in Westeros,
and LF is not likely to learn much about anyone from the Census’s survival
rate simply because of their gender. However, the $t$-closeness is larger for
Gender+Nobility; this raises concerns for LV, because he is concerned LF might
learn about the probability that someone in the database, like the Dornish
princess, is alive or not. However, $t$-closeness can sometimes capture
population-level effects; so maybe, LF would learn about the difference in
survival rates between noble females and the whole population, regardless of
whether the Dornish princess completed the Census of Westeros or not!

Figure 2: GoT data, (top) $k$-anonymity and (bottom) $t$-closeness risk
measures for different aggregated counts by query (quasi-identifiers) and
database size.

LV decides he will release a 2x2 contingency table of nobility vs. survival
with different $k$-anonymity protections. He wants to perform inference for
the null hypothesis $H_{0}:$ nobles are at least as likely as peasants to
survive GoT, with $H_{1}$: otherwise. Under the null, the number of surviving
nobles follows a Hypergeometric distribution. Normally, LV would simulate from
this distribution and numerically estimate the test statistic, since he wants
to extract as much information as possible. But LV knows his inference is
affected by his choice of $k$, and while others may ignore that fact, he
conditions on the database being $k$-anonymous for different $k$ values by
rejecting simulated statistics that violate $k$-anonymity. LV then uses these
reduced samples to calculate the $p$-value, on the $y$-axis in Figure 3. In
this risk-utility plot, the horizontal lines refer to the non-private
$p$-values, and the solid lines are the estimated $p$-values (on the $y$-axis)
at different $k$s (on the $x$-axis). As $k$ increases, LV loses power to
detect differences in the survival rate of nobles and peasants; for example,
if $n=300$ and $k=20$, we fail to detect such a difference at a Type I error
of $.10$. This demonstrates that SDC measures affect statistically valid
inference, even when no randomization occurs.

Figure 3: GoT data, privacy-corrected $p$-values for Fisher’s exact test
($H_{0}=$ nobles at least as likely as peasents to survive) from $k$-anonymous
tabular data at different database sizes and $k$ values.

###  5.2 Counting queries with DP

Because of LV’s concerns, including that he cannot release much data under the
SDC framework since the risk with Nobility is high, and the fact that he
really cannot be sure what LF may already know, he decides to use bounded
$\epsilon$-DP methods for counting queries. He first plans to release the
counts of the surviving and dead, aggregated by CultureRedued+Gender+Nobility,
and with discrete Laplace noise added to each count (Equation 19). This way,
LF will not be able to learn more about individuals in the database, because
the possible releases where any one respondent survived GoT or not are close
together with high probability. But this has LV wondering: how much could LF
know already, and how much could he stand to learn from using LV’s DP census
results? LV decides to analyze two different scenarios: first, maybe LF
randomly guesses (i.e. flips a fair coin) to determine whether someone has
survived GoT or not. Second, maybe LF knows the true confidential proportion
of people who have survived GoT, in which case he is a more informed adversary
(for reference, around 25% of characters in GoT die). Using these two priors,
LV calculates the posterior risk that LF learns whether the last person in any
quasi-identifying cell (CultureRedued+Gender+Nobility) survived or died, in
the worst-case scenario where LF knows all but the last entry in any table
cell.

In Figure 4, LV plots the posterior disclosure risk on the $y$-axis and looks
that these posterior disclosure risks. First, the worst-case disclosure risks
are not the same for all cultures. Certain minority cultures under the
informed prior (top row of panels), such as Braavosi (BRAA) and Dornishmen
(DORN), are more likely to be reidentified at small PLBs (e.g.,
$\epsilon=0.1$) than people of larger cultures, such as Free folk (FREE).
Second, we see that prior assumptions can change how these posterior
disclosure risks are distributed amongst the populations; if LF has a good
prior, he could potentially learn more about whether the Dornish princess
survives GoT than, say, someome from the Free folk. This visually demonstrates
that even though the worst-case privacy guarantee in $\epsilon$-DP applies to
everyone, not everyone has the same posterior disclosure risks.

Figure 4: Posterior disclosure risks for individual GoT characters by prior
assumptions, culture, and PLB.

LV realizes from that analysis that if he wants to release the overall
survival rate (or equivalently, the death rate), he needs to sanitize it, even
though it is just a summary statistic. But LV still wants to do inference on
what this value could be, requiring him to account for additional noise due to
privacy. In Figure 5, LV plots three important figures at varying PLBs, from
$\epsilon=.01$ (stronger privacy protections) to $\epsilon=\infty$ (non-
private release). The upper figure shows the likelihood of the death rate
where we assume $S(D)=T(D)$ (chosen for comparison with non-private
inference). For this figure, LV also plots 95% confidence intervals based on
the sampling distribution of $S(D)$ (dashed line), which increase in size as
the PLB decreases. For some PLBs, like $\epsilon=.10$, the errors due to
privacy are dominated by errors due to sampling. For other PLBs, like
$\epsilon=.01$, the opposite is true. This essential information can only be
inferred by comparing the probability model to the errors due to privacy.

Most importantly, the middle panel of Figure 5 tells LV posterior credible
intervals (dashed lines) for $\theta\mid S(D)$ under the Jeffery’s prior
$\theta\sim\mathrm{Beta}(.5,.5)$. Because LV properly accounted for errors due
to privacy in his inference, his resulting credible interval increases in
width as $\epsilon$ decreases while providing exact statistical coverage. This
is NOT true in the case when we naively substitute $T(D)$ with $S(D)$,
demonstrating once again the essential nature of statistically valid inference
for sanitized results. Moreover, LV plotted this credible interval length on
the $y$ axis with the PLB on the $x$-axis. This allows him to visualize the
trade-off between privacy and utility and choose a PLB. LV sees that even the
non-private result, $\epsilon=\infty$, has a small amount of uncertainty. By
sacrificing a little data utility by making his credible interval wider for
the number of dead in GoT, LV can help protect the citizens of Westeros from
LF, regardless of whether it was the Dornish princess or someone else who
completed the Census of Westeros. Huzzah!

Figure 5: (top) Naive Inference: Likelihood of $\theta$ given $S(D)=T(D)$
under $T(D)\sim\mathrm{Binomial}(n,\theta)$ and associated confidence
intervals at different PLBs. (middle) Adjusted Inference: Posterior
distributions and associated credible intervals for $\theta\mid S(D)$ at
different PLBs. (bottom) Risk-utility curve for private posterior inference on
the GoT survival rate.

[h]

##  6 The Morals of Our Fable

  * •

SDC measures can provide strong or weak privacy protections that scale
differently with database sizes, and they may sometimes capture population-
level effects that exist regardless of whose data contributed to the
population-level inferences.

  * •

All SDP methods affect downstream inference, even SDC methods that do not
involve randomized noise.

  * •

Although DP methods offer worst-case relative privacy guarantees, the
posterior disclosure risks look different for different members of the
database and different adversarial prior assumptions.

  * •

DP necessitates adjusting downstream inferences for errors due to privacy,
which requires analyzing the interaction of probability models with
statistical measures.

##  7 Discussion & Future Directions

SDC and DP are schools of thought that frame the underlying problems of data
privacy in different ways, as there are theoretical and empirical pros and
cons to both approaches. Moreover, choosing to frame data privacy problems
from one perspective or the other induces trade-offs that cannot always be
quantitatively captured; these may be better solved by the legal and normative
literatures on data privacy. In this section, we discuss the high-level
differences between these approaches along a few key dimensions.

###  7.1 Comparing SDC and DP: Quantifying Risk

SDC and DP rely on measures of privacy risk with different conceptual trade-
offs, as discussed in Section 1.2. How can we tell which framework is better
suited for a particular use case? For that, we need to think about the gaps
left from either perspective. For SDC, the main question left unanswered is
whether bounds on the DRMs allow for resilience against other kinds of
inference attacks; e.g., by using database reconstruction attacks on public
Census data, the Census Bureau was able to identify real vulnerabilities in
their previous SDC methodology (Garfinkel et al., 2019). For DP, the main
question left unanswered is how to sociologically interpret PLBs, requiring us
to reason about worst-case adversaries, database pairs, and disclosure
scenarios. This shift in language can make it hard to express privacy concerns
in terms of PLBs (Cummings et al., 2021). Making PLBs more interpretable,
though, often requires further assumptions. For example, using the Bayesian
formulation of $\epsilon$-DP, we can make prior assumptions and calculate
different posterior disclosure risks under such protections (McClure & Reiter,
2012). Such measures offer more interpretability to practitioners at the
expense of no longer providing worst-case guarantees.

Interpreting SDC and DP guarantees depends on many different considerations.
How amenable is our output statistic space to privacy-preserving inference?
How sociologically sensitive are the attributes about units we observe? How
large is our database? What kinds of variability do we expect in the attribute
responses? In Sections 4 and 5, we only began to scratch the surface of
answering these questions with respect to database size and query selection.
Still, we demonstrated that answers to these questions change the social
calculus of how we aim to quantify and limit privacy risks.

Future work could address an alternative approach, where the unit of analysis
is neither a single database (as in SDC) nor an entire schema (as in DP), but
instead a restricted set of database pairs within the schema. This approach,
sitting somewhere between SDC and DP, could prove useful by making the DP-
style ”worst-case-scenario” analysis for DP less extreme while still providing
more robustness to database reconstruction than SDC. Examples of early work in
this area include (Kifer & Machanavajjhala, 2014, Song et al., 2017, Seeman et
al., 2022).

###  7.2 Comparing SDC and DP: Quantifying Utility and Uncertainty

The role of data dependence is another distinguishing factor in comparing SDC
and DP. Recall that SDC methods aim to formalize privacy as a property of a
particular database $D\in\mathcal{D}$, whereas DP methods aim to formalize
privacy as a property of a particular release process on a database schema
$\mathcal{D}$. This change captured an important shortcoming of SDC methods.
The way they are implemented could not be disclosed transparently without
revealing probabilistic information about the individuals whose data was
altered due to disclosure limitation. Still, many optimal DP mechanisms rely
on privacy-preserving errors in ways that depend heavily on the confidential
data (e.g., Reimherr & Awan (2019), Asi & Duchi (2020)), making $S(D)\mid D$
difficult to characterize in practice.

Should the distributions of randomized errors due to privacy depend on the
confidential data? Even though the form of the mechanism can be transparently
disclosed, the usefulness of this disclosure varies substantively for
different mechanisms, which we explored in Section 4.3. From these examples,
the discrete Laplace mechanism provides independent perturbations to
collections of statistics; because the perturbation forms a location family
with independent noise set by the PLB, the distance between the private
statistic $S$ and the non-private statistic $T(X)$ is independent of $X$.
Aside from this relatively simple class of mechanisms, this property is not
generally shared. Some primitive mechanisms, such as the exponential mechanism
and its variants, do not easily allow for characterizations of errors due to
privacy independent of the data. This is not to say we shoul not use
mechanisms like these! It only means we should not ignore the tractability of
valid downstream inference as a design consideration.

In particular, the ubiquitous use of post-processing in DP methodology yields
many different methods which meet certain optimality criteria, but for which
the distribution of $S(D)\mid D$ is highly data dependent and sometimes
computationally intractable. This is the case for the U.S. Census TopDown
algorithm, which sequentially post-processes dependent count queries to
conform to global public information and various internal self-consistency
rules (Abowd et al., 2019). This suggests that both theoretically (Seeman et
al., 2022) and empirically (Seeman et al., 2020), DP results should be
released with and without post-processing applied whenever possible.

###  7.3 Challenges in Schema Choice and Data Generation

SDP guarantees, regardless of whether using SDC or DP, depend heavily on the
schema, $\mathcal{D}$. While SDP focuses on the form of the statistics we want
to release, $\mathcal{S}$, the choice of $\mathcal{D}$ limits the possible
values of $\mathcal{S}$ a priori. Moreover, from a system-level perspective,
we tend to view $\mathcal{D}$ as a static entity, when in reality, schemas are
dynamic and change over time. Schemas can grow to account for new unit
attributes; e.g., many databases containing protected health information (PHI)
are now updated to include information on COVID-19, such as vaccination status
and testing history. Additionally, individual contributions to a database
change over time, such as with streaming user data; this is an important
consideration for databases regularly updated with event data, such as
application logs from user behavior within different software applications.
While there is some emerging work on this topic, we feel that neither SDC nor
DP has developed robust solutions to these problems yet. Hence, we see this a
budding area for future research opportunities.

Furthermore, SDP frameworks tend to view collected data as complete, full-
information data, but rarely is this true in practice. Any social science data
collection scheme could suffer from one of the many sources of “total survey
error” (Groves et al., 2011) such as measurement error due to social
desirability bias, errors due to missingness or other systematic non-response,
or sampling procedures used to construct the database. We included these at
the top of Figure 1, as most SDP analyses deal with human-level data. Because
all information in statistical data privacy is typically taken ”at face
value,” the practical effects of accounting for ambiguity in this process are
often lost.

Model-based SDC methods, like those discussed in Section 2.2, can account for
some aspects of the data generating process, like survey sampling. However,
incorporating similar ideas into DP is conceptually challenging, as the
methodological details themselves also depend on the confidential data (Bun et
al., 2020, Seeman & Brummet, 2021). Resolving these differences is especially
important for the needs of data curators at official statistical agencies like
the U.S. Census.

###  7.4 Privacy and other ethical dimensions of data sciences

Even though we have focused on data privacy in a narrow, technical sense,
privacy is a naturally interdisciplinary topic which involves philosophical,
legal, and political scholarly traditions. The legal operationalization of SDP
remains an open problem, as there is much debate as to how SDP approaches
capture different legal statutes. Rogaway (2015) argues against any approach
that a priori privileges one conception of privacy over another, as all SDP
methods are inherently political in the way they allocate access to different
data in different forms. If we argue one kind of political allocation is
automatically ”better” than another, we risk ignoring how defining the terms
of that allocation influences our comparisons. Science and Technology Studies
(STS) scholars refer to these as “abstraction traps,” which have been studied
in algorithmic fairness (Selbst et al., 2019).

Additionally, SDP is but one of many research areas which attempts to imbue
data analysis processes with sociologically desirable properties, such as
interpretability (Carvalho et al., 2019) or fairness (Mitchell et al., 2021).
Current research has pointed to limits in the ability to jointly satisfy DP
guarantees and certain definitions of algorithmic fairness, both
quantitatively (Cummings et al., 2019) and qualitatively (Green, 2021).

###  7.5 Closing the Gap Between Theory and Practice

Here, we propose directions for open research that aims to resolve ideological
tensions within SDC and DP research communities and direct future research
towards addressing the needs of data subjects, curators, and users
simultaneously.

SDP research, in its current state, is largely focused on establishing
theoretical asymptotic results. Such results are clearly valuable, as they
bound the sample complexity of SDP problems in collecting and releasing
private statistics. However, when practitioners are deciding which method to
use, we argue that such approaches fail to support them.

Furthermore, it creates barriers to entry for who is reasonably prepared to
use the results from SDP methodology. Private companies that collect data at
scale and use DP, like Google and Microsoft, have enough data to estimate the
regimes in which asymptotic results offer useful characterizations of privacy
risk and utility. But for small datasets, like many of those in the social and
behavioral sciences, such techniques are infeasible. As a research community,
we ought to enable everyone to use SDP, regardless of database size.

None of our critiques should detract from the theoretical value of this work,
as it is an important step towards applicability! Instead, here we highlight
open questions within SDP research that take practitioner’s barriers to using
SDP seriously. These research directions require substantive efforts from the
SDP community (computer scientists, statisticians & data users) to help close
the widening gap between SDP theory and practice, most importantly along a few
key dimensions:

  1. 1.

Finite-sample utility guarantees: the close theoretical intersections between
learning theory and privacy theory have motivated the sample complexity
approach to SDP problems. As discussed above, this does not help practitioners
easily identify the asymptotic regime in which these results apply. Future
research ought to highlight tools that allow researchers working without data
at scale to select optimal mechanisms for their use case.

  2. 2.

Uncertainty quantification: uncertainty quantification is the foundation of
statistical reasoning, and future SDP work needs to prioritize valid
uncertainty quantification. For the design approach, this requires considering
optimal inference in terms of total uncertainty, and not just uncertainty
about the non-private estimator. For the adjustment approach, this requires
examining how SDP methods influence the bias and variability of statistics
produced from sanitized results. sls

  3. 3.

Optimization against operational intangibles: many of the logistical
requirements for using SDP in practice require constraints that prevent
optimal mechanisms from being used. For example, the U.S. Census’s
requirements for releasing self-consistent microdata poses problems not only
for optimality, but for consistent data utility across queries (Abowd et al.,
2021). Future research should treat seriously these operational requirements,
like the need for microdata or interpretable error distributions.

  4. 4.

Computational barriers: the focus of the majority of DP mechanisms is in
optimizing the trade-off between privacy and utility. However, computational
issues are usually a third, neglected dimension of the problem, as mechanisms
that are optimal from a privacy-utility perspective may be computationally
prohibitive to implement. These problems arise deterministically with finite
computing problems (Mironov, 2012) as well as computing with randomized
algorithms (Ganesh & Talwar, 2020, Seeman et al., 2021). For example,
instance-optimal mechanisms like the inverse sensitivity and $k$-norm gradient
mechanisms require sampling from an intractable distribution, and failure to
draw an exact sample using finite computing or finite MCMC approximation
consumes additional PLB. Future research should explore trade-offs from this
three-dimensional perspective, instead of the two-dimensional perspective
offered by privacy vs. utility alone.

  5. 5.

Extended trust models: right now, the majority of trust models in SDP focus on
the central model. However, techniques from secure multiparty computation
(SMC) could be used to extend SDP methodology to offer more practical
flexibility in trust modeling (Karr, 2010). There are many possible
opportunites to synthesize studies of privacy-preserving secure multiparty
computation and federated learning (e.g., Lindell & Pinkas (2009), Snoke et
al. (2018a), Kairouz et al. (2021)).

##  8 Conclusion

In conclusion, this review paper highlights and demonstrates the common
methodological foundation of SDC and DP, and their associated quantitative and
qualitative trade-offs required to investigate data privacy from either
perspective. By focusing on the statistical viewpoint, SDP will produce and
support the data sharing necessary for reproducible scientific discourse and
democratic data governance. Whether using SDC or DP, or whether by design or
adjustment, we all ought to remember that “different roads sometimes lead to
the same castle” (Martin, 2011).

[SUMMARY POINTS]

  1. 1.

SDC and DP methods are built upon common statistical foundations that make
different but necessary compromises in conceptualizing privacy as properties
of a particular database or as a schema.

  2. 2.

SDP is inseparable from the study of data generating processes, as mechanism
implementations introduce new privacy-preserving errors to be treated
holistically alongside other error sources.

  3. 3.

Both SDC and DP can suffer from model misspecification, and addressing this
misspecification statistically can help improve our understanding of privacy
and utility guarantees.

  4. 4.

Future SDP research should address open statistical problems typically left
unarticulated by theoretical SDP research, such as valid statistical
inference, computational tractability, and compatibility with probability
models, and their interplay.

## DISCLOSURE STATEMENT

The authors are not aware of any affiliations, memberships, funding, or
financial holdings that might be perceived as affecting the objectivity of
this review.

## ACKNOWLEDGMENTS

A.S. would like to acknowledge Vishesh Karwa and late Steve Fienberg for many
early discussions and sharing of ideas on validity of privacy-preserving
statistical inference; this paper is in honor to them and to our joint work
that was never completed. The authors are supported in part by NSF Awards No.
SES-1853209 and NCSES-BAA 49100421C0022 to The Pennsylvania State University.

## References

  * Abowd et al. (2021) Abowd J, Ashmead R, Cumings-Menon R, Garfinkel S, Kifer D, et al. 2021. An Uncertainty Principle is a Price of Privacy-Preserving Microdata. Advances in Neural Information Processing Systems 34
  * Abowd et al. (2019) Abowd J, Kifer D, Moran B, Ashmead R, Sexton W. 2019. Census TopDown Algorithm: Differentially Private Data, Incremental Schemas, and Consistency with Public Knowledge
  * Abowd (2021) Abowd JM. 2021. Third Declaration of John M. Abowd in ”Fair Lines America Foundation, Inc. v. United States Department of Commerce and United States Bureau of the Census”
  * Arnold & Neunhoeffer (2020) Arnold C, Neunhoeffer M. 2020. Really Useful Synthetic Data–A Framework to Evaluate the Quality of Differentially Private Synthetic Data. arXiv preprint arXiv:2004.07740
  * Asi & Duchi (2020) Asi H, Duchi JC. 2020. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms, In Advances in Neural Information Processing Systems, eds. H Larochelle, M Ranzato, R Hadsell, MF Balcan, H Lin, vol. 33, pp. 14106–14117, Curran Associates, Inc.
  * Avella-Medina (2021) Avella-Medina M. 2021. Privacy-preserving parametric inference: a case for robust statistics. Journal of the American Statistical Association 116(534):969–983
  * Awan et al. (2019) Awan J, Kenney A, Reimherr M, Slavković A. 2019. Benefits and pitfalls of the exponential mechanism with applications to hilbert spaces and functional pca, In International Conference on Machine Learning, pp. 374–384, PMLR
  * Awan & Slavković (2018) Awan J, Slavković A. 2018. Differentially private uniformly most powerful tests for binomial data. Advances in Neural Information Processing Systems 31:4208–4218
  * Awan & Slavković (2020) Awan J, Slavković A. 2020. Structure and sensitivity in differential privacy: Comparing k-norm mechanisms. Journal of the American Statistical Association :1–20
  * Beaumont (2019) Beaumont MA. 2019. Approximate bayesian computation. Annual review of statistics and its application 6:379–403
  * Boucheron et al. (2013) Boucheron S, Lugosi G, Massart P. 2013. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press
  * Boulemtafes et al. (2020) Boulemtafes A, Derhab A, Challal Y. 2020. A review of privacy-preserving techniques for deep learning. Neurocomputing 384:21–45
  * Bousquet et al. (2003) Bousquet O, Boucheron S, Lugosi G. 2003. Introduction to statistical learning theory, In Summer school on machine learning, pp. 169–207, Springer
  * Bowen & Snoke (2019) Bowen CM, Snoke J. 2019. Comparative study of differentially private synthetic data algorithms from the NIST PSCR differential privacy synthetic data challenge. arXiv preprint arXiv:1911.12704
  * Boyd & Sarathy (2022) Boyd D, Sarathy J. 2022. Differential Perspectives: Epistemic Disconnects Surrounding the US Census Bureau’s Use of Differential Privacy. Harvard Data Science Review (forthcoming)
  * Bun et al. (2020) Bun M, Drechsler J, Gaboardi M, McMillan A. 2020. Controlling privacy loss in survey sampling. arXiv preprint arXiv:2007.12674
  * Bun & Steinke (2016) Bun M, Steinke T. 2016. Concentrated differential privacy: Simplifications, extensions, and lower bounds, In Theory of Cryptography Conference, pp. 635–658, Springer
  * Canonne et al. (2020) Canonne CL, Kamath G, Steinke T. 2020. The discrete gaussian for differential privacy. Advances in Neural Information Processing Systems 33:15676–15688
  * Carroll et al. (2006) Carroll RJ, Ruppert D, Stefanski LA, Crainiceanu CM. 2006. Measurement Error in Nonlinear Models. Chapman and Hall
  * Carvalho et al. (2019) Carvalho DV, Pereira EM, Cardoso JS. 2019. Machine learning interpretability: A survey on methods and metrics. Electronics 8(8):832
  * Chaudhuri et al. (2011) Chaudhuri K, Monteleoni C, Sarwate AD. 2011. Differentially private empirical risk minimization. Journal of Machine Learning Research 12(3)
  * Chaudhuri et al. (2012) Chaudhuri K, Sarwate A, Sinha K. 2012. Near-optimal differentially private principal components. Advances in neural information processing systems 25
  * Cohen (2012) Cohen JE. 2012. What privacy is for. Harv. L. Rev. 126:1904
  * Cummings et al. (2019) Cummings R, Gupta V, Kimpara D, Morgenstern J. 2019. On the compatibility of privacy and fairness, In Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization, pp. 309–315
  * Cummings et al. (2021) Cummings R, Kaptchuk G, Redmiles EM. 2021. ” I need a better description”: An Investigation Into User Expectations For Differential Privacy, In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 3037–3052
  * Dalenius (1977) Dalenius T. 1977. Towards a methodology for statistical disclosure control. statistik Tidskrift 15(429-444):1–2
  * Desfontaines & Pejó (2019) Desfontaines D, Pejó B. 2019. Sok: differential privacies. arXiv preprint arXiv:1906.01337
  * Dinur & Nissim (2003) Dinur I, Nissim K. 2003. Revealing information while preserving privacy, In Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 202–210
  * Dobra et al. (2009) Dobra A, Fienberg SE, Rinaldo A, Slavkovic A, Zhou Y. 2009. Algebraic statistics and contingency table problems: Log-linear models, likelihood estimation, and disclosure limitation. In Emerging applications of algebraic geometry. Springer, New York, NY, 63–88
  * Domingo-Ferrer & Mateo-Sanz (2002) Domingo-Ferrer J, Mateo-Sanz JM. 2002. Practical data-oriented microaggregation for statistical disclosure control. IEEE Transactions on Knowledge and data Engineering 14(1):189–201
  * Domingo-Ferrer et al. (2021) Domingo-Ferrer J, Sánchez D, Blanco-Justicia A. 2021. The limits of differential privacy (and its misuse in data release and machine learning). Communications of the ACM 64(7):33–35
  * Domingo-Ferrer & Torra (2003) Domingo-Ferrer J, Torra V. 2003. Disclosure risk assessment in statistical microdata protection via advanced record linkage. Statistics and Computing 13(4):343–354
  * Dong et al. (2019) Dong J, Roth A, Su WJ. 2019. Gaussian differential privacy. arXiv preprint arXiv:1905.02383
  * Drechsler & Reiter (2010) Drechsler J, Reiter JP. 2010. Sampling with synthesis: A new approach for releasing public use census microdata. Journal of the American Statistical Association 105(492):1347–1357
  * Duchi et al. (2018) Duchi JC, Jordan MI, Wainwright MJ. 2018. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association 113(521):182–201
  * Duncan & Pearson (1991) Duncan GT, Pearson RW. 1991. Enhancing access to microdata while protecting confidentiality: Prospects for the future. Statistical Science 6(3):219–232
  * Dwork et al. (2006a) Dwork C, Kenthapadi K, McSherry F, Mironov I, Naor M. 2006a. Our data, ourselves: Privacy via distributed noise generation, In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 486–503, Springer
  * Dwork & Lei (2009) Dwork C, Lei J. 2009. Differential Privacy and Robust Statistics, In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, p. 371–380, New York, NY, USA: Association for Computing Machinery
  * Dwork et al. (2006b) Dwork C, McSherry F, Nissim K, Smith A. 2006b. Calibrating noise to sensitivity in private data analysis, In Theory of cryptography conference, pp. 265–284, Springer
  * Dwork & Naor (2010) Dwork C, Naor M. 2010. On the difficulties of disclosure prevention in statistical databases or the case for differential privacy. Journal of Privacy and Confidentiality 2(1)
  * Dwork et al. (2014) Dwork C, Roth A, others. 2014. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science 9(3-4):211–407
  * Dwork et al. (2010) Dwork C, Rothblum GN, Vadhan S. 2010. Boosting and differential privacy, In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 51–60, IEEE
  * Dwork et al. (2017) Dwork C, Smith A, Steinke T, Ullman J. 2017. Exposed! a survey of attacks on private data. Annual Review of Statistics and Its Application 4:61–84
  * Evfimievski et al. (2003) Evfimievski A, Gehrke J, Srikant R. 2003. Limiting privacy breaches in privacy preserving data mining, In Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 211–222
  * Fearnhead & Prangle (2012) Fearnhead P, Prangle D. 2012. Constructing summary statistics for approximate Bayesian computation : semi-automatic approximate Bayesian computation. Journal of the Royal Statistical Society. Series B (Statistical Methodology) 74(3):419–474
  * Fienberg & Steele (1998) Fienberg SE, Steele RJ. 1998. Disclosure limitation using perturbation and related methods for categorical data. Journal of Official Statistics 14(4):485
  * Foulds et al. (2016) Foulds J, Geumlek J, Welling M, Chaudhuri K. 2016. On the theory and practice of privacy-preserving Bayesian data analysis. arXiv preprint arXiv:1603.07294
  * Franconi & Polettini (2004) Franconi L, Polettini S. 2004. Individual risk estimation in $$\mu$$-Argus: A review, In International Workshop on Privacy in Statistical Databases, pp. 262–272, Springer
  * Ganesh & Talwar (2020) Ganesh A, Talwar K. 2020. Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC, In Advances in Neural Information Processing Systems, eds. H Larochelle, M Ranzato, R Hadsell, MF Balcan, H Lin, vol. 33, pp. 7222–7233, Curran Associates, Inc.
  * Garfinkel et al. (2019) Garfinkel S, Abowd J, Martindale C. 2019. Understanding database reconstruction attacks on public data. Communications of the ACM 62:46–53
  * Ghosh et al. (2012) Ghosh A, Roughgarden T, Sundararajan M. 2012. Universally Utility-Maximizing Privacy Mechanisms. SIAM Journal on Computing 41(6):1673–1693
  * Gong (2019) Gong R. 2019. Exact inference with approximate computation for differentially private data via perturbations. arXiv preprint arXiv:1909.12237
  * Green (2021) Green B. 2021. Escaping the” Impossibility of Fairness”: From Formal to Substantive Algorithmic Fairness. arXiv preprint arXiv:2107.04642
  * Groves et al. (2011) Groves RM, Fowler FJ, Couper MP, Lepkowski JM, Singer E, Tourangeau R. 2011. Survey Methodology. Wiley Series in Survey Methodology. Wiley
  * Hardin & Hilbe (2002) Hardin JW, Hilbe JM. 2002. Generalized estimating equations. chapman and hall/CRC
  * Hardt & Talwar (2010) Hardt M, Talwar K. 2010. On the geometry of differential privacy, In Proceedings of the forty-second ACM symposium on Theory of computing, pp. 705–714
  * Hundepool et al. (2012) Hundepool A, Domingo-Ferrer J, Franconi L, Giessing S, Nordholt ES, et al. 2012\. Statistical disclosure control. John Wiley \& Sons
  * Jordon et al. (2019) Jordon J, Yoon J, van der Schaar M. 2019. Differentially Private Bagging: Improved utility and cheaper privacy than subsample-and-aggregate. Advances in Neural Information Processing Systems 32
  * Kairouz et al. (2021) Kairouz P, McMahan HB, Avent B, Bellet A, Bennis M, et al. 2021. Advances and open problems in federated learning. Foundations and Trends®in Machine Learning 14(1–2):1–210
  * Karr (2010) Karr AF. 2010. Secure statistical analysis of distributed databases, emphasizing what we don’t know. Journal of Privacy and Confidentiality 1(2)
  * Karwa et al. (2017) Karwa V, Krivitsky PN, Slavković AB. 2017. Sharing social network data: differentially private estimation of exponential family random-graph models. Journal of the Royal Statistical Society Series C 66(3):481–500
  * Karwa & Slavković (2016) Karwa V, Slavković A. 2016. Inference using noisy degrees: Differentially private $$\beta$$-model and synthetic graphs. Ann. Statist. 44(1):87–112
  * Karwa & Vadhan (2017) Karwa V, Vadhan S. 2017. Finite sample differentially private confidence intervals. arXiv preprint arXiv:1711.03908
  * Kasiviswanathan & Smith (2008) Kasiviswanathan SP, Smith A. 2008. A note on differential privacy: Defining resistance to arbitrary side information. CoRR abs/0803.3946
  * Kenny et al. (2021) Kenny CT, Kuriwaki S, McCartan C, Rosenman E, Simko T, Imai K. 2021. The impact of the US Census Disclosure Avoidance System on redistricting and voting rights analysis. arXiv preprint arXiv:2105.14197
  * Kifer & Machanavajjhala (2011) Kifer D, Machanavajjhala A. 2011. No free lunch in data privacy, In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pp. 193–204
  * Kifer & Machanavajjhala (2014) Kifer D, Machanavajjhala A. 2014. Pufferfish: A framework for mathematical privacy definitions. ACM Transactions on Database Systems (TODS) 39(1):1–36
  * Kifer et al. (2012) Kifer D, Smith A, Thakurta A. 2012. Private convex empirical risk minimization and high-dimensional regression, In Conference on Learning Theory, pp. 21–25, JMLR Workshop and Conference Proceedings
  * Li et al. (2007) Li N, Li T, Venkatasubramanian S. 2007. t-closeness: Privacy beyond k-anonymity and l-diversity, In 2007 IEEE 23rd International Conference on Data Engineering, pp. 106–115, IEEE
  * Li et al. (2012) Li N, Qardaji W, Su D. 2012. On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy, In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pp. 32–33
  * Lindell & Pinkas (2009) Lindell Y, Pinkas B. 2009. Secure Multiparty Computation for Privacy-Preserving Data Mining. Journal of Privacy and Confidentiality 1(1)
  * Liu et al. (2016) Liu C, Chakraborty S, Mittal P. 2016. Dependence Makes You Vulnberable: Differential Privacy Under Dependent Tuples., In NDSS Symposium
  * Machanavajjhala et al. (2007) Machanavajjhala A, Kifer D, Gehrke J, Venkitasubramaniam M. 2007. l-diversity: Privacy beyond k-anonymity. ACM Transactions on Knowledge Discovery from Data (TKDD) 1(1):3–es
  * Martin (2011) Martin GRR. 2011. A Game of Thrones. Bantam
  * McClure & Reiter (2012) McClure D, Reiter JP. 2012. Differential Privacy and Statistical Disclosure Risk Measures: An Investigation with Binary Synthetic Data. Trans. Data Privacy 5(3):535–552
  * McKenna (2019) McKenna L. 2019. Disclosure avoidance techniques used for the 1960 through 2010 decennial censuses of population and housing public use microdata samples. Washington, DC: United States Census Bureau (Working Paper)
  * McKenna et al. (2018) McKenna R, Miklau G, Hay M, Machanavajjhala A. 2018. Optimizing error of high-dimensional statistical queries under differential privacy. Proceedings of the VLDB Endowment 11(10):1206–1219
  * McKenna et al. (2019) McKenna R, Sheldon D, Miklau G. 2019. Graphical-model based estimation and inference for differential privacy, In International Conference on Machine Learning, pp. 4435–4444, PMLR
  * McSherry & Talwar (2007) McSherry F, Talwar K. 2007. Mechanism design via differential privacy, In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pp. 94–103, IEEE
  * McSherry (2009) McSherry FD. 2009. Privacy integrated queries: an extensible platform for privacy-preserving data analysis, In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pp. 19–30
  * Minami et al. (2016) Minami K, Arai H, Sato I, Nakagawa H. 2016. Differential privacy without sensitivity, In Advances in Neural Information Processing Systems, pp. 956–964
  * Mironov (2012) 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, pp. 650–661
  * Mitchell et al. (2021) Mitchell S, Potash E, Barocas S, D’Amour A, Lum K. 2021. Algorithmic fairness: Choices, assumptions, and definitions. Annual Review of Statistics and Its Application 8:141–163
  * Nissim et al. (2007) Nissim K, Raskhodnikova S, Smith A. 2007. Smooth sensitivity and sampling in private data analysis, In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 75–84
  * Ohm (2009) Ohm P. 2009. Broken promises of privacy: Responding to the surprising failure of anonymization. UCLA l. Rev. 57:1701
  * Raghunathan (2021) Raghunathan TE. 2021. Synthetic data. Annual Review of Statistics and Its Application 8:129–140
  * Reimherr & Awan (2019) Reimherr M, Awan J. 2019. KNG: The k-norm gradient mechanism. Advances in Neural Information Processing Systems 32
  * Rogaway (2015) Rogaway P. 2015. The Moral Character of Cryptographic Work. IACR Cryptol. ePrint Arch. 2015:1162
  * Seeman (2022) Seeman J. 2022. The Politics of Formal Privacy’s Axioms. Submitted.
  * Seeman & Brummet (2021) Seeman J, Brummet Q. 2021. Posterior Risk and Utility from Private Synthetic Weighted Survey Data, In World Meeting of the International Society for Bayesian Analysis (ISBA)
  * Seeman et al. (2021) Seeman J, Reimherr M, Slavković A. 2021. Exact Privacy Guarantees for Markov Chain Implementations of the Exponential Mechanism with Artificial Atoms. Advances in Neural Information Processing Systems
  * Seeman et al. (2020) Seeman J, Slavković A, Reimherr M. 2020. Private Posterior Inference Consistent with Public Information: a Case Study in Small Area Estimation from Synthetic Census Data. Privacy in Statistical Databases
  * Seeman et al. (2022) Seeman J, Slavkovic A, Reimherr M. 2022. A Formal Privacy Framework for Partially Private Data. arXiv preprint arXiv:2204.01102
  * Selbst et al. (2019) Selbst AD, Boyd D, Friedler SA, Venkatasubramanian S, Vertesi J. 2019. Fairness and abstraction in sociotechnical systems, In Proceedings of the conference on fairness, accountability, and transparency, pp. 59–68
  * Skinner (2009) Skinner C. 2009. Statistical disclosure control for survey data. In Handbook of statistics, vol. 29. Elsevier, 381–396
  * Skinner & Shlomo (2008) Skinner CJ, Shlomo N. 2008. Assessing Identification Risk in Survey Microdata Using Log-Linear Models. Journal of the American Statistical Association 103:989–1001
  * Slavkovic (2013) Slavkovic A. 2013. Steve the matchmaker: the marriage of statistics and computer science in the world of data privacy. CHANCE 26(4):4–7
  * Slavkovic & Molinari (2021) Slavkovic A, Molinari R. 2021. Perturbed M-Estimation: A Further Investigation of Robust Statistics for Differential Privacy
  * Slavković (2004) Slavković AB. 2004. Statistical Disclosure Limitation Beyond the Margins. Ph.D. thesis, Carnegie Mellon University
  * Slavković & Karwa (2019) Slavković AB, Karwa V. 2019. Statistical Inference and Privacy, Part I, In Simons Institute Workshop on Data Privacy: Foundations and Applications
  * Smith (2011) Smith A. 2011. Privacy-preserving statistical estimation with optimal convergence rates, In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 813–822
  * Snoke et al. (2018a) Snoke J, Brick TR, Slavković A, Hunter MD. 2018a. Providing accurate models across private partitioned data: Secure maximum likelihood estimation. The Annals of Applied Statistics 12(2):877–914
  * Snoke et al. (2018b) Snoke J, Raab GM, Nowok B, Dibben C, Slavkovic A. 2018b. General and specific utility measures for synthetic data. Journal of the Royal Statistical Society: Series A (Statistics in Society) 181(3):663–688
  * Snoke & Slavković (2018) Snoke J, Slavković A. 2018. pMSE mechanism: differentially private synthetic data with maximal distributional similarity, In International Conference on Privacy in Statistical Databases, pp. 138–159, Springer
  * Song et al. (2013) Song S, Chaudhuri K, Sarwate AD. 2013. Stochastic gradient descent with differentially private updates, In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245–248, IEEE
  * Song et al. (2017) Song S, Wang Y, Chaudhuri K. 2017. Pufferfish privacy mechanisms for correlated data, In Proceedings of the 2017 ACM International Conference on Management of Data, pp. 1291–1306
  * Stoller (2011) Stoller SD. 2011. Trust Management in Databases.
  * Sweeney (2002) Sweeney L. 2002. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10(05):557–570
  * Technical University of Munich (2019) Technical University of Munich. 2019. A Song of Ice and Data
  * Torkzadehmahani et al. (2019) Torkzadehmahani R, Kairouz P, Paten B. 2019. Dp-cgan: Differentially private synthetic data and label generation, In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, p. 0
  * Tsiatis (2006) Tsiatis AA. 2006. Semiparametric theory and missing data. Springer
  * Ullman (2021) Ullman J. 2021. Statistical Inference is Not a Privacy Violation
  * Vadhan (2017) Vadhan S. 2017. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography. Springer, 347–450
  * Vatsalan et al. (2013) Vatsalan D, Christen P, Verykios VS. 2013. A taxonomy of privacy-preserving record linkage techniques. Information Systems 38(6):946–969
  * Vershynin (2018) Vershynin R. 2018. High-dimensional probability: An introduction with applications in data science, vol. 47. Cambridge university press
  * Vietri et al. (2020) Vietri G, Tian G, Bun M, Steinke T, Wu S. 2020. New oracle-efficient algorithms for private synthetic data release, In International Conference on Machine Learning, pp. 9765–9774, PMLR
  * Vu & Slavkovic (2009) Vu D, Slavkovic A. 2009. Differential Privacy for Clinical Trial Data: Preliminary Evaluations, In Proceedings of the 2009 IEEE International Conference on Data Mining Workshops, ICDMW ’09, pp. 138–143, Washington, DC, USA: IEEE Computer Society
  * Wang et al. (2018) Wang Y, Kifer D, Lee J, Karwa V. 2018. Statistical Approximating Distributions Under Differential Privacy. Journal of Privacy and Confidentiality 8(1)
  * Wang et al. (2015) Wang YX, Fienberg S, Smola A. 2015. Privacy for free: Posterior sampling and stochastic gradient monte carlo, In International Conference on Machine Learning, pp. 2493–2502, PMLR
  * Warner (1965) Warner SL. 1965. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association 60(309):63–69
  * Wasserman & Zhou (2010) Wasserman L, Zhou S. 2010. A statistical framework for differential privacy. Journal of the American Statistical Association 105(489):375–389
  * Westeros.org (2014) Westeros.org. 2014. A Wiki of Ice and Fire
  * Westin (1968) Westin AF. 1968. Privacy and freedom. Washington and Lee Law Review 25(1):166
  * Willenborg & De Waal (1996) Willenborg L, De Waal T. 1996. Statistical disclosure control in practice, vol. 111. Springer Science \& Business Media
  * Winkler (2004) Winkler WE. 2004. Re-identification Methods for Masked Microdata, In Privacy in Statistical Databases, eds. Domingo-Ferrer Josep, , V Torra, pp. 216–230, Berlin, Heidelberg: Springer Berlin Heidelberg