# The Epistemology behind Covariate Adjustment

Grayson L. Baird 111Corresponding author: 535 Eddy St. Providence, RI 02903
<EMAIL_ADDRESS>
Brown University
and
Stephen L. Bieber
University of Wyoming

###### Abstract

It is often asserted that to control for the effects of confounders, one
should include the confounding variables of concern in a statistical model as
a covariate. Conversely, it is also asserted that control can only be
concluded by design, where the results from an analysis can only be
interpreted as evidence of an effect because the design controlled for the
cause. To suggest otherwise is said to be a fallacy of cum hoc ergo propter
hoc. Obviously, these two assertions create a conundrum: How can the effect of
confounder be controlled for with analysis instead of by design without
committing cum hoc ergo propter hoc? The present manuscript answers this
conundrum.

Keywords: multicollinearity, collinearity, statistical control, confounders,
covariate adjustment

##  1 Introduction

It is often asserted that to control for the effects of confounds, one should
include the confounding variables of concern in a statistical model as a
covariate222Here and throughout this manuscript, a covariate is defined
exclusively as an additive term in a model that is not the regressor of
interest. (e.g., Wysocki, Lawson, Rhemtulla, 2022; von Elm et al., 2007).
Conversely, it is also asserted that control can only be achieved by design,
where the results from an analysis can only be interpreted as evidence of an
effect because the design controlled for the cause; to suggest otherwise is
said to be a fallacy of cum hoc ergo propter hoc: “with this, therefore
because of this” (Fischer, 1970, p. 167). Obviously, these two assertions
create a conundrum: Can the effect of a confound be controlled for by analysis
instead of by design without committing cum hoc ergo propter hoc? The purpose
of the present manuscript is to answer this conundrum.

##  2 Ex Post Facto Data

When modeling data from an Ex Post Facto design, a common concern is how to
control for confounding variables that likely exist but, given the nature of
the non-experimental (observational) data, were not controlled for by design.
A common solution to this problem is to include the confounding variables of
concern in a statistical model as covariates, a practice often referred to as
covariate adjustment. Covariate adjustment is simply the removal of the shared
correlation among a regressor of interest, the outcome, and one or more
confounding regressors of concern (the mathematics behind this are provided in
the next section). It is believed that the regressor of interest, when
adjusted, therefore, represents the relationship between the regressor of
interest and the outcome controlling for the confounding regressor or
regressors of concern.

For example, let us assume that Y is an outcome of interest while X1 is a
regressor of interest and X2 is another regressor, a confound of concern,
resulting in the following model multiple regression model$:$ Ŷ=b0+b1X1+b2X2.
Mathematically, when X2 is placed in a model, the relationship between Y and
X1 is adjusted (i.e., b1.2) when the shared correlation between X1, Y, and X2
is removed. But is control over a confound actually achieved with adjustment
by removing this shared correlation?

To be clear, if a confound in question were a regressor in the model, then the
model would be adjusted—the shared correlation from that confounding regressor
would be removed, thus controlling for that confound. However, the belief that
adjustment is evidence itself of control of a confound is a logical fallacy
known as affirming the consequent333or in psychology, the contingency symmetry
bias (Imai et al., 2021).: here, if control of a confound is achieved, then
the coefficient will be adjusted; therefore, an adjusted coefficient is
evidence of a controlled confound. The logical fallacy is committed because
adjustment is a necessary condition of control but not a sufficient condition
of control (Darner, 1987). The reason for this is straightforward: as the
shared correlation is removed from both regressors, this removal is
indiscriminate to cause itself—did X1 cause the shared correlation, did X2
cause the shared correlation, or was the shared correlation caused by X3,
which was not in the model444referred to as the causal-arrow ambiguity (Meehl,
1970).? Because covariate adjustment removes all shared correlation regardless
of the cause, as a consequence, variance caused by the confound, if any, as
well as variance not caused by a confound (“artifact”) will be removed
jointly.

The belief that adjustment is evidence of control of a confound is an example
of postdiction555or in psychology, hindsight bias (Fischhoff, 1975).—an
explanation after the fact, which relies on another logical fallacy known as
post hoc ergo propter hoc: after this, therefore, because of this (Fischer,
1970, p. 166). Here, after an adjustment occurs, it is, therefore, because of
the confound. Conversely, if no adjustment occurs, it is, therefore, because
there was no confound, which also relies on the logical fallacy of negative
proof or confusing the absence of evidence with evidence of absence (Fischer,
1970, p. 47). The logical fallacy is committed because other counterfactuals
cannot be considered, such as adjustment not occurring but the confound still
existing (i.e., undercorrelation, due to poor measurement, Kahneman, 1965), or
more aptly, adjustment occurring but not because of the intended confound. As
noted in the preceding paragraph, the latter outcome is the direct threat to
the verisimilitude of covariate adjustment as a means of confound
control—although covariate adjustment can control for confounds, the problem
is it is impossible to determine the degree to which the removal is due to the
confound, if any, and the degree to which the removal is not due to the
confound but instead artifact. But why is this a problem?

If the shared correlation that is removed is solely the confound, then the
adjusted model reflects the population without a confound, as described by
Bring (1994). However, if the removal includes shared correlation that is both
confound and artifact, then what population does this adjusted model now
represent? What does the model represent if the removal includes no confound
and only artifact? In both cases, the adjusted model reflects neither the
original population nor even the intended adjusted population—a discrepancy
between the intended adjusted population and the population actually
represented by the adjustment—known as model bias. But can this model bias be
prevented?

Wysocki, Lawson, and Rhemtulla (2022) explicitly acknowledge that incorrect
model adjustment must introduce bias in estimation. They hold that to prevent
such bias, one needs to justify covariate adjustment with theory. Indeed, as
far back as 1957, Kempthorne warns

> “the adjustment of data should be based on knowledge of how the factor which
> is being adjusted for actually produces its effect. An arbitrarily chosen
> adjustment formula may produce bias rather than remove the systematic
> difference. It is this fact which tends to vitiate the uses of the analysis
> of covariance recommended in most books on the analysis of experiments.” (p.
> 284).

Obviously, theory-based adjustment is better than blind adjustment, such as
the default adjustment of demographic variables, but theory alone cannot
differentiate between confound and artifact from the shared correlation, and
believing so relies upon yet another logical fallacy—special pleading—the
application of a double standard or “if X then Y, but not when it hurts my
agrument”. (Fischer, 1970, p. 110). Here, the logical fallacy is committed
when it is believed that covariate adjustment can serve as evidence for
control simply because doing so is justified by some theory.

In conclusion, if covariate adjustment only demonstrates that shared
correlation was removed, not that the confound and only the confound was
removed in that correlation, then the belief that covariate adjustment serves
as evidence of control over a confound is explicitly cum hoc ergo propter hoc.
A similar account of this fallacy was well documented by Meehl (1970), who
observed

> “it makes no sense to speak of a correlation as “spurious” or “in need of
> correction” unless a possible error in causal-theoretical interpretation is
> envisaged … In every instance that I have come across in which the
> investigator felt it necessary to employ partial correlation, analysis of
> covariance … to ’avoid the influence’ of an alleged nuisance variable, the
> rationale of such a procedure lay in his wish to conclude with a causal-
> theoretical inference or, at least, a counterfactual conditional of some
> kind.”(p.8)

In summary, the logical fallacy is committed not because covariate adjustment
is unable to control for confounds but rather because covariate adjustment as
a means of control is not falsifiable, and, as such, therefore, adjustment
cannot serve as evidence of control of a confound.

##  3 Experimental Data

In the previous section, epistemology alone demonstrated why covariate
adjustment could not serve as evidence of control of confounds for data from
an Ex Post Facto design, therefore revealing that the conundrum posed is both
easily resolved and an issue not of mathematics but rather the
misinterpretation of mathematics. If covariate adjustment cannot serve as
evidence of control for confounds, then what can? Design can control for
confounds, both known and unknown, by way of randomization666restriction is
another method of control (of a known confound) by way of design.. Here,
control of confounds is achieved because the process of randomization
guarantees that any observed differences between randomized groups must be due
to chance variation, save for that which is being experimentally manipulated.
If randomization controls for confounds by design a priori of observation,
then what would covariate adjustment achieve post hoc of observation?

Nuisance factors are undesired sources of systematic variation (bias) and
random variation (error) occurring in an experiment that ultimately affect the
outcome of interest (Kirk, 2013). It is believed that when these nuisance
factors have been measured, referred to as “nuisance variables,” these
nuisance variables, therefore, can be controlled for using covariate
adjustment. For example, if an imbalance of confounding variables between
randomized groups is observed, then it is believed that randomization either
created bias (Egbewale, Lewis, and Sim, 2014) or at least failed to control
for bias from these confounding variables (Kahan et al., 2014). Another
popular justification for using covariate adjustment with randomized data is
the belief that adjustment reduces error between the randomized groups,
thereby increasing statistical efficiency (Kahan et al., 2014; Pocock et al.,
2002).

###  3.1 Post-randomization control of confounds

The former belief, that covariate adjustment controls for bias that
randomization either created or failed to control, is predicated on three
assumptions. The first assumption is that if confound imbalance is observed
(at any defined alpha level), then the observed imbalance is evidence of a
true difference between randomized groups—a bias (e.g., more males in one
group versus another). The second assumption is that this observed bias is,
therefore, evidence that randomization failed to control for the confounding
variables of concern—the point of randomization is to control for bias; thus,
if bias resulted after randomization, then randomization failed. The third
assumption is that because randomization failed to control for bias, then the
resulting bias can be controlled for using post hoc covariate adjustment.

The first assumption is easily refuted using fundamental statistical inference
theory—hypothesis testing. Any difference observed in confounding variables
between randomized groups must be due to chance variation; therefore,
inferring a true difference in confounds between the randomized groups—a
bias—is, by definition, a Type I error (a false discovery error) because the
null is known to be true by design, so rejecting the null must be in error
(Begg, 1987). The second assumption is also easily refuted. Imbalance cannot
serve as evidence of bias because imbalance is a property of randomness—if
randomization guaranteed balance across all factors, then randomization would
be non-random as there would be a systematic selection bias against imbalance.
Although possible, it is very unlikely that randomization will result in
balance across all confounds, measured or unmeasured.

In fact, the belief that confound imbalance is evidence that randomization
“failed” to control for bias is the logical fallacy known as the fallacy of
regression—the misperception of random events as non-random (Tversky and
Kahneman, 1974), illustrated by Edwards Deming’s red bead experiment (see
Boardman, 1994). Here, because confound balance was not achieved, therefore,
randomization “failed” to control for confound bias. The fallacy is committed
because the distribution of confounds between randomized groups is, by design,
random, therefore, any resulting imbalance, which must also be random, cannot
serve as evidence that randomization “failed”. Relatedly, the smaller the
sample size, the more likely that confound imbalance will be observed.
Therefore, the belief that more imbalance is evidence of more failure, not
more random variability due to smaller sample sizes, is the insensitivity-to-
sample-size cognitive bias (Tversky and Kahneman, 1974)—the misperception that
variability, in this case, the chance of imbalance, does not change with
sample size; simply, randomization cannot “fail” at any sample size.

The third assumption is easily refuted when considering the case in which
randomization resulted in a confound imbalance between randomized groups to
the extreme as if randomization had not even taken place. The belief that post
hoc covariate adjustment could control for this confound imbalance falls
victim to the same logical fallacies as if randomization had not taken place
(i.e., the Ex Post Facto design). And if this is the case for the most extreme
instance of confound imbalance, then it follows this would be the case for
lesser degrees of imbalance, too.

