lbarman
commented
4 years ago Hi again @adewes. Thanks for the detailed suggestion !
To better understand, let me ask: when Alice feels sick and goes to the hospital, but is diagnosed negative; she still uploads her (seed of) EphIDs with some probability as if she was infected ?
In practice, a balance needs to be found between these two extremes that sufficiently reduces the privacy risk to the individual and at the same time does not reduce the precision of the contact tracing scheme too much.
would you see a sweet spot ?
Don't get me wrong, I like plausible deniability; just trying to see how many false positives this creates :)
FishmanL
adewes
kollokollo
Thinking about the privacy risk to infected people I wondered if it could be reduced further by creating plausible deniability for them via a randomized response technique. This could be done by randomly changing the reporting of a Covid-19 test, so that people which have been tested negative have a small chance of being reported as positive and vice versa. This would obviously increase the error rate but it would make it harder for attackers to learn about the infection status of people that they have re-identified by e.g. observing EphID values and correlating them with other data such as video footage.
The drawback of this method is of course that it's possible persons will be quarantined due to a person that was randomly reported as infected, or that an infected person will be reported as healthy when he/she is infected. How strongly this affects the precision of the system depends on the other errors that are present.
Threat Analysis
Scenario: An adversary obtains
EphIDvalues of an individual as well as further information of that individual, e.g. an image or other personal data that can be used to identify the individual. If the individual now gets marked as infected by the system the adversary will be able to obtain this information with 100 % confidence. Such an attack is easy to perform for any adversary that has access to a suitable BLE device and access to relevant conext information such as video footage, so it has a high likelihood of occurring in practice.Defense Mechanism
To defend against this attack, we use randomization of reported results in order to create plausible deniability. This can e.g. be done by randomly modifying the test results of the subset of individuals that get tested for Covid-19. The randomization uses two Bernoulli-distributed binary variables with probabilities $p_1$ and $p_2$. The After performing a Covid-19 test with result $r$ (either $0$ or $1$), a value $x_1$ is drawn from the first distribution, which will be $x_1=0$ with probability $p_1$ or $x_1=1$ with probability $1-p_1$. If $x_1 = 1$, the system will report the true test result. If not, another value $x_2$ will be drawn from the second distribution, which will be $x_2=0$ with probability $p_2$ or $x_2=1$ with probability $1-p_2$. That value will be reported as the test result instead of the true value.
This procedure creates a differentially private randomization mechanism and can thereby protect the anonymity of every individual whose data is submitted to the system.
Effect on Tracing Accuracy and Privacy
The effect of the randomization on the accuracy of the tracing system depends on the parameter $p_1$. The larger $p_1$, the more random noise will be injected, reducing the precision of the tracing data. The question is, which value of $p_1$ is necessary to create enough plausible deniability for an individual? This depends on the context information that an adversary has access to. If he/she does not have any additional information about the individual, his/her best estimate that the person is infected without having any data from the tracing system is equivalent to the base infection rate of the population. Now, if the adversary observes a positive test result for this individual via the system, he/she can improve this estimate. Without any randomization, the adversary would learn the true value with 100 % accuracy. On the other extreme, if $p_1=1$ (i.e. all values are generated randomly), the adversary would learn nothing about an individual based on the test result. In practice, a balance needs to be found between these two extremes that sufficiently reduces the privacy risk to the individual and at the same time does not reduce the precision of the contact tracing scheme too much. For a given value of $p_1$, the adversary then has to take all possible combinations of ($x_1$, $x_2$ and $r$) into account to update his/her estimate. Likewise, the precision of the differentially private tracing system can be estimated based on the value of $p_1$ and the estimates of other relevant error sources.
As a first naive guess one could choose $p_1=p_2=p_r$, where $p_r$ is the non-randomized empirical frequency of positive test results (i.e. the empirical probability that a Covid-19 test will be positive). Hence, the resulting randomized test results would have the same distribution as the original results and a reported positive test result would have the same likelihood of being produced by the randomization process as by a real positive result. This parameter choice also decreases the confidence in a reported test result by 50 % though. Whether this is problematic depends on the other sources of error that are present in the system. If we choose a smaller value for $p_1$, the confidence of the adversary (and a legitimate user) in his/her estimate of the infection status of the individual will increase. Even a small $p_1$ value might create enough plausible deniability for an individual though.
Effect on Statistical Use of the Data
As the randomization mechanism is known (and does not need to be kept secret), its statistical effect can be corrected for. The randomization introduces additional noise into the system, which reduces the precision of any statistical estimate. With a large enough sample size this effect quickly becomes negligible though.
Let me know what you think! If there's a general interest to explore this approach further I'm happy to work out a detailed optimization scheme for picking the randomization parameters.