Epione: Privacy-Preserving Contact Tracing

The global COVID-19 pandemic has left organizations around the world scrambling to find solutions. One of the best tools for containing the spread of infectious diseases such as COVID-19 is contact tracing. Unfortunately, in the rush to contain the disease, fundamental rights such as privacy are often dropped. But what if we could achieve the goals of contact tracing, without giving up privacy?

Epione is a joint project between UC Berkeley, National University of Singapore, and Oasis Labs that aims to produce a framework for truly privacy-preserving contact tracing. In this post we’ll explain what Epione is, how it’s different from other efforts, and our plans for building it. For details or a more technical description of Epione, please see the Epione website.

What is Contact Tracing?

Let’s say Alice is diagnosed with COVID-19. Contact Tracing is the act of identifying every person Alice has come into contact with while she was contagious, and then isolating and testing those people to find out if they have the disease. You repeat the process for every person diagnosed positive.

One of the key steps to contact tracing is identifying contacts. “Contact” generally means being within a certain distance for a certain period of time, such as within 2 m for 10 minutes or more. Full contact tracing requires all 3 steps above: diagnosis, contact identification, isolation and testing.

Obviously, an app on your phone can’t provide a diagnosis, nor isolation and testing. But it can help with contact identification by keeping track of people you’ve been near or places you’ve been.

Contact Tracing Apps and Privacy Concerns

In traditional contact tracing, Alice would have to reveal a lot of very personal information to whoever is doing the tracing: details on every person she’s been in contact with and places she’s been over a period of time that could be up to two weeks. There are obvious privacy concerns there — not just for Alice, but also for anyone Alice has been in contact with.

An app on your phone may help to automate the process, but doesn’t necessarily protect your privacy better than traditional methods. Singapore’s TraceTogether app broke ground by using Bluetooth to find contacts and record them in a way that can’t be observed by third parties. This data is then made available to the Singaporean government if the user is then diagnosed with COVID-19, which can greatly facilitate contact tracing.

Inspired by Singapore’s TraceTogether we just mentioned, a number of other groups have announced their own contact tracing apps, including Apple and Google, and DP3T from EPFL and ETH Zurich among others. In nearly all of these apps, the model is flipped around: instead of a central authority collecting all of the contact information, random “tokens” are passed from phone to phone that can’t be tied to anyone directly. When Alice is diagnosed with the disease, the app on her phone gathers up all of the tokens that she has sent over the last two weeks and uploads it to a central server. Other users can then get the list of all tokens from people that have been diagnosed with the disease, and see if they’ve received any of them. If so, they get an alert on their phone.

While this is a lot better for user privacy than the central model, there are still privacy concerns with these designs:

1. In some cases, it’s possible to use the list of tokens from the “positive” list to retroactively track people’s movements. For example, there’s an app that can be used with Bluetooth beacons to figure out movements of people diagnosed positive in the Apple-Google system.
2. In all cases, it’s possible for someone to keep track of when and where they received which tokens, and use that to identify who has been diagnosed with the disease.

What’s Different about Epione

With Epione we aim to resolve both of the problems above to make a truly privacy preserving contact tracing app. Specifically, we want to make sure that:

• Servers and central authorities do not learn anything about users contacts and social connections (unlike BlueTrace / TraceTogether)
• Other users cannot figure out who has been diagnosed positive, nor figure out which of their contacts caused them to be exposed to it (unlike Apple/Google and DP3T’s approach)
• Keeps processing and bandwidth costs for users efficient and practical

We use an advanced cryptographic technique called Private Set Intersection Cardinality (PSI-CA) combined with Private Information Retrieval (PIR) to allow users to check if they have received any tokens from people diagnosed with the disease, without users revealing any information about their contacts and without the server revealing any information about who has been diagnosed with the disease. We’ve also designed this so that it puts the vast majority of processing on the server, and designed it so that we can scale the system up to as many users as needed.

Scaling to a Global Solution

Every system comes with tradeoffs. In order to get the privacy guarantees we have in Epione, we have to do a lot more processing on the server and send a lot more bits across the network. Despite that, we believe that we can scale the system up to global levels by making some smart choices. That’s what we’re working on now.

What’s Next

We’re now working on building a proof-of-concept of Epione that can be used to integrate with a number of existing contact tracing apps. Watch this space for updates!

Special Thanks

Epione wouldn’t exist without my collaborators, Ni Trieu, Dawn Song, Prateek Saxena, and Reza Shokri. I’d also like to thank Min Suk Kang, Ilya Sergey, Jun Han, Xiaoyuan Liu, Duong Hieu Phan, Jiaheng Zhang, Tiancheng Xie, and Lun Wang for their contributions to Epione.