The solution to confound imbalance is obvious: replication—the random
imbalance of variables, confound or not, observed for a given trial will
balance out with several repeated trials—the random imbalance of variables
will average out over the long run777another solution is by design, using
balance block, urn, etc., though these solutions deviate from random and only
control measured and specified variables.. In this way, covariate adjustment
in response to these random imbalances will vary from trial to trial,
resulting in a game of adjustment Whac-A-MoleTM; any unintended model bias
that results from these adjustments can, therefore, be a source of replication
discordance in the literature that would otherwise not occur had covariate
adjustment not been used. Although this issue was touched upon theoretically
and empirically by de Boer et al. (2015), their solution—using theory to guide
covariate selection instead of random confound imbalance—rests upon logical
fallacies outlined in the preceding section.

Finally, some acknowledge that confound imbalances are random; however, they
still hold that not using covariate adjustment will still result in bias
(Sherry et al., 2023). Here, it is believed that if confounding variables are
selected with theory and a priori to randomization, then adjustment will
result in decreased bias (note: why randomization failed to control for this
bias is never explored). This line of reasoning is an improvement to blind
covariate adjustment as a reaction to random confound imbalance, though again,
it still falls victim to the same logical fallacies presented in the previous
section and, in particular, a special pleading.

###  3.2 Post-randomization control of error

The latter belief, that covariate adjustment controls for (or reduces) error,
is based on the knowledge that because covariate adjustment can explain some
variation that occurs in outcomes between randomized groups, covariate
adjustment reduces unexplained variance which in turn, increases statistical
efficiency. As Kahan et al. (2014) note, the greater the error that is
“reduced depends on the correlation between the covariates and the outcome;
the higher the correlation, the larger the increase in power”. Although this
certainly can be true, this reduction in unexplained variance can also come at
the cost of increased bias. The present section demonstrates how covariate
adjustment may reduce unaccounted-for variance but at the cost of introducing
bias into the model, where the inference and estimation of the adjusted model
become divorced from the original population it was intended to represent.

To demonstrate this, we will compare data that represent two possibilities:
data in which a nuisance variable does not correlate with the regressor of
interest but does correlate with the outcome and data in which a nuisance
variable correlates with the regressor of interest and the outcome jointly.
For simplicity and without loss of generality, the two-regressor model is
used, assuming randomization took place but without any manipulation. This is
done as the issue at hand deals with the “correlation between the covariates
and the outcome” (Kahan et al., 2014, p.2); thus, we will examine how
adjustment reduces the unaccounted-for variance (error) between the covariates
and outcome by explaining “nuisance” variation in isolation of any
manipulation. Thus, we show how bias is introduced with covariate adjustment,
even without experimental manipulation.

We will first define covariate adjustment by demonstrating the process by
which covariate adjustment is achieved for the multiple linear regression
model (MLR). Each step of this demonstration will provide graphical evidence,
using Ballantine Venn diagram (Cohen and Cohen, 1975; Baird and Bieber, 2023)
representing a 3-variable situation, mathematical equations, and empirical
evidence, using data from a simulation (code found in Appendix A).

####  3.2.1 No Covariate Adjustment

Again, let us assume that Y is an outcome of interest while X1 is a regressor
of interest and X2 is another regressor, the covariate, both of which relate
with Y. This is illustrated conceptually in Figure 1 as a Venn diagram, where
X1 and X2, represented as areas 1 and 2, respectively, are independent of each
other and both relate with Y, and the remainder is represented as area 3,
denoted as Y123. This is also represented as a covariance matrix in Figure 2,
defined as COV1 = [Y X1 X2]. When both regressors, X1 and X2, are uncorrelated
such that COV1(X1,X2)=0.00 and are placed together into the model, defined as
Ŷ=b0+b1X1+b2X2, the regressors need not be adjusted, as seen in Equations (1)
and (2).

Figure 1: Y123

$COV1=\begin{pmatrix}2.00&0.65&0.65\\\ 0.65&0.60&0.00\\\ 0.65&0.00&0.60\\\
\end{pmatrix}$

Figure 2: Matrix

$\begin{split}{\textup{\^{X}}_{1}}=({\textup{c}_{0}}+{\textup{c}_{2}}{\textup{X}_{2}})=0\\\
{\textup{X}_{1.2}}={\textup{X}_{1}}-{\textup{\^{X}}_{1}}={\textup{X}_{1}}\end{split}$
(1)

yielding a residualized regressor X1.2 and

$\begin{split}{\textup{\^{X}}_{2}}=({\textup{c}_{0}}+{\textup{c}_{1}}{\textup{X}_{1}})=0\\\
{\textup{X}_{2.1}}={\textup{X}_{2}}-{\textup{\^{X}}_{2}}={\textup{X}_{2}}\end{split}$
(2)

yielding a residualized regressor X2.1. In other words, if there is no shared
correlation between regressors and Y, then there is no need for covariate
adjustment and thus, both regressors simply reduced to themselves, X1 and X2,
respectively.

These regressors are then used to calculate the MLR coefficients, seen in
Equations (3) and (4).

$\begin{split}{\textup{b}_{1.2}}=\frac{\sum{\textup{X}_{1.2}}\cdot
Y}{\sum({\textup{X}_{1.2}})\textsuperscript{2}}={\textup{b}_{1}}=\frac{\sum{\textup{X}_{1}}\cdot
Y}{\sum({\textup{X}_{1}})\textsuperscript{2}}\\\
=\frac{6606.337}{6014.009}=1.099\end{split}$ (3)

$\begin{split}{\textup{b}_{2.1}}=\frac{\sum{\textup{X}_{2.1}}\cdot
Y}{\sum({\textup{X}_{2.1}})\textsuperscript{2}}={\textup{b}_{2}}=\frac{\sum{\textup{X}_{2}}\cdot
Y}{\sum({\textup{X}_{2}})\textsuperscript{2}}\\\
=\frac{6554.81}{6037.42}=1.090\end{split}$ (4)

These coefficients are then used to calculate the sums of squares of the
model, as seen in Equations (5) and (6):

$\begin{split}SS(X\textsubscript{1}|X\textsubscript{2})={\textup{b}_{1.2}}\sum{\textup{X}_{1.2}}\cdot
Y=SS(X\textsubscript{1})={\textup{b}_{1}}\sum{\textup{X}_{1}}\cdot Y\\\
=1.099\cdot 6606.34=7257.01\end{split}$ (5)

$\begin{split}SS(X\textsubscript{2}|X\textsubscript{1})={\textup{b}_{2.1}}\sum{\textup{X}_{2.1}}\cdot
Y=SS(X\textsubscript{2})={\textup{b}_{2}}\sum{\textup{X}_{2}}\cdot Y\\\
=1.090\cdot 6554.81=7116.53\end{split}$ (6)

and the sums of squares of the error of the model, as seen in Equation (7):

$SS(E)=\sum({\textup{Y}}-{\textup{\^{Y}}})\textsuperscript{2}=5760.98$ (7)

When the sums of squares for the regressors and the error are then added
together, the total sums of squares is the following

$\begin{split}SS({\textup{Total}})=({\textup{b}_{1.2}}\sum{\textup{X}_{1.2}}\cdot
Y)+({\textup{b}_{2.1}}\sum{\textup{X}_{2.1}}\cdot
Y)+\sum({\textup{Y}}-{\textup{\^{Y}}})\textsuperscript{2}\\\
=({\textup{b}_{1}}\sum{\textup{X}_{1}}\cdot
Y)+({\textup{b}_{2}}\sum{\textup{X}_{2}}\cdot
Y)+\sum({\textup{Y}}-{\textup{\^{Y}}})\textsuperscript{2}\\\
=7257.01+7116.53+5760.98=20134.51,\end{split}$ (8)

which is the same value888empirically, the small difference is due to
simulation and round-off error as the sums of squares of Y, as seen in
Equation (9)

$\sum{\textup{Y}}\textsuperscript{2}-\frac{(\sum{\textup{Y}})\textsuperscript{2}}{N}=20150.29-\frac{15506.23}{10000}=20148.74.$
(9)

For reference, again, this is illustrated conceptually in Figure 1, where the
outcome Y is comprised of the unique correlation with X1 (area 1), X2 (area
2), and error, (area 3), and will be denoted as Y123. The regression model,
conceptualized in Figure 3, is denoted as Ŷ\textsubscript{12.3}.

Figure 3: The regression model, Ŷ\textsubscript{12.3}, or the outcome, Y123

Figure 3 also conceptually represents the variance accounted for by the model,
where area 1 represents SS(X1), area 2 represents SS(X2), and area 3
represents SS(E), which added together represents SS(Total). This value is
quantified by the calculation of the coefficient of determination or R2:

${\textup{R}}\textsuperscript{2}=\frac{SS(Total)-SS(E)}{SS(Total)}=\frac{20134.51-5760.98}{20134.51}=.71$
(10)

or equivalently,

$\begin{split}{\textup{R}}\textsuperscript{2}=\frac{SS(X\textsubscript{1}|X\textsubscript{2})+SS(X\textsubscript{2}|X\textsubscript{1})}{SS(X\textsubscript{1}|X\textsubscript{1})+SS(X\textsubscript{2}|X\textsubscript{1})+SS(E)}=\frac{SS(X\textsubscript{1})+SS(X\textsubscript{2})}{SS(X\textsubscript{1})+SS(X\textsubscript{2})+SS(E)}\\\
=\frac{7257.01+7116.53}{7257.01+7116.53+5760.98}=.71.\end{split}$ (11)

This can be confirmed by comparing the variance components of the model,
${\sigma}_{\hat{Y}_{12.3}}^{2}$, with the variance components of the model
${\sigma}_{\hat{Y}_{12.3}}^{2}$ and error ${\sigma}_{e}\textsuperscript{2}$,
or ${\sigma}_{Y_{123}}^{2}$, as seen in Equation (12):

${\textup{R}}\textsuperscript{2}=\frac{{\sigma}_{\hat{Y}_{12.3}}^{2}}{{\sigma}_{Y_{123}}^{2}}=\frac{1.44}{2.02}=.71$
(12)

where

$\begin{split}{\sigma}_{\hat{Y}_{12.3}}^{2}={b}_{1.2}\textsuperscript{2}{\sigma}_{X1.2}\textsuperscript{2}+{b}_{2.1}\textsuperscript{2}{\sigma}_{X2.1}\textsuperscript{2}={b}_{1}\textsuperscript{2}{\sigma}_{X1}\textsuperscript{2}+{b}_{2}\textsuperscript{2}{\sigma}_{X2}\textsuperscript{2}\\\
=(1.099\cdot 0.60)+(1.090\cdot 0.60)=1.44\end{split}$ (13)

is the variance components of the model (areas 1 and 2 in Figure 3) and,

$\begin{split}{\sigma}_{Y_{123}}^{2}={b}_{1.2}\textsuperscript{2}{\sigma}_{X1.2}\textsuperscript{2}+{b}_{2.1}\textsuperscript{2}{\sigma}_{X2.1}\textsuperscript{2}+{\sigma}_{e}\textsuperscript{2}={b}_{1}\textsuperscript{2}{\sigma}_{X1}\textsuperscript{2}+{b}_{2}\textsuperscript{2}{\sigma}_{X2}\textsuperscript{2}+{\sigma}_{e}\textsuperscript{2}\\\
=(1.099\cdot 0.60)+(1.090\cdot 0.60)+0.576=2.02,\end{split}$ (14)

