ROBERT's desired property is not clearly stated, proposing: "k-anonymity" #52
Comments
|
Hello @superboum. I note that, as you say:
I agree with the way you formulate the problem. Yet I cannot avoid thinking about the limits of manual tracing: an elderly (B) who sees only the person who brings her daily meals (A). Here A will be in 1-exposure-anonymity to B. So what? You ask in particular:
Manual tracing considers that the benefits are superior to the risks, and de-anonymisation will no be considered as a fundamental obstacle. Why should this very particular situation be considered differently when it is an app? Once again we are back to the “honest but curious” assumption. As we already said in #2:
|
|
I propose k-anonymity as it seems to capture the property you want and it could help to leverage on the vast literature on the subject. It captures at the same time a vast majority of attacks and simplify the problem. About "honest but curious"I am speaking about end users here. Does it mean you assume "honest but curious" end users too? If so, why not simply use the API provided by phone manufacturers like Trusty, more generally TPM/TEE/etc. ? But hardware security mechanisms may not be needed at all. Users do not have root access on their phone, so if the collected list is managed by the system and not an app, it is possible to expose an API on the phone that do not expose ephemeral IDs. It seems that its what Apple+Google have chosen to do. source So if you choose a weak attack model, then it seems the problem is already solved. And if you choose a stronger attack model, it seems many things are still blurry. |
|
Hi; I've previously done a lot of work on hash-based k-Anonymous search; I created the k-Anonymous search approach used in Have I Been Pwned, which I later worked with Cornell University to provide formal analysis for the protocols refine into new C3S protocols [ACM]. This work fed into the efforts to create Google Password Checkup by Google and Stanford [Usenix] Before the pandemic, I was doing work on anonymising wireless unique identifiers (for example, in Bluetooth Journey Time Monitoring Systems). This work provides formal analysis and experimental data for applying k-Anonymity to hashes for the purpose of anonymisation. The pre-print of the paper is here (conference accepted): https://arxiv.org/abs/2005.06580 Recently, I've been working on using k-Anonymity to prevent de-anonymisation attacks in existing Contact Tracing protocols. I have formed a hypothesis for using a cross-hashing approach to provide a cryptographic guarantee for the minimum contact time and additionally prevent "Deanonymizing Known Reported Users". This uses a k-Anonymous search approach to reduce the communication overhead and additionally offer additional protection to data leaks from the server (using Private Set Intersection). The hypothesis can be found here alongside discussions of the risk factors - but do note there are no experimental results at this stage and this paper is not peer-reviewed: https://arxiv.org/abs/2005.12884 If anyone has any feedback on this work, please do reach out to me (my email is on the papers). Thanks |
ROBERT's authors refer often (3 times) to @vaudenay's security analysis of DP-3T in their paper. Indeed, they position their paper as an alternative of "decentralized" applications like DP-3T:
Authors precise their thought later:
It seems that the main point they identify is exposure deanonymization.
However, defining exactly what attacks could lead to such deanonymization is not that simple.
It has been lengthily discussed in #46 and it appears that without a proper authentication mechanism, ROBERT is vulnerable to the same attacks than DP-3T. At the same time, it has been proven that such deanonymization attacks can't be conducted at scale on DP-3T. Finally, and following inherent problems of tracking applications, if you met only one person during the last 15 days and receive a notification, you will be able to identify the infected person. Please refer to aboutet's message for the authentication part, veale's message for DP-3T mitigations, and risques-tracage.fr for inherent attacks to tracking apps.
We define authenticated ROBERT as a patched version of ROBERT that is not vulnerable to Sybil attacks
It seems that the only goal of authenticated ROBERT is to, contrary to DP-3T, prevent a notified user to learn who may have infected her considering she met more than one app user in the last 15 days.
It looks like we could rephrase this desired property as "k-exposure-anonymity" (exposure referring to the fact that we were in contact long and close enough to be recorded by the app).
k would be the degree of anonymity that has an infected person A against another user of the app named B.
k will be equal to the number of people that B has seen during the last 15 days.
A has probably met many people during the last 15 days, so we name the people she was exposed to B_i (B_0, B_1, B_2, etc.).
Each B_i app user met a different number of users during these last 15 days.
It will mean that A will have a different anonymity degree against each user B_i.
Anonymity degree between A and B_i is referred to as k_i.
If one user B_j has seen only one app user in the last 15 days, A will be 1-contact-anonymous to B_j - so no anonymity is provided to A against B_j.
Introducing this k-exposure-anonymity logic could help us improve our exchange and evaluation of ROBERT:
To conclude, I think that ROBERT tries to provide a property that I name "k-exposure-anonymity" without explicitly defining and naming it. Authors should clearly state the property they seek and critically evaluate their proposal at the light of it
Note: This post is not about the usefulness of this property or about tradeoff it involves (like requiring authentication and trust in an authority), however an analysis of cost/benefit of introducing such a property would be very interesting
The text was updated successfully, but these errors were encountered: