Mobile app protocols for privacy-sensitive epidemic contact tracing

As the news about the novel Coronavirus (nCov-19 / SARS-CoV-2) grows, I have been pondering some way to use technology to enable contact tracing to help people determine quickly if they may be at higher risk. I believe it is particularly important to develop approaches that are privacy-sensitive and based on an opt-in approach. Here are two protocols I came up with, which could be potentially implemented as a mobile app. I would love to hear if anyone has feedback on ways to improve these schemes or interest in implementation and trial.

Protocol 1 — encrypted beacons

1. Each user periodically beacons, using Bluetooth, a message consisting of a unique name/ID, a time-stamp, and a random number (salt) that changes over time that is encrypted using a symmetric key. Users do not share this key with others.

2. Others that hear the encrypted message beacon log it locally.

3. Either periodically or in a batch, on an opt-in basis, each user can upload all the encrypted beacon messages they have heard to a common server.

4. If a user i becomes infected, they inform the server (with evidence that they are infected such as a medical report or “infection certificate”), which then proceeds to make all the messages uploaded by this user publicly available (still encrypted).

5. Each other user j can privately check these now publicly available encrypted messages (this could be automated) to see if they can decrypt any of them. If so, they are at risk as they have been near an infected person. They should then proceed to get tested themselves.

Protocol 2 — random beacons

1. Each user beacons a sufficiently large random number ( to minimize the chance of collisions with beacons generated by other users ) and logs this random number locally.
2. Other that hear the beacon log this number locally.
3. Either periodically or in a batch, on an opt-in basis, each user can upload all the random beacon messages they have transmitted to a common server.
4. If a user i becomes infected, they inform the server (with evidence that they are infected, such as a medical report / “infection certificate”), which then proceeds to make all the random numbers uploaded by this user publicly available.
5. Other users periodically check the server and see if any of the numbers they have logged locally match those that were revealed by an infected user; if so they should proceed to get tested.

Illustration of how the Privacy-Sensitive Contact Tracing App would work. Both protocols are illustrated here. In phase A , the first two steps of both protocols, anonymized (encrypted or random) beacons are sent and logged. In phase B, the last three steps of both protocols, an infected patient uploads to a trusted third party server anonymized beacon messages that they received/sent along with a medical certificate; these messages are publicized by the server; and finally other users can check privately if they have been in contact with an infected patient by checking the publicized messages uploaded by infected patients.

While protocol 1 uses symmetric key encryption, protocol 2 requires the secure generation of sufficiently large random numbers. In a way they are duals of each other: protocol 1 nodes upload the messages they have heard, while in protocol 2 nodes upload the messages they have sent. Both protocols provide privacy for users that are not infected as such users never need to reveal their identity or contacts. Both protocols provide users with opt-in measures to get verified and declare if they are infected, while still maintaining some measure of privacy with respect to the general public as they do not need to reveal their true identities or those of their contacts or the locations they have visited to everyone. And both protocols allow users to privately detect if they have had contacts with others that are infected.

The fourth step in both protocols requires a trusted third party that a) operates the “publicizing” server, and b) can verify through a medical certificate of some sort that the user whose uploaded anonymous data is being made public has truly tested positive for being infected. It is important that this party be trusted and perform the verification correctly to minimize false alarms. It may be necessary for this role to be fulfilled by an organization (whether public or private) with relevant experience and reputation.

Both protocols require the ability to beacon information over short range Bluetooth links. Today’s phones, for security, privacy and energy efficiency reasons, generally require applications that do such beaconing to run in the foreground; regrettably, this could make the protocols less effective than they could be. But perhaps mobile device manufacturers could be prevailed upon to provide greater access to such an app in the public interest. Alternatively, at least at relatively more crowded venues such as airports, campuses, shopping areas or public transportation, users can be encouraged to download and turn on these apps.

One caveat I should offer is that these protocols are far from perfect.It cannot be guaranteed that any of the several key steps will happen: download and regular use of the app by citizens, opt-in and uploading of logged data, informing the server with certified proof when found to be infected, or compliance (in terms of getting themselves tested) by those who find out that they have been in contact with someone infected. But it offers honest and concerned citizens a means to improve their understanding of risks. I believe that the adoption hurdles can be potentially overcome with sufficient public messaging and community support in a challenging time such as we are facing.

There is prior academic work on this topic that is worth a close look. In particular, the ENACT approach uses logs of WiFi AP’s detected as the basis of their approach, which is a nice orthogonal alternative to the proposed approach (I could see an app potentially combining both approaches).

Thanks to Gowri Sankar Ramachandran at USC Viterbi CCI for a helpful discussion on this topic and for the pointer to the ENACT work.