the total variance components of the model and error (areas 1, 2, and 3 in
Figure 3) which is also the same value as the variance of Y:

${\sigma}_{Y}\textsuperscript{2}={\sigma}_{Y_{123}}^{2}=2.02.$ (15)

The variance accounted for by the model can also be confirmed by summing the
squared standardized coefficients (area 1 and 2 in Figure 3), as seen in
Equation (16):

$\begin{split}{\textup{R}}\textsuperscript{2}={\beta}_{1.2}\textsuperscript{2}+{\beta}_{2.1}\textsuperscript{2}={\beta}_{1}\textsuperscript{2}+{\beta}_{2}\textsuperscript{2}\\\
=0.36+0.35=.71\end{split}$ (16)

where

$\begin{split}{\beta}_{1.2}=\frac{{b}_{1.2}\cdot{\sigma}_{X1.2}}{{\sqrt{{\sigma}_{Y_{123}}^{2}}}}={\beta}_{1}=\frac{{b}_{1}\cdot{\sigma}_{X1}}{{\sqrt{{\sigma}_{Y}^{2}}}}=\\\
\frac{1.099\cdot 0.78}{\sqrt{{1.42}}}=0.60\end{split}$ (17)

and

$\begin{split}{\beta}_{2.1}=\frac{{b}_{2.1}\cdot{\sigma}_{X2.1}}{{\sqrt{{\sigma}_{Y_{123}}^{2}}}}={\beta}_{2}=\frac{{b}_{2}\cdot{\sigma}_{X2}}{{\sqrt{{\sigma}_{Y}^{2}}}}=\\\
\frac{1.090\cdot 0.78}{\sqrt{{1.42}}}=0.60.\end{split}$ (18)

As illustrated in Figure 3 (area 2) and made obvious in Equations 12-14, the
inclusion of the covariate reduced the value of the unaccounted-for variance,
thereby increasing the statistical efficiency of the model. It is important to
note that while the inclusion of the covariate reduced the value of the error,
the sum of the variance components of the model still equal the variance of
the outcome as made evident with Equation 15 and illustrated when comparing
Figures 1 with 3.

####  3.2.2 Covariate Adjustment

Now let us consider when the regressors are not independent. This is
illustrated conceptually in Figure 4, where outcome Y is comprised of the
unique correlation of X1 (area 1), X2 (area 2), the shared correlation of X1
and X2 (area 4), and error (area 3), which will be denoted as Y1234. This is
also represented as a covariance matrix in Figure 5, defined as COV2 = [Y X1
X2].

Figure 4: Y1234

$COV2=\begin{pmatrix}2.00&0.65&0.65\\\ 0.65&0.60&0.25\\\ 0.65&0.25&0.60\\\
\end{pmatrix}$

Figure 5: Matrix Structure

A close inspection reveals Equations (19-22) are identical to Equations (1-4),
but the results differ dramatically when X1 and X2 share correlation with Y:

$\begin{split}{\textup{\^{X}}_{1}}=({\textup{c}_{0}}+{\textup{c}_{2}}{\textup{X}_{2}})\\\
{\textup{X}_{1.2}}={\textup{X}_{1}}-{\textup{\^{X}}_{1}}\end{split}$ (19)

what remains in X1 and Y (area 1 and 4) after removing X2 (removing area 2 and
4) is a residualized regressor, X1.2 (area 1) and

$\begin{split}{\textup{\^{X}}_{2}}=({\textup{c}_{0}}+{\textup{c}_{1}}{\textup{X}_{1}})\\\
{\textup{X}_{2.1}}={\textup{X}_{2}}-{\textup{\^{X}}_{2}}\end{split}$ (20)

what remains in X2 and Y (area 2 and 4) after removing X1 (removing area 1 and
4) is a residualized regressor, X2.1 (area 2). These adjusted (residualized)
regressors are then used to calculate the adjusted MLR coefficients in the
following manner999Frisch-Waugh-Lovell theorem; see Yule (1907), Frisch and
Waugh (1933), Lovell (1963).:

${\textup{b}_{1.2}}=\frac{\sum{\textup{X}_{1.2}}\cdot
Y}{\sum({\textup{X}_{1.2}})\textsuperscript{2}}=\frac{3871.54}{4984.37}=0.78$
(21)

${\textup{b}_{2.1}}=\frac{\sum{\textup{X}_{2.1}}\cdot
Y}{\sum({\textup{X}_{2.1}})\textsuperscript{2}}=\frac{3881.04}{4964.31}=0.78$
(22)

Because X1 and X2 are correlated with each other and Y, the shared correlation
has been removed via Equations (19-22), producing adjusted coefficients b1.2
and b2.1, represented as areas 1 and 2 in Figure 6, (cf. instead of non-
adjusted coefficients b1 and b2, represented in area area 1 and 2 in Figure
3). The model’s sums of squares101010Equations 19-22 represent the Type III or
unique sums of squares. To the authors’ knowledge, this is the first place
where the derivation for Type III sums of squares has been provided for
multiple linear regression. are then the following:

$SS(X\textsubscript{1}|X\textsubscript{2})={\textup{b}_{1.2}}\sum{\textup{X}_{1.2}}\cdot
Y=0.78\cdot 3871.54=3007.17$ (23)

$SS(X\textsubscript{2}|X\textsubscript{1})={\textup{b}_{2.1}}\sum{\textup{X}_{2.1}}\cdot
Y=0.78\cdot 3881.04=3034.14.$ (24)

When the sums of squares for the regressors and the error are then added
together, the total sums of squares is the following

$\begin{split}SS({\textup{Total}})=({\textup{b}_{1.2}}\sum{\textup{X}_{1.2}}\cdot
Y)+({\textup{b}_{2.1}}\sum{\textup{X}_{2.1}}\cdot
Y)+\sum({\text{Y}}-{\textup{\^{Y}}})\textsuperscript{2}\\\
=3007.17+3034.14+9843.36=15884.67\end{split}$ (25)

which is no longer the same value as the sums of squares of Y,

$\sum{\textup{Y}}\textsuperscript{2}-\frac{(\sum{\textup{Y}})\textsuperscript{2}}{N}=20150.29-\frac{15506.23}{10000}=20148.74$
(26)

a difference of 4264.07, or a 21 percent reduction in overall variance of Y.
If the shared variance is not contained in the sums of squares for either
regressor, then the shared variance cannot be contained in either the model
sums of squares or the total sums of squares (see Woolf, 1951; Baird and
Bieber, 2023). This is because the shared correlation was removed not once but
twice (Kerlinger and Pedhazur 1973, p. 46), making the shared correlation
absent from the model (Newton and Spurrell, 1967, p. 57; Kennedy, 1982, p. 63)
and the variance for which it accounts. As before, Figure 6 conceptually
represents the variance accounted for by the model, where area 1 represents
$SS(X\textsubscript{1}|X\textsubscript{2})$, area 2 represents
$SS(X\textsubscript{2}|X\textsubscript{1})$, and area 3 represents SS(E).

Figure 6: Regression model, Ŷ\textsubscript{12.34}, or Y123.4

Just as in Figure 3, Figure 6 reveals that the error is reduced when placing
X2 in the model as a covariate. However, the relationship between X1 and Y is
now adjusted because the shared correlation between X2 and X1 has been removed
(area 4 in Figure 4), which reveals the shared correlation from X1 and X2
(area 4) has been removed from the outcome, denoted as Y123.4. Likewise, the
adjusted model is denoted as Ŷ12.34.

Identical with Equations (10,11,12,16), Equations (27,28,29,33) then become
the basis for calculating the R2 of the adjusted model:

${R}\textsuperscript{2}=\frac{\textup{Total}-SS(E)}{\textup{Total}}=\frac{15884.67-9843.363}{15884.67}=.38$
(27)

or equivalently

${R}\textsuperscript{2}=\frac{SS(X\textsubscript{1}|X\textsubscript{2})+SS(X\textsubscript{2}|X\textsubscript{1})}{SS(X\textsubscript{1}|X\textsubscript{2})+SS(X\textsubscript{2}|X\textsubscript{1})+SS(E)}=\frac{3007.17+3034.14}{3007.17+3034.14+9843.36}=.38$
(28)

This can be confirmed by comparing the variance components of the adjusted
model, ${\sigma}_{\hat{Y}_{12.34}}^{2}$, with the variance components of the
adjusted model ${\sigma}_{\hat{Y}_{12.34}}^{2}$ and error
${\sigma}_{e}\textsuperscript{2}$, or ${\sigma}_{Y_{123.4}}^{2}$, as seen in
Equation (29):

${\textup{R}}\textsuperscript{2}=\frac{{\sigma}_{\hat{Y}_{12.34}}^{2}}{{\sigma}_{Y_{123.4}}^{2}}=\frac{0.60}{1.59}=.38$
(29)

where

${\sigma}_{\hat{Y}_{12.34}}^{2}={b}_{1.2}\textsuperscript{2}{\sigma}_{X1.2}\textsuperscript{2}+{b}_{2.1}\textsuperscript{2}{\sigma}_{X2.1}\textsuperscript{2}=(0.60\cdot
0.50)+(0.61\cdot 0.50)=0.60$ (30)

is the variance components of the adjusted model (areas 1 and 2 in Figure 6)
and,

${\sigma}_{Y_{123.4}}^{2}={b}_{1.2}\textsuperscript{2}{\sigma}_{X1.2}\textsuperscript{2}+{b}_{2.1}\textsuperscript{2}{\sigma}_{X2.1}\textsuperscript{2}+{\sigma}_{e}\textsuperscript{2}=(0.60\cdot
0.50)+(0.61\cdot 0.50)+0.98=1.59$ (31)

is the total variance components of the adjusted model and error (areas 1, 2,
and 3 in Figure 6) which is no longer the same value as the variance of Y:

${\sigma}_{Y}\textsuperscript{2}=2.02\neq{\sigma}_{Y_{123.4}}^{2}=1.59$ (32)

.

As before, the variance accounted for by the model can also be confirmed by
summing the squared adjusted standardized coefficients, as seen in Equation
(33):

${R}\textsuperscript{2}={\beta}_{1.2}\textsuperscript{2}+{\beta}_{2.1}\textsuperscript{2}=0.19+0.19=0.38$
(33)

where

${\beta}_{1.2}=\frac{{b}_{1.2}{\sigma}_{X1.2}}{{\sqrt{{\sigma}_{Y_{123.4}}^{2}}}}=\frac{0.78\cdot
0.71}{\sqrt{{1.26}}}=0.44$ (34)

and

${\beta}_{2.1}=\frac{{b}_{2.1}{\sigma}_{X2.1}}{{\sqrt{{\sigma}_{Y_{123.4}}^{2}}}}=\frac{0.78\cdot
0.71}{\sqrt{{1.26}}}=0.44$ (35)

.

As illustrated in Figure 6 (area 2) and made obvious in Equations 29-31, the
inclusion of the covariate reduced the value of the unaccounted-for variance,
thereby increasing the statistical efficiency of the model. However, unlike
the previous example, it is important to note that while the inclusion of the
covariate reduced the value of the error, the sum of the variance components
of the model no longer equals the variance of the outcome, as made evident
with Equation 32 and illustrated comparing Figure 4 with 6.

##  4 Discussion

Although Equations 16-18 and 33-35 are identical, only the former refers to
the model’s accounting of variance for the original outcome, Y, while the
latter refers to the adjusted outcome Y123.4. That is, when there is no
covariate adjustment, the model coefficients, model variance components, and
model sums of squares, along with the corresponding error, together represent
the original population, Y. Conversely, when covariate adjustment takes place,
the “additive” model no longer adds to the original variance of Y; instead,
the model represents a population without the shared correlation, an
“adjusted” population, Y123.4. But what does the discrepancy between the
original population and this adjusted population represent?

Clearly, the adjusted population ipso facto no longer represents the original
population. The reason for the adjustment is simple: when regressors are
correlated with each other and the outcome variable, this shared correlation
is removed entirely, including from the outcome itself. But this reduction in
error affects the interpretation of the model$:$ when adjusting for X2, for
every increase in $\sigma$X1.2, a $\beta$1.2 change in ${\sigma}_{Y_{123.4}}$
occurs, which is clear from the variance components in Equation (31) and
illustrated in Figure 6. Now consider the interpretation when no covariate
adjustment has taken place$:$ for every increase in $\sigma$X1, a $\beta$1
change in $\sigma$Y occurs, which is clear from the variance components in
Equation (14) and illustrated in Figure 3. This distinction in interpretation
was perhaps first made explicit by Bring (1994, p. 211), but the fact that the
model no longer represents the original population is hidden by the common
misinterpretation of the adjusted model$:$ when adjusting for X2, for every
increase in $\sigma$X1, a $\beta$1.2 change in ${\sigma}_{Y}$ occurs, a subtle
but important bait-and-switch, which hides the discrepancy between the
original population and what the adjustment model represents.

As before, the issue is not one of mathematics but instead the
misinterpretation of mathematics. Covariate adjustment, symbolized by the
lacuna (area 4) when comparing Figure 6 with Figure 4, illustrates the
successful reduction of unaccounted-for variance in the model, but it also
illustrates the cost of this reduction: the model is no longer representative
of the original population. Conversely, if a covariate is included in the
model but no adjustment takes place, then the model remains representative of
the original population, even though the covariate reduced the unaccounted-for
variance, symbolized by comparing Figures 1 and 3. Therefore, the cost of
increased statistical efficiency using a covariate is an increase in bias
(removal of area 4) but only when adjustment results from the inclusion of the
covariate. This is likely why, over 70 years ago, when Woolf first discovered
the effects of adjustment on the variance components, he concluded, “there
seems to be an enormous deficit in the balance sheet. The paradox, of course,
is easily resolved. It is essential for the validity of an analysis of
variance that the various components shall be uncorrelated or independent”
(1951, p.113).

At this point, the question is clear: why use covariate adjustment? When
control of confounds or nuisance variables is not possible by design, it could
be argued that covariate adjustment must then be used. This decision is
predicated on faith—faith that adjustment reduces the intended confound
without simultaneously introducing more bias or faith that although adjustment
may lead to increased statistical efficiency, this efficiency is not also
creating a discrepancy with which the model no longer reflects the population
it is supposed to represent—again bias. Another option is to use the
unadjusted model with replication. This decision is predicated on parsimony,
where there is no threat of introducing more bias than what already exists and
with the knowledge that the inference and estimation of the model reflect the
same population that was originally observed and can be directly defined by
the design.

Faith will likely prevail because the incentives are aligned, a possible
result of Goodhart’s Law (Rodamar, 2018). With the inherent pressures to
achieve statistical significance with as little data and replication as
possible, the promise of the former approach—control of confounds or reduction
of error—is perceived to outweigh the likely cost—the introduction of
bias—because the consequences of bias cannot be quantified. The impulse to use
modeling to achieve what can only be achieved by design is hardly a new
phenomenon. Now, over 90 years ago, Nikola Tesla observed: “Today’s scientists
have substituted mathematics for experiments, and they wander off through
equation after equation, and eventually build a structure which has no
relation to reality” (1934, p. 117-118). Only four short years later, in his
“The Misuse of Statistics,” Cohen (1938) cautioned, “…unjustifiable
conclusions may be drawn, and with instances where incorrect inferences are
drawn from valid data. The trained statistician absorbed in the improvement of
technical procedure grows careless in interpretation…” (p. 660). Likely, these
traditions will continue.

##  5 Appendix A: Simulation Study, R Code

    #####R Code

    #### Covariance Matrix (COV.1), Figure 2, Uncorrelated by design
    nobs = 10000
    set.seed(2001)
    M = matrix(c(2.00, 0.65, 0.65,
                 0.65, 0.60, 0.00,
                 0.65, 0.00, 0.60), nrow=3, ncol=3)

    #### Covariance Matrix (COV.2), Figure 5, Shared Correlation by design
    nobs = 10000
    set.seed(2001)
    M = matrix(c(2.00, 0.65, 0.65,
                 0.65, 0.60, 0.25,
                 0.65, 0.25, 0.60), nrow=3, ncol=3)

    ### Cholesky decomposition
    L = chol(M)
    nvars = dim(L)[1]
    t(L)
    t(L) %*% L
    r = t(L) %*% matrix(rnorm(nvars*nobs), nrow=nvars, ncol=nobs)
    r = t(r)
    SimM = as.data.frame(r)
    names(SimM) = c("Y", "X1", "X2")
    Y=SimM$Y
    X1=SimM$X1
    X2=SimM$X2

    ##Model fit
    MLR = lm(Y~ X1 + X2, SimM)
    resid_Y=resid(MLR)

    #Equation 1/19, Residualized Predictor
    residX1 = lm(X1~ X2, SimM)
    X1.2=resid(residX1)

    #Equation 2/20, Residualized Predictor
    residX2 = lm(X2~ X1, SimM)
    X2.1=resid(residX2)

    #Equation 3/21, Unstandardized Coefficient
    b1.2=sum((X1.2*Y))/sum(X1.2^2)
    b1.2

    #Equation 4/22, Unstandardized Coefficient
    b2.1=sum((X2.1*Y))/sum(X2.1^2)
    b2.1

    #Equation 5/23, Type III Sums of Squares
    SSb1.2=b1.2*sum(X1.2*Y)
    SSb1.2

    #Equation 6/24, Type III Sums of Squares
    SSb2.1=b2.1*sum(X2.1*Y)
    SSb2.1

    #Equation 7, Error Sums of Squares
    SSE = sum(resid(MLR)^2)
    SSE

    #Equation 8/25, Total Sums of Squares by parts
    SSTotal.12=SSb1.2+SSb2.1+SSE
    SSTotal.12

    #Equation 9/26, Sums of Squares Y
    SSTotal= sum(Y^2) - ((sum(Y)^(2))/10000)
    SSTotal

    #Equation 10/27 , Coefficient of determination
    R2=(SSTotal.12-SSE)/SSTotal.12
    R2

    #Equation 11/28 , Coefficient of determination
    R2=(SSb1.2+SSb2.1)/(SSb1.2+SSb2.1+SSE)
    R2

    #Equation 13/30 Variance components of model
    Sig_Yp=(((b1.2)^2)*var(X1.2)) + (((b2.1)^2)*var(X2.1))
    Sig_Yp

    #Equation 14/31 Variance components of model and error
    Sig_Y=(((b1.2)^2)*var(X1.2)) + (((b2.1)^2)*var(X2.1))+var(resid_Y)
    Sig_Y

    #Equation 12/29 , Coefficient of determination
    R2=Sig_Yp/Sig_Y
    R2

    #Equation 15/32, Variance of Y
    Var_Y=var(Y)
    Var_Y

    #Equation 17/34  Standardized Coefficient
    B1.2= (b1.2*(sd(X1.2))/sqrt(Sig_Y))
    B1.2

    #Equation 18/35 Standardized Coefficient
    B2.1= (b2.1*(sd(X2.1))/sqrt(Sig_Y))
    B2.1

    #Equation 16/33, Coefficient of determination
    R2=(B1.2^2)+(B2.1^2)
    R2

    ###############################
    #Type III Sums of Squares Check
    library("car")
    Anova(MLR, type="III")

    ##Reference to shared correlation that was removed removed
    Area4=var(Y)-Sig_Y
    Area4

##  6 References

  1. 1.

Baird, G. L., and Bieber, S. L. (2016). The Goldilocks dilemma: Impacts of
multicollinearity-a comparison of simple linear regression, multiple
regression, and ordered variable regression models. Journal of Modern Applied
Statistical Methods, 15(1), 18.

  2. 2.

Baird, G. L., and Bieber, S. L. (2020). Sampling the porridge: A comparison of
ordered variable regression with F and R2 and multiple linear regression with
corrected F and R2 in the presence of multicollinearity. Journal of Modern
Applied Statistical Methods, 18(1), 11.

  3. 3.

Baird, G. L., and Bieber, S. L. (2023). Revisiting the conceptualization of
multiple linear regression. arXiv preprint arXiv:2302.06464.

  4. 4.

Begg, C. B. (1990). Significance tests of covariate imbalance in clinical
trials. Controlled Clinical Trials, 11(4), 223-225.

  5. 5.

Bring, J. (1994). How to standardize regression coefficients, The American
Statistician, 48(3), 209-213.

  6. 6.

Boardman, T. J. (1994). The statistician who changed the world: W. Edwards
Deming, 1900–1993. The American Statistician, 48(3), 179-187.

  7. 7.

Cohen, J. and P. Cohen. Applied multiple regression/correlation analysis for
the behavioral sciences. Hillside. N.J.: Lawrence Erlbaum Associates. 1975.

  8. 8.

Cohen, J. B. (1938). The misuse of statistics. Journal of the American
Statistical Association, 33(204), 657-674.

  9. 9.

Darner, T. E. (1987). Attacking faulty reasoning. Belmonth, CA: Wadsworth.

  10. 10.

De Boer, M. R., Waterlander, W. E., Kuijper, L. D., Steenhuis, I. H., and
Twisk, J. W. (2015). Testing for baseline differences in randomized controlled
trials: An unhealthy research behavior that is hard to eradicate.
International Journal of Behavioral Nutrition and Physical Activity, 12, 1-8.

  11. 11.

Egbewale, B. E., Lewis, M., and Sim, J. (2014). Bias, precision and
statistical power of analysis of covariance in the analysis of randomized
trials with baseline imbalance: A simulation study. BMC Medical Research
Methodology, 14, 1-12.

  12. 12.

Fischer, D. H. (1970). Historians’ fallacies: Toward a logic of historical
thought. Harper and Row, Publishers.

  13. 13.

Fischhoff, B. (1975). Hindsight is not equal to foresight: The effect of
outcome knowledge on judgment under uncertainty. Journal of Experimental
Psychology: Human perception and performance, 1(3), 288.

  14. 14.

Frisch, R., and Waugh, F. V. (1933). Partial time regressions as compared with
individual trends. Econometrica: Journal of the Econometric Society, 387-401.

  15. 15.

Fox, J., Weisberg, S., Adler, D., Bates, D., Baud-Bovy, G., Ellison, S., … and
Heiberger, R. (2012). Package ‘car’. Vienna: R Foundation for Statistical
Computing, 16(332), 333.

  16. 16.

Imai, M., Murai, C., Miyazaki, M., Okada, H., and Tomonaga, M. (2021). The
contingency symmetry bias (affirming the consequent fallacy) as a prerequisite
for word learning: A comparative study of pre-linguistic human infants and
chimpanzees. Cognition, 214, 104755.

  17. 17.

Kahan, B. C., Jairath, V., Doré, C. J., and Morris, T. P. (2014). The risks
and rewards of covariate adjustment in randomized trials: an assessment of 12
outcomes from 8 studies. Trials, 15, 1-7.

  18. 18.

Kahneman, D. (1965). Control of spurious association and the reliability of
the controlled variable. Psychological Bulletin, 64, 326-‐329.

  19. 19.

Kempthorne, O. (1957). An introduction to genetic statistics. Wiley.

  20. 20.

Kennedy, P. E. (1982). Eliminating problems caused by multicollinearity: A
warning. Journal of Economic Education, 62-64.

  21. 21.

Kerlinger, F. N., and Pedhazur, E. J. (1973). Multiple regression in
behavioral research. New York: Hold, Rinehart and Winston.

  22. 22.

Kirk, R. E. (2013). Experimental design: Procedures for the behavioral
sciences (4th). Thousand Oaks, CA: Sage.

  23. 23.

Lovell, M. C. (1963). Seasonal adjustment of economic time series and multiple
regression analysis. Journal of the American Statistical Association, 58(304),
993-1010.

  24. 24.

Meehl, P. E. (1970). Nuisance variables and the ex post facto design. In M.
Radner and S. Winokur (Eds.), Minnesota Studies in the philosophy of
science$:$ Vol. IV. Analyses of theories and methods of physics and psychology
(p. 373-402). Minneapolis: University of Minnesota Press.

  25. 25.

Newton, R. G., and Spurrell, D. J. (1967). A development of multiple
regression for the analysis of routine data. Journal of the Royal Statistical
Society Series C: Applied Statistics, 16(1), 51-64.

  26. 26.

Pedhazur, E. J., and Kerlinger, F. N. (1982). Multiple regression in
behavioral research. Holt, Rinehart, and Winston.

  27. 27.

Pocock, S. J., Assmann, S. E., Enos, L. E., and Kasten, L. E. (2002). Subgroup
analysis, covariate adjustment and baseline comparisons in clinical trial
reporting: current practiceand problems. Statistics in Medicine, 21(19),
2917-2930.

  28. 28.

Rodamar, J. (2018). There ought to be a law! Campbell versus Goodhart,
Significance, p. 15 (6).

  29. 29.

Sherry, A. D., Msaouel, P., McCaw, Z. R., Abi Jaoude, J., Hsu, E. J., Kouzy,
R., … and Ludmir, E. B. (2023). Prevalence and implications of significance
testing for baseline covariate imbalance in randomised cancer clinical trials:
The Table 1 Fallacy. European Journal of Cancer, 194, 113357.

  30. 30.

Tesla, N. (1934). Radio power will revolutionize the world. Modern Mechanix
and Inventions, 2.

  31. 31.

Tversky, A., and Kahneman, D. (1974). Judgment under uncertainty: Heuristics
and biases: Biases in judgments reveal some heuristics of thinking under
uncertainty. Science, 185(4157), 1124-1131.

  32. 32.

Von Elm, E., Altman, D. G., Egger, M., Pocock, S. J., Gøtzsche, P. C.,
Vandenbroucke, J. P., and Strobe Initiative. (2007). The Strengthening the
Reporting of Observational Studies in Epidemiology (STROBE) statement:
Guidelines for reporting observational studies. Annals of Internal Medicine,
147(8), 573-577.

  33. 33.

Woolf, B. (1951). Computation and interpretation of multiple regressions.
Journal of the Royal Statistical Society: Series B (Methodological), 13(1),
100-119.

  34. 34.

Wysocki, A. C., Lawson, K. M., and Rhemtulla, M. (2022). Statistical control
requires causal justification. Advances in Methods and Practices in
Psychological Science, 5(2), 25152459221095823.

  35. 35.

Yule, G. U. (1907). On the theory of correlation for any number of variables,
treated by a new system of notation. Proceedings of the Royal Society of
London. Series A, Containing Papers of a Mathematical and Physical Character,
79(529), 182-193.


# Assessing Disease Exposure Risk with Location Data: A Proposal for
Cryptographic Preservation of Privacy

Alex Berke  MIT Media Lab, Cambridge, MA, USA  Michiel Bakker  MIT Media Lab,
Cambridge, MA, USA  MIT Connection Science, Cambridge, MA, USA  Praneeth
Vepakomma  MIT Media Lab, Cambridge, MA, USA  Kent Larson  MIT Media Lab,
Cambridge, MA, USA  Alex ‘Sandy’ Pentland  MIT Media Lab, Cambridge, MA, USA
MIT Connection Science, Cambridge, MA, USA

(March 2020)

###### Abstract

Governments and researchers around the world are implementing digital contact
tracing solutions to stem the spread of infectious disease, namely COVID-19.
Many of these solutions threaten individual rights and privacy. Our goal is to
break past the false dichotomy of effective versus privacy-preserving contact
tracing. We offer an alternative approach to assess and communicate users’
risk of exposure to an infectious disease while preserving individual privacy.
Our proposal uses recent GPS location histories, which are transformed and
encrypted, and a private set intersection protocol to interface with a semi-
trusted authority.

There have been other recent proposals for privacy-preserving contact tracing,
based on Bluetooth and decentralization, that could further eliminate the need
for trust in authority. However, solutions with Bluetooth are currently
limited to certain devices and contexts while decentralization adds
complexity. The goal of this work is two-fold: we aim to propose a location-
based system that is more privacy-preserving than what is currently being
adopted by governments around the world, and that is also practical to
implement with the immediacy needed to stem a viral outbreak.

##  1 Introduction

This is a proposed design for how a system can identify and notify users who
may have come in contact with diagnosed disease carriers about their risk
while respecting individual’ privacy. It is common practice for healthcare
workers to interview individuals diagnosed with a communicable disease about
their recent movements in order to identify and alert others who they may have
come in contact with. This process is referred to as contact tracing and is
crucial as health entities, communities and governments attempt to contain
viral outbreaks. Manually performing contact tracing is highly resource-
intensive, intrusive and time-consuming. Yet the ubiquitous use of personal
digital devices provides access to detailed location histories that are
collected automatically, enabling a system that could conduct this process at
scale. The objective of this paper is to describe such a system in the face of
the COVID-19 pandemic that better preserves the privacy of its users than the
systems we see governments adopting.

###  1.1 Contact tracing & privacy

There currently are digital approaches to contact tracing that use location
histories111There are also digital contact tracings solutions that use
Bluetooth technology to detect points of contact between individuals without
using location histories directly [1, 2, 3]. We will discuss these in Section
2. but many operate on a skewed trade-off between privacy and effectiveness
[4]. Some rely on general public broadcasting of information that introduces
uncertainty in the information disseminated.222Information about where
diagnosed COVID-19 carriers have visited has been publicly broadcasted in
different ways. Singapore updates a map and lists details about the identities
about each COVID-19 case [5]. South Korea sends text messages to citizens
containing personal information about diagnosed carriers [6]. In the US,
location information about diagnosed patients has been published through media
outlets and university and government websites [7, 8, 9]. Other alternatives
resort to the usage of technologies that risk violating individual rights
against stigmatization and surveillance333Israel employs cellphone tracking
for coronavirus patients [10]. China requires use of an COVID-19 mobile
application to effectively surveil citizens and dictate quarantines [11]. (see
[4] for a discussion).

Even when systems do attempt to use location data while respecting individual
privacy, their methods are often insufficient: simply anonymizing user
location histories by replacing users’ identifiers with random new ones fails
to achieve privacy in a meaningful way. Secondary data that is not anonymized
can be used to re-identify users by matching data points across the datasets.
For example, a study using credit cards records has shown that only four data
points from a user’s location history are enough to uniquely re-identify 90%
of individuals [12].

This work breaks past the dichotomy of privacy versus effectiveness
established by previous digital contact tracing approaches. We propose a
technology-based solution for contact tracing and disseminating information on
the state of infections while protecting the privacy rights of both diagnosed
infected carriers and other citizens.

###  1.2 Trust & privacy principles

The privacy and trust principles central to the design of this work are
summarized below:

  * •

Keep location data private. Locations visited are kept private for all users
including those who are diagnosed disease carriers.

  * •

Avoid surveillance. The system can detect points of contact between users
without precise location histories being exposed.

  * •

Only allow one-way private data publication. Only diagnosed carriers ever
publish data, but this data remains encrypted and private, and their
identities remain protected. Other users can check if they came in contact
with carriers without sharing their location histories.

Any privacy-preserving contact tracing framework should be considered a “best
effort” and avoid promising to be perfectly private. Our primary contribution
to the space of existing frameworks and digital tools is the degree to which
our cryptographic approach can preserve user privacy while providing highly
useful and accurate information through individuals GPS location histories.

We present our proposal in response to current events where we see an increase
in surveillance and a forfeit of privacy due to contact tracing efforts
designed to contain the spread of COVID-19. We intend to show that effective
contact tracing is possible without further forfeiting privacy.

###  1.3 A useful first step

A simple first version of a system that provides exposure risk information is
one that collects, anonymizes, and aggregates the recent GPS location
histories of diagnosed carriers. This information allows the creation of a
spatiotemporal _heatmap_ representing large geographic regions where diagnosed
carriers spent time and when.

Individuals’ data and areas visited must be aggregated and obfuscated in a way
that minimizes what can be learned about individual people or places visited
in the dataset. This is done in order to protect people and businesses from
potential stigmatization or any other threat. This aggregated view can provide
helpful information about infection risk across different areas, types of
places, and time periods for both health authorities and the general public.
This aggregated data can be further analyzed to better understand the flow and
trends of disease transmission.

###  1.4 Contributions

In the current paper we build upon this first step and discuss the potential
use of a private set intersection protocol to provide more precise risk
assessments to individual users based on points of contact with individuals
who were later diagnosed as disease carriers. Our approach partitions the
space of fine-grained GPS location and time data into discrete spatiotemporal
points that represent location histories. This combination of a partition
scheme and private set intersection protocol allows the system to detect when
a user came in contact (e.g. was in close proximity) with diagnosed carriers
to assess and inform them of their risk, while preserving the privacy of
individuals.

##  2 A Short Survey of Alternative Solutions

Clever approaches to privacy-preserving systems for contact tracing that rely
on Bluetooth rather than GPS have been proposed and implemented as smartphone
applications, such as TraceTogether [2], which was created by the government
of Singapore, and the open source projects COVID Watch [3] and CoEpi [1].
Instead of recording user location histories, these systems record when users
come in proximity of one another. A user’s smartphone application generates,
and periodically updates, a random identifier called a “contact event number”
(CEN). The user’s device broadcasts this CEN using Bluetooth Low Energy and
receives and locally records CENs broadcast by other users’ devices. Users who
later fall ill then share their CENs, which can be matched against the CENs
recorded locally by other users to identify points of contact between
diagnosed users and the other users. The different implementations vary in the
privacy and security they provide their users. For example, the Singapore
government requires users of its TraceTogether app to share their phone
numbers and identities with a central authority that maintains a database of
recorded CENs. This authority contacts users whose recorded CENs match against
diagnosed users’ CENs to alert them of their exposure. This system provides
users with no privacy from the central authority but does protect users from
having their identities exposed to other users. In contrast, the COVID-Watch
and CoEpi projects place more trust in users rather than in a central
authority.444The CoEpi project allows users to self-diagnose and share their
CENs without a health official verifying their diagnosis and data. This can
result in false reporting and invites spam attacks from malicious users, which
can result in other users seeing false positives which, in turn, could cause
panic or simply distrust of the system. This issue has been acknowledged by
CoEpi’s technical leadership and they have invited solutions from researchers
[13]. With their designs, diagnosed users’ CENs are stored in a database that
is either made public for other users’ apps to download or made available for
them to poll [13, 14]. These models are not perfectly privacy-preserving
either, as they are susceptible to privacy attacks from other users, as
described by Cho et al. [15].

These systems use Bluetooth to directly detect whether users come in proximity
of one another, which GPS cannot provide. With Bluetooth, proximity can be
approximated by signal strength that is reduced by obstructions like walls;
therefore, it more accurately reflects functional proximity in high-risk
environments for close contact, such as within buildings and vehicles, or in
underground transit. These Bluetooth features can benefit our proposed system
as well, as the installation of Bluetooth beacons could mark locations with
higher levels of accuracy than what would otherwise be marked only with GPS
coordinates.

We note that applications that detect users’ exposure risk by relying on users
to come into Bluetooth proximity may not be sufficient, given that in addition
to human-to-human transmission, coronaviruses can transmit through commonly
touched surfaces or environments [16]. In contrast, our proposed system can be
extended to handle this kind of exposure risk by checking adjacent time
periods to accommodate when two users may have occupied the same space one
after another.

Another issue with purely Bluetooth-based systems is that they require people
to use a special application that could suffer from slower or limited
adoption, limiting the ability to capture a large enough base of users before
they are diagnosed, and therefore limiting their potential to be useful. With
GPS based approaches we might leverage the fact that the applications on
users’ phones are already collecting their GPS location histories, and develop
a technology as a plugin to interface with these apps, to more quickly roll
out our system as a life-saving contact tracing technology.

##  3 A GPS-based privacy-preserving scheme

In what follows, we describe what type of information our proposed system
provides before showing a high-level system overview. We then explain the
trust and privacy model it is designed for, and finally provide a more
technical description with details on how the system could be built in
practice.

###  3.1 Probabilistic risk assessment

The proposed system provides a probabilistic measure of disease exposure risk
for a user, based on the time they have spent in spaces shared with users who
were later diagnosed as disease carriers. More time spent in such shared
spaces indicates higher levels of risk, but this risk is also dependent on
where those spaces are.

Any technological system should be wary of claiming to precisely determine
exposure risk, due to the limitations of the technologies used for detection,
and the ambiguity over what types of interactions between people, shared
spaces, or common surfaces, most elevate risk. Our proposed system uses GPS
points collected from users’ devices and can be extended to use Bluetooth to
indicate locations visited as well. It is worth noting that GPS has limited
accuracy, especially in dense urban environments or multi-story buildings. But
even detecting whether a user spent sustained time in a crowd or multi-story
building with a diagnosed carrier may be useful, due to the heightened
likelihood of sharing not only space but surfaces such as door handles or
elevator buttons, which help a virus spread [16]. For this reason, we propose
a probabilistic risk assessment based on the amount of time and number of
places that a user shared with a disease carrier, which we call “points of
contact”.

###  3.2 System overview

Below we provide a high-level overview of our system and walk through an
illustrated example.

Figure 1: High-level schematic showing the major steps in the system’s process
for privacy-preserving contact tracing: (1) data collection, (2) redaction and
transformation of data, (3) secure data exchange, and (4) individualized risk
assessment and notification, as well as the distribution of aggregated data to
create a ‘heatmap’ to inform the public of more general risk. A more detailed
description of the process includes usage of discrete spatiotemporal ‘point
intervals’ and ‘a private set intersection protocol and is described later on
in this paper.

Our proposed system follows four (4) steps, namely (1) data collection, (2)
redaction and transformation of data, (3) secure data exchange, and (4) risk
assessment and notification. We expand upon these steps below (see Figure 1).

Step 1:

Data collection. An application (app), installed on the mobile device of the
user, collects timestamped GPS points throughout the user’s day, every $t$
minutes. The sequence of points represents their location history.

Step 2:

Redaction and transformation of data. All collected location histories are
redacted, transformed, and encrypted before leaving the device, to protect
user privacy. In the case that a user is diagnosed, their points are
transformed and shared with the server in a way that maintains their privacy.
Collected points are deleted from both devices and servers $d$ days after they
were collected, where $d$ is the period of possible disease transmission
informed by medical experts.

Step 3:

Secure data exchange. In this phase, using the agreed secure data exchange
mechanism, the mobile app (acting as the client) establishes a secure channel
with the designated server. Within this secure channel, the mobile application
requests the server for the ‘point interval’ data of known infected carriers
for a chosen duration of time (e.g. the last 2 weeks) for a given region (e.g.
Boston).

The infected carriers’ data in the server’s possession is anonymized and has
already undergone redaction and transformation to remove sensitive information
to limit the risk for re-identification, and contains no personally-
identifying information (PII).

Users’ apps can check whether they came in contact with carrier users, and how
often, while preserving privacy. This is done with a cryptographically secure
“private set intersection” (PSI) protocol to find matches between encrypted
‘point intervals’ for carriers and other users.

Step 4:

Risk assessment and notification. The app assesses risk for its user based on
the points of contact it found via (3) and can notify users of risk. Users
whose apps find them at risk due to contact with carriers can then be
encouraged to get tested or self-quarantine. The app can optionally show the
user where and when the points of contact occurred.

This process is also illustrated above in Figure 1. We expand upon the steps 2
and 3 in the following section.

####  3.2.1 Storing and sharing GPS histories

As GPS points are collected by a user’s device, sensitive areas are removed
through either automatic redaction or manually by the user. Redaction is an
important privacy step, as knowledge about where someone was when, or where
they commonly spend time, such as their home area, can be used to re-identify
pseudo-anonymized users [17, 18].

The system provides two methods of redaction: automatic and manual. Home areas
can be easily inferred by the app based on where users spend time in the
nighttime, and these can be automatically redacted. In addition, the app can
provide the user with an interface to mark additional sensitive areas for
redaction. Any GPS point collected within an area marked for redaction is
deleted and not shared. To further protect the user’s privacy, this redaction
happens on the user’s device and the remaining points are then transformed or
obfuscated before they are stored. Redacting and modifying GPS points on the
device, rather than after points are shared, is an important privacy measure
to prevent users from being coerced into providing information on where they
have been.

If a mobile app user is diagnosed as a carrier (e.g. by professional medical
personnel), the proposed system provides two different ways for that user to
anonymously share their GPS points to provide important information to
healthcare professionals, other system users, and the general public.

The two GPS transformations that support these different use cases are:

  1. (a)

GPS points are replaced by larger geographic areas that contain them to
represent the areas where carriers spent time and when, without representing
precise locations.

  2. (b)

Precise timestamped GPS points are transformed into “point intervals” and
obfuscated using a one-way hash function (e.g. NIST standard SHA256 hash
algorithm).

The first way (a) is used for the aggregated view of data that we previously
described as a motivating first step. The granularity level can be dialed-up
or dialed-down depending on the circumstances. The more fine-grain granularity
means an increase in likelihood that the user can be re-identified.

The second way (b) is used for contact tracing. This use case is where we make
a new contribution with our approach to finding points of contact while
preserving privacy.

The two different use cases that (a) and (b) serve are both central to this
work as they will both be invaluable to containing the spread of infectious
disease such as COVID-19. However the remainder of this document focuses on
(b), as it is our main contribution and requires explanation.

###  3.3 Trust and privacy model

The proposed system is designed around a model that assumes there is a semi-
trusted authority maintaining the server with diagnosed carriers’ redacted
location histories. Such semi-trusted authorities could be local hospitals or
local government agencies chartered and regulated to hold citizen data and
maintain data privacy. We believe that a common goal – one that would make the
proposed system usable while preserving individual privacy – is to minimize
the amount of information from a diagnosed carrier that is exposed to other
users and to the semi-trusted authority.

The proposed system is designed to minimize the amount of diagnosed carriers’
information that is exposed, and to maximize the privacy for all other users
of the system. These other users need not share any of their location data in
order to find points of contact with diagnosed users. However, diagnosed users
do risk forfeiting some privacy when they share their location histories with
the authority managing the server 555Even systems designed to be opt-in on the
part of users sharing data can be abused and made compulsory by authorities
once they are built. In Singapore, people contacted by health authorities are
required by law to assist in the activity mapping of their movements and
interactions [2, 19].. Even though they only share their redacted and
encrypted location data, given enough computational resources and malicious
intent, the managing authority can attempt to circumvent these measures and
reconstruct location history data and re-identify users666The authority
managing the server with redacted and encrypted user data can attempt a grid
search (brute force) attack over all possible encrypted point intervals in
order to find hash collisions and reverse the one-way hash function that
encrypted the point intervals, thereby exposing the underlying data. They can
then attempt to reconstruct location histories based on the spatiotemporal
correlation between data points or re-identify users due to the unique nature
of location histories [12]..

There is a clear need for a governance model regarding this data collection
and use. For example, data should be deleted $d$ days after it was shared,
where $d$ is the number of days the diagnosed user could have transmitted the
virus before sharing their location history. There also needs to be a legal
framework in place to end the practice of collecting data in this way once the
health crisis is under control777We have examples to be wary of regarding
measures taken in times of crisis that extend indefinitely. Israel declared a
state of emergency during its 1948 War of Independence, justifying a range of
“temporary” measures that removed individual freedoms. They won the War of
Independence but never declared their state of emergency over, and many of the
“temporary” measures are ongoing [20]. Israel recently approved cellphone
tracking for its COVID-19 patients [21]. Similarly COVID-19 surveillance
innovations in China are likely to be used by China’s counterterrorism forces
beyond the pandemic to further monitor and regulate the movement of its
people. Consider the Uighur people. The Chinese government has categorized
this ethnic group as terrorists and has subjected many of them to forced labor
[22]..

That said, we must also acknowledge that governments already have access to
the massive amounts of location data that our proposed system would collect.
Location histories are already collected by apps on users’ smartphones, and
the cellular towers they connect to, and through credit card purchases.

##  4 Technical description

Our proposed system broadly involves data collection followed by a method to
deterministically construct hashed spatiotemporal intervals that discrete
points in users’ location histories are mapped to. These intervals are then
used with a private set intersection protocol to inform users when points in
their location histories match the points in the location histories of
diagnosed carriers. We discuss these steps in the following sections.

  1. 1.

Collecting and Representing GPS points

  2. 2.

Detecting Points of Contact Using Private Set Intersection

  3. 3.

Assessing Risk and Notifying Users

###  4.1 Collecting and representing GPS points

Timestamped GPS points are collected within user devices as they move
throughout their day. These points are collected as tuples of latitude,
longitude, and time: (latitude, longitude, time). A user’s app checks for
matches between their collected points and the points shared by users who were
diagnosed as carriers in order to identify points of contact.

####  4.1.1 Partition space and time into intervals

For privacy purposes, GPS points are never directly compared in order to find
these matches. Timestamped GPS points are instead first mapped to a
3-dimensional grid, where two dimensions are for geographic space (latitude
and longitude), and the third dimension is time. We call these 3-dimensional
grid cells ‘point intervals’. The point intervals are then obfuscated with a
deterministic one-way hash function. Identifying points of contact becomes a
matter of matching hashed point intervals. Transforming GPS histories in this
way to map (latitude, longitude, time) points that occur within a continuous
spatiotemporal space into discrete ‘point intervals’ makes comparing
obfuscated GPS histories possible. It also makes sense for our use case of
finding (short) time intervals where users occupied the same spatial
area888Phones collect GPS data with limited accuracy and therefore trying to
match users across spatial areas with radii too small will miss points of
contact..

There are established ways to partition a geographic space, such as with
geohashes999https://en.wikipedia.org/wiki/Geohash for square grid cells or
with the hexagonal global geospatial indexing system of H3
grid101010https://h3geo.org/.

Figure 2: A geographic area partitioned by a hexagonal H3 grid. Points are
mapped to an index corresponding to their containing grid cell.

Similarly, time can be partitioned into intervals. For example, if an interval
size is 2 minutes, then an interval boundary can always fall on the hour, and
on the 2nd minute of the hour, and so on. The 3-dimensional grid of point
intervals is an underlying system parameter (or logical “map”) that is agreed-
upon and shared across all user devices in the system. The specific partition
scheme and interval sizes used are implementation details. What matters more
is that the chosen partition scheme and the geographic and temporal resolution
used are consistent across devices.

We note that when collecting GPS points there is a trade-off between accuracy
in detecting points of contact and the amount of data that must be then stored
and processed. For example, if data is collected more frequently, the system
is more likely to detect when users spend little time near each other, such as
sharing a bus ride. However, this requires collecting and storing more data,
and hence more compute resources. We also note that the geographic partition
of space can be expanded to include specific locations. For example, a bus
line might install Bluetooth beacons on its buses with unique identifiers to
serve as the geographic portion of point intervals, allowing users with an app
that supports this functionality to later detect if they shared a bus ride
with a diagnosed carrier.

####  4.1.2 Checking for matches across obfuscated GPS histories

Since the point intervals are transformed with a one-way hash function, they
cannot be easily reversed to expose underlying location histories of users.

Yet, since this transformation is deterministic, users’ apps can still check
for points of contact with diagnosed users by checking for matches between
their transformed point intervals and those returned by a server. Verifying
whether two individuals came into contact becomes a matter of comparing
whether the transformed point intervals that were constructed from timestamped
GPS points (latitude, longitude, time) collected by their devices coincide
with any of the transformed point intervals provided by the server (as well as
adjacent point intervals).111111Technical note about matching against adjacent
intervals: Since the partition of geographic space into intervals was
predetermined, two points may be close together in space but fall into
different intervals. For this reason a user’s app checks each of their
collected point intervals, as well as the spatially adjacent intervals against
the diagnosed carriers’ shared point intervals. That is, if we use a spatial
grid of hexagons (like H3), a user’s collected point falls within a grid cell
and that grid cell is used as an interval. We must check that interval as well
as the surrounding 6 hexagons in the grid against each data point shared by
diagnosed carriers. This adds some complexity in terms of processing power to
make the comparisons $7N_{u}\times N_{I}$ rather than just $N_{u}\times
N_{I}$.

###  4.2 Detecting points of contact using private set intersection

We now describe the protocol that facilitates the private detection of matches
across users’ GPS histories. We assume that there is a semi-trusted authority
(e.g. a local health agency) operating a server. When a patient is diagnosed
as a disease carrier, they share their redacted, anonymized, hashed point
intervals to the central server. Other users’ apps periodically exchange
information about their own hashed point intervals with the server to detect
if their hashed point intervals match against those shared by diagnosed
carriers. They do so with a private set intersection protocol.

Private set intersection (PSI) enables two parties to compute the intersection
of their data in a privacy-preserving way, such that only the common data
values are revealed. It has applications in a variety of privacy sensitive
settings, from measuring conversion rates for online advertising [23] to
securely testing sequenced human genomes [24].

In our case, the two parties involved are the server storing the hashed point
intervals shared by diagnosed carriers, and another users’ device - the
client. Their data are their respective hashed point intervals. We can
leverage PSI in a way so that only the user learns about the intersection of
their data - the server does not learn whether it shares any point intervals
in common with the user, while the users’ app does learn this. Therefore, our
use of PSI is designed to maximize the privacy for users who may be wary of
surveillance or who do not fully trust the entities that maintain the server.

There are many PSI schemes that would fit our needs. These different schemes
vary in their computational complexity, speed, and accuracy. Researchers have
developed fast PSI protocols optimized for a client-server model, including
those where the client is a smartphone app [25] and where the server’s dataset
is significantly larger than the client’s [26], which is the case for our
system121212 However many of these PSI protocols achieve their improved
efficiency at the cost of accuracy, allowing a small number of false
positives, such as by employing bloom filters. This may not be an acceptable
trade-off for a disease contact tracing system where false positives can lead
to panic or the wrong people seeking scarce medical resources.. A good
overview and comparison of PSI protocols can be found in [23].

To aid the reader in understanding how PSI supports our privacy goals, we
provide a simple scheme using the Diffie-Hellman protocol [27, 28] in Appendix
A.

####  4.2.1 PSI benefits and implementation notes

The use of a PSI protocol adds an extra layer of privacy protection for both
the diagnosed carriers and the other users, beyond just the redaction and
obfuscation of data131313When other users send their point intervals to the
server, their point intervals are effectively encrypted twice. First with the
deterministic hash function ($H$) that encrypts all point intervals in the
same way. Second by the PSI protocol..

Other users only ever learn points shared by diagnosed carriers that their own
points matched with (the intersection $P_{I}\cap P_{U}$). This further
protects the privacy of diagnosed carriers. Moreover, the server need not
learn whether any points match; only the other user learns the intersection of
$P_{I}$ and $P_{U}$. This further protects the privacy of undiagnosed users
who may be wary of their location histories leaving their device, or being
shared with an authority.

There are implementation details that further enhance privacy and efficiency.
For example, servers can hold data for their local geographic regions, so that
users with location histories specific to an area (e.g. the Boston area) need
not interact with servers holding data specific to a far away region (e.g. the
Bay Area in California). This helps subset the data so as to run PSI on a much
smaller dataset, thereby helping computational efficiency. In addition, data
shared by diagnosed carriers to servers should be deleted after $d$ days, as
both a privacy and efficiency measure.

The server should also limit the amount of data that a user’s client device
can exchange with it. It is only relevant to compare recent location histories
(i.e. from the past $d$ days). Since points are partitioned into consistent
time intervals, there is therefore an upper bound on the number of points, N,
that any app needs to check against the server’s set of points, $P_{I}$. The
server can limit the exchanges with any client to N points per exchange, and
limit the number of queries per day. This limitation is important for
preventing privacy attacks where an adversary might attempt querying over the
entire spatiotemporal grid to reconstruct the location histories of diagnosed
carriers. It also reduces the computational burden for servers.

###  4.3 Assessing risk and notifying users

A user’s app can assess their risk of infection based on the comparison
(performed on the user’s device) between the point intervals on the user’s
device with those received from the server. Users whose apps find them at
reasonable risk can then be encouraged to get tested or self quarantine.

The implementation of our system can differ to either allow the app to learn
just the number of points of contact that occured, or where and when points of
contact occurred. These different implementations have different implications
for the privacy and utility that our system can offer to its users.

The number of detected points of contact is related to how likely a user was
to have spent sustained time in spaces shared with diagnosed users, so the
number of detected points of contact is commensurate with risk and can be used
to provide a risk assessment. When the locations of points of contact are
known, the risk assessment can leverage context about these locations, such as
whether they are confined spaces with few people versus multi-story office
buildings versus outdoor parks. Future work can further incorporate
intelligence into the risk assessment.

##  5 Intermediary implementation

Given the urgency of the COVID-19 pandemic, we note that intermediary steps
can be taken to implement the system we describe. Even before a secure server
is set up to perform the private set intersection (PSI) protocol, hashed point
intervals for diagnosed carriers can be published to a flat data file for
other users to download. While this would speed up implementation, privacy
guarantees would be diminished in this case, as attackers can attempt to
create points representing every potential point interval to check for
matches. Attackers could then attempt to reconstruct location histories of
users diagnosed as carriers and possibly re-identify them from their shared
anonymized data. While the redaction step would decrease the likelihood of an
attacker’s success, some privacy risk remains. Finally, this intermediary
implementation with a flat data file can then be subsequently transitioned to
the more secure implementation using a PSI protocol.

##  6 Discussion

We proposed a technical design to address the problem of assessing users’ risk
of disease exposure with location histories. Our proposal is in response to
existing digital contact tracing technologies, with an approach that better
preserves the privacy of individuals.

We are encouraged by other recent privacy-sensitive proposals for contact
tracing [29, 15, 1, 3]. Some of these even extend our notions of privacy by
removing the need for trust in authorities who might abuse their access to
diagnosed patients’ encrypted data and violate their privacy. However, these
systems are more complex and require more infrastructure and coordination,
making them more difficult to implement. Our goal is to propose a system that
is more privacy-preserving than the contact tracing technologies that we see
governments around the world adopting, but that can also be practically
implemented with the immediacy needed to both stem the spread of disease and
stem the adoption of privacy-violating technologies.

Importantly, any implemented system, based on Bluetooth or GPS, should be opt-
in, and clearly communicate to users how it collects, retains, and uses data,
to provide users the opportunity to weigh the trade-off between their
individual privacy risk posed by sharing information with the system and the
ongoing risk the pandemic poses.

In addition to the trade-offs between privacy, effectiveness, and the speed of
implementation for these technologies, we must consider adoption. None of
these systems can have widespread impact without extensive adoption. To expand
system adoption, the proposed app’s technology can be developed as an SDK
(software development kit) and integrated into partnering applications that
already collect user location histories, such as Google Maps. These partner
applications can then ask the user for the extra permissions and consent for
this system’s use case. There are many such applications that already collect
user location histories in the background. They often use this information to
serve the user more relevant advertisements and content. This data is used to
improve the user experience but more often serves private profit. Now, in the
face of the COVID-19 pandemic, is the time for industry and researchers to
come together and for the ubiquitous collection of location data to serve the
public good. At the same time, we must avoid building any new surveillance
systems to serve as short-term emergency measures that can last beyond a time
of crisis.

##  7 Acknowledgements

We thank Thomas Hardjono, Dan Calacci, Ethan Zuckerman, and Robert Obryk for
contributing their ideas and critiques, and we thank Connection Science and
Media Lab sponsors for their support.

## References

  * [1] Dana M. Lewis et al.  Coepi: Community epidemiology in action.  https://github.com/Co-Epi, note = Accessed: 2020-03-30, 2020.
  * [2] Government Digital Services and Blue Trace.  Tracetogether.  https://www.tracetogether.gov.sg/, note = Accessed: 2020-03-30, 2020.
  * [3] Rhys Fenwick, Mike Hittle, Mark Ingle, Oliver Nash, Victoria Nguyen, James Petrie, Jeff Schwaber, Zsombor Szabo, Akhil Veeraghanta, Mikhail Voloshin, Sydney Von Arx, and Tina White.  Covid watch.  https://www.covid-watch.org/, note = Accessed: 2020-03-30, 2020\.
  * [4] Ramesh Raskar, Isabel Schunemann, Rachel Barbar, Kristen Vilcans, Jim Gray, Praneeth Vepakomma, Suraj Kapa, Andrea Nuzzo, Rajiv Gupta, Alex Berke, et al.  Apps gone rogue: Maintaining personal privacy in an epidemic.  arXiv preprint arXiv:2003.08567, 2020.
  * [5] Government Digital Services.  Covid-19: Cases in singapore.  https://www.gov.sg/article/covid-19-cases-in-singapore, note = Accessed: 2020-03-30, 2020.
  * [6] M Zastrow.  South korea is reporting intimate details of covid-19 cases: has it helped?  Nature, 2020.
  * [7] The New York Times.  Coronavirus in the u.s.: Latest map and case count.  https://www.nytimes.com/interactive/2020/us/coronavirus-us-cases.html, note = Accessed: 2020-03-30, 2020.
  * [8] John Hopkins University and Medicine.  Coronavirus covid-19 global cases.  https://coronavirus.jhu.edu/map.html, note = Accessed: 2020-03-30, 2020.
  * [9] Nebraska Department of Health and Human Services.  Coronavirus disease 2019 (covid-19).  http://dhhs.ne.gov/Pages/Coronavirus.aspx, note = Accessed: 2020-03-30, 2020.
  * [10] Haaretz.  Israel approves cellphone tracking for coronavirus patients as cases rise to 213.  https://www.haaretz.com/israel-news/.premium-israel-approves-cellphone-tracking-for-coronavirus-patients-as-cases-rise-to-213-1.8678361, note = Accessed: 2020-03-30, 2020.
  * [11] The New York Times.  In coronavirus fight, china gives citizens a color code, with red flags.  https://www.nytimes.com/2020/03/01/business/china-coronavirus-surveillance.html, note = Accessed: 2020-03-30, 2020.
  * [12] Yves-Alexandre De Montjoye, Laura Radaelli, Vivek Kumar Singh, et al.  Unique in the shopping mall: On the reidentifiability of credit card metadata.  Science, 347(6221):536–539, 2015.
  * [13] Sourabh Niyogi, James Petrie, Scott Leibrand, Jack Gallagher, Hamish, Manu Eder, Zsombor Szabo, and George Danezis.  Cen proposals for privacy-preserving distributed contact tracing.  https://docs.google.com/document/d/1f65V3PI214-uYfZLUZtm55kdVwoazIMqGJrxcYNI4eg, note = Accessed: 2020-03-30, 2020.
  * [14] Sourabh Niyogi, Scott Leibrand, and Dana M. Lewis.  Cen proposals for privacy-preserving distributed contact tracing.  https://github.com/Co-Epi/coepi-backend-go, note = Accessed: 2020-03-30, 2020.
  * [15] Hyunghoon Cho, Daphne Ippolito, and Yun William Yu.  Contact tracing mobile apps for covid-19: Privacy considerations and related trade-offs.  arXiv preprint arXiv:2003.11511, 2020.
  * [16] Günter Kampf, Daniel Todt, Stephanie Pfaender, and Eike Steinmann.  Persistence of coronaviruses on inanimate surfaces and its inactivation with biocidal agents.  Journal of Hospital Infection, 2020.
  * [17] Philippe Golle and Kurt Partridge.  On the anonymity of home/work location pairs.  In International Conference on Pervasive Computing, pages 390–397. Springer, 2009.
  * [18] John Krumm.  Inference attacks on location tracks.  In International Conference on Pervasive Computing, pages 127–143. Springer, 2007.
  * [19] Team Trace Together.  Can i say no to uploading my tracetogether data when contacted by the ministry of health?  https://tracetogether.zendesk.com/hc/en-sg/articles/360044860414-Can-I-say-no-to-uploading-my-TraceTogether-data-when-contacted-by-the-Ministry-of-Health-, note = Accessed: 2020-03-30, 2020.
  * [20] Yuval Noah Harari.  The world after coronavirus.  Financial Times, March 2020.
  * [21] Oliver Holmes.  Israel to track mobile phones of suspected coronavirus cases.  The Guardian, March 2020.
  * [22] Shui-yin Sharon Yam.  Coronavirus and surveillance tech: how far will gov’ts go and will they stay when they get there?  Hong Kong Free Press, March 2020.
  * [23] Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner.  Phasing: Private set intersection using permutation-based hashing.  In 24th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 15), pages 515–530, 2015.
  * [24] Pierre Baldi, Roberta Baronio, Emiliano De Cristofaro, Paolo Gasti, and Gene Tsudik.  Countering gattaca: Efficient and secure testing of fully-sequenced human genomes (full version).  arXiv preprint arXiv:1110.2478, 2011.
  * [25] Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, and Christian Weinert.  Mobile private contact discovery at scale.  In 28th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 19), pages 1447–1464, 2019.
  * [26] Ágnes Kiss, Jian Liu, Thomas Schneider, N Asokan, and Benny Pinkas.  Private set intersection for unequal set sizes with mobile applications.  Proceedings on Privacy Enhancing Technologies, 2017(4):177–197, 2017.
  * [27] Whitfield Diffie and Martin Hellman.  New directions in cryptography.  IEEE transactions on Information Theory, 22(6):644–654, 1976.
  * [28] Bernardo A Huberman, Matt Franklin, and Tad Hogg.  Enhancing privacy and trust in electronic communities.  In Proceedings of the 1st ACM conference on Electronic commerce, pages 78–86, 1999.
  * [29] Ran Canetti, Ari Trachtenberg, and Mayank Varia.  Anonymous collocation discovery:taming the coronavirus while preserving privacy, 2020.
  * [30] Hao Chen, Kim Laine, and Peter Rindal.  Fast private set intersection from homomorphic encryption.  In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1243–1255, 2017.

##  Appendix A An example private set intersection protocol using Diffie-
Hellman

Below we outline an example of how our system would work with a simple Diffie-
Hellman PSI protocol. Note that the actual implementation may differ from this
example. Our description assumes familiarity with Diffie-Hellman, modular
arithmetic and concepts from cryptography such as the discrete log problem.
Readers can otherwise skip this section to the PSI protocol summary below.

Before we walk through this PSI protocol, we clarify the problem and notation.

##### Notation and Problem Statement:

We call a point interval $p$, and a collected sequence of point intervals
$P=[p_{1},p_{2},...]$. We call the users’ point intervals that are collected
by their device $P_{U}$. We call the point intervals collected for diagnosed
carriers and later shared with the server $P_{I}$.

As we noted earlier, each point interval is encrypted by a commonly shared
deterministic hash function, which we call $H$. This means that a user’s phone
really stores $H(P_{U})=[H(p_{U1}),H(p_{U1}),...H(p_{Un})]$, and the server
stores
${H(P_{I})=[H(p_{I1}),H(p_{I1}),...H(p_{Im})]}$.

If a user has a point interval matching one shared by a diagnosed carrier,
i.e. $p_{Ui}=p_{Ij}$ for some $p_{Ui}$ in $P_{U}$ collected by the user’s
device, and some $p_{Ij}$ in $P_{I}$ collected by a diagnosed carriers’ device
and later shared to the server, then the encrypted hashes of these point
intervals match as well. $H(p_{Ui})=H(p_{Ij})$.

Consider $H(P_{U})$ as a set which is stored on the user’s device, and
$H(P_{I})$ as a set stored on the server. The problem is then to allow the
user’s app to learn the set intersection of $H(P_{U})$ and $H(P_{I})$.

##### Protocol:

Our described use of Diffie-Hellman is written with the multiplicative group
of integers modulo $p$, where $p$ is prime, and $g$ is a primitive root modulo
$p$.

##### Setup:

The server and the client user’s device have an agreed upon modulus, $p$, and
base of the multiplicative group, $g$. The server and client each generate
secret private keys, $a$ and $b$, respectively.

  1. 1.

The client encrypts the user’s hashed point intervals, $H(P_{U})$, with a and
sends this data to the server.

$Client\rightarrow
Server:H(P_{U})^{a}=[H(p_{U1})^{a},H(p_{U1})^{a},...,H(p_{Un})^{a}]\bmod p$

  2. 2.

The server encrypts its stored hashed point intervals, $H(P_{I})$, with $b$
and sends this data to the client.

$Server\rightarrow
Client:H(P_{I})^{b}=[H(p_{I1})^{b},H(p_{I1})^{b},...H(p_{Im})^{b}]modp$

  3. 3.

Upon receiving the encrypted hashed point intervals sent by the client
$H(P_{U})^{a}$, the server further encrypts this data with its key b and sends
the result back to the client.

$Server\rightarrow
Client:H(P_{U})^{ab}=[H(p_{U1})^{ab},H(p_{U1})^{ab},...,H(p_{Un})^{ab}]\bmod
p$

  4. 4.

The client receives both $H(P_{I})^{b}$ and $H(P_{U})^{ab}$. The client then
further encrypts $H(P_{I})^{b}$ with its key a to create

$H(P_{I})^{ba}=[H(p_{I1})^{ba},H(p_{I1})^{ba},...,H(p_{Im})^{ba}]\bmod p$.

  5. 5.

The client can then compute the set intersection by comparing the elements of
$H(P_{U})^{ab}$ and $H(P_{I})^{ba}$.

Due to the multiplicative properties of the group, any matching $H(p_{U})$ and
$H(_{I})$ values will have matching $H(p_{U})^{ab}$ and $H(p_{I})^{ba}$
values. This means that if the client has any point intervals that match point
intervals shared to the server, $p_{U}=p_{I}$, then
$H(p_{U})^{ab}=H(p_{I})^{ba}$, and these matches will be detected by the
client.

Figure A.1: This figure shows our private set intersection (PSI) protocol
based on Diffie-Hellman key exchange. The intersection is done on encrypted
point intervals corresponding to the client’s and carrier’s location traces.
The encrypted point intervals from diagnosed carriers are stored in a server.
Only the client device learns the intersection of data, where the intersection
is the set of point intervals it has in common with the point intervals on the
server $(P_{U}\cap P_{I})$. Points in $(P_{U}\cap P_{I})$ are represented in
$(H(P_{U})^{ab}\cap H(P_{I})^{ba})$.

This protocol allows for flexibility in terms of whether it allows a client to
learn which of its points have matches versus how many of its points have
matches. At step (3) of the protocol the server further encrypts the data
received from the client, H(PU)a, and returns H(PU)ab. If the server maintains
the order in the sequence of points intervals, then the client can then learn
exactly which hashed point intervals in the sequence it sent to the server,
$H(P_{U})^{a}=[H(p_{U1})^{a},H(p_{U1})^{a},...H(p_{Un})^{a}]$ match against
items in the server’s encrypted data, $H(P_{I})^{ba}$. If the server instead
shuffles the sequence before returning it in step (3), then the client can
learn how many of its point intervals match against the server’s data, but not
which ones do.

We described a simple protocol in order to more easily explain how our system
can operate. Optimizations can be made for efficiency. For example, the server
can reuse its private key, b, and set of encrypted data across multiple
interactions with different clients. It can refresh this key and re-encrypt
its data periodically, or as new data is shared by diagnosed carriers or
deleted as it becomes old. Decreasing how often the server encrypts its data
can increase its efficiency. Faster PSI protocols have been developed,
including those that optimize for the exchange of information between a server
and client, particularly where the server has a much larger set of data than
the client, such as in our use case [30, 26].