One week ago, Australia rolled out its Covid-19 contact tracing app. In the US, at least three states have advertised their own apps, and in Europe Covid contact tracing apps are scheduled for release in Italy and Germany. These efforts follow the earlier debuts of apps to track Covid in Singapore, South Korea, and China.

Meanwhile, Google and Apple – together responsible for key software on 99% of all smart phones – are teaming up to offer their own contact tracing solution.

With worldwide Covid deaths close to a quarter-million and restrictions being loosened in many countries near their peak number of active infections, we need good data about who has the virus and whom they might infect.

But which of the contact tracing apps are best? Why should we trust Google and Apple? And will their solutions make a difference?

What is contact tracing?

Contact tracing is nothing new. Usually, the procedure is done manually. When someone tests positive for a contagious disease, doctors conduct an interview to find out with whom the person has been in contact. Those contacts are tracked down so that they know to isolate themselves.

Unfortunately, manual contract tracing is hard. Who was the cashier that I paid at the gas-station? What was the name of the guy sitting next to me on the subway? Whom did my children talk to on the playground? And once doctors have made a list of these contacts, it is a painstaking process to track down and speak with every one of them. In the meantime, those contacts will have exposed many others to the disease.

On the bright side, manual contact tracing is limited and decentralized. Doctors only gather data from patients who have tested positive. This data is only shared with those who have been in the patients’ paths. Moreover, the data can be processed individually; Covid-positive Joe’s doctor can handle Joe’s data, and Covid-positive Sarah’s doctor can handle her data.

Centralized contact tracing on smartphones

Smartphones have all the tools required to perform electronic contract tracing. In fact, they have more than enough tools. These tools can be mixed and matched to create two very different solutions: centralized and decentralized solutions.

The centralized solution is what probably first comes to mind. The term “contact tracing” evokes the image of a massive, spatial-temporal map with millions of lines – created in most cases using GPS location data. Each line represents the movement of a single person. Intersections represent contact points. A large database must store this massive map, whether it is a within a government agency or a private company. This is a centralized solution because the data is all in one place.

The centralized solution the is approach taken by China, South Korea, and – most surprisingly – the early US apps that debuted in Utah and North and South Dakota.

How decentralized contact tracing works

In reality, the lines that represent individual movements are superfluous pieces of information. Contact tracing only requires knowing the intersections of these lines. In fact, only the intersections in which one person is Covid-positive are necessary. Apps can discard everyone else’s data once it ages more than two weeks.

Moreover, not everyone needs to know about this subset of intersections. The only people who need to know are the non-infected people who have taken part in an intersection. The government doesn’t need to know; the cell phone company doesn’t need to know, and even the infected person doesn’t need to know.

This principle is the base of the solution proposed by Google and Apple, and offered or to be offered by Singapore, Germany, Italy, and (more or less) Australia.

In the Google-Apple approach, phones that interact with other phones use Bluetooth to exchange a set of anonymized, cryptographic tokens that each expire after two weeks. If a user tests positive for Covid, he can voluntarily inform the app. The tokens that he had given out are then considered “poison;” all phones with poison tokens receive an alert suggesting that have been exposed. They know neither who has given them the poison tokens, nor where they were when the tokens were received.

This is a decentralized solution for two reasons. One reason is that only those need-to-know people are told that they have been exposed to the virus. The second reason is that the technological infrastructure itself is decentralized. Someone who wants to get private data would have to break into individual phones.

Bluetooth already allows peer-to-peer communication with other smartphones. The Google-Apple approach only (1) makes Bluetooth transmissions more frequent and (2) requires each phone to keep a two-week record of Bluetooth interactions.

Courtesy of Google
Courtesy of Google

Expert opinions

On April 30, the journal Nature offered an editorial about privacy concerns in contact-tracing apps. The article referenced a Joint Statement on Contact Tracing signed by 300 scientists from around the world; the Joint Statement itself is worth reading.

The opinions given by both Nature and the Joint Statement are quite balanced. They note that contact tracing apps “can complement a country’s overall Covid-19 control strategies” and “may improve the effectiveness of the manual contact tracing approach.” At the same time, “apps should not be rolled out without pilot studies or risk assessments,” and “solutions which allow reconstructing invasive information about the population should be rejected without further discussion.”

At the same time, the leitmotif of these expert opinions is not balance or trade-off, but diligent discrimination that identifies the best approach. The articles avoid the common perception of security (or here, health) and privacy as diametrically opposed. The important thing is to seek solutions that respect both and reject those that do not.

Contact tracing in South Korea, for instance, “is based on a degree of surveillance that people in many other countries would find hard to accept. When a person tests positive for Covid-19, a text alert is sent to everyone living nearby. The alert typically includes a link to a detailed log of the infected person’s movements – in some cases down to the last minute – which are reconstructed from public data, such as closed-circuit television cameras. But the government is also permitted to access confidential records, such as credit-card transactions. The data are then stored centrally by government agencies” (Nature). Privacy is essentially ignored.

On the other hand, “highly decentralized systems have no distinct entity that can learn anything about the social graph. In such systems, matching between users who have the disease and those who do not is performed on the non-infected users’ phones as anonymously as possible, whilst information about non-infected users is not revealed at all” (Joint Statement).

In summary, the articles reject GPS and centralized solutions as overly invasive, while Bluetooth and decentralized solutions are “highly preferred.”

But not everyone can be happy

The Joint Statement on Contact Tracing suggests a few additional principles. Apps should be used only to combat Covid – they must not be capable of collecting any more data than is necessary for this purpose. They should also be fully transparent. Users must understand how they work and where they store data. When multiple options to implement app functionality exist, then the most privacy-preserving option should be taken. Finally, the use of contact tracing apps and the systems that support them should be “voluntary, used with the explicit consent of the user.”

This last guideline is being followed by Google and Apple as well as almost all governments except for South Korea and China. In many ways, the requirement that contact tracing apps be voluntary seems like the most obvious one.

Unfortunately, completely voluntary apps probably will not work at all.

The problem with optional apps

Countries in which the app is voluntary hope that about 25% of the population will download it. But experts such as the international group Covid Watch say that at least 60% of the population would be necessary.

That’s because percentages in contact tracing degrade multiplicatively.

To detect a possible infection point, both the infected and uninfected person must have the app installed on a smartphone. Hence, if about one quarter of a country’s population installs the app, then only one quarter of one quarter or about 6% of the possible infections will be detected.

In reality, the numbers get even worse. Perhaps about half of people infected by Covid never become symptomatic, and so can’t tell the app that they have the disease. This lowers the estimate of detected contacts to about 3%.

And what about children who don’t have smartphones, elderly who don’t use them, and those who simply fail to report? In any case, it is hard to imagine optional apps identifying more than a few percentage points of potential Covid infections.

Mandatory contact-tracing applications?

In my opinion, legal incentives will be necessary to achieve the 60% adoption requisite to detect any significant portion of potential Covid infections.

What would these legal incentives look like?

Obviously, governments should not impose fines or other punishments for going out in public without using a contact tracing app. What about people who don’t have smartphones? What about those who “accidentally” leave them at home? China followed the approach of use-or-punish, but that doesn’t make it ethical. And outside of China, it wouldn’t be enforceable either.

Should governments go after smart phone companies such as Google and Apple instead, requiring them to make contact-tracing mandatory? My answer is “no.” Tech companies shouldn’t be forced to do something that they reasonably hold to be unethical. And consumers shouldn’t open their smartphones to find that they’ve received an update without their consent.

Yet governments have a duty to protect the common good, which certainly includes public health. Epidemics have the peculiar feature that individual actions affect society exponentially. And while 20 and 30-somethings have comparatively low risk of mortality, by catching Covid they endanger lives of the more vulnerable elderly. Hence, government regulation is needed.

Here is my suggestion. Many governments are currently relaxing restrictions in a step-by-step process. Here in Italy, for instance, manufacturing and construction will reopen on May 4. Shops, museums, and other public venues will open on May 18. Restaurants, bars, and hairdressers will open on June 1. Why not allow people who download a decentralized contact-tracing app to proceed one step ahead in the relaxation of restrictions? For instance, users with the app would be allowed to head to shops or museums on May 4, and they could go to restaurants on May 18. Those who do not own smartphones could obtain the same privileges by keeping detailed manual contact logs.

In tandem with the legal incentives, my suggestion is that Google and Apple specifically prompt users to ask if they want to install the app. Both installation and the submission of positive test results should be optional, but the app must be heavily advertised in order to succeed.

The good news is that app adoption will follow a cascading patten. There is little incentive for an initial group of people to download an app with few users. But if legal incentives can convince a critical mass, then other users should find the app increasingly attractive.

Many questions remain about the logistics of such an incentive system. And there is the potential for the legal precedent to cause a slippery slope. But the technical approach is solid, and as long as tens of thousands of lives are in the balance, government sponsorship is justified for a decentralized contact-tracing application.

Jeffrey Pawlick

Jeffrey Pawlick holds a PhD in Electrical Engineering from New York University, where he developed mathematical models for risk analysis in cyber security and information privacy in the Internet of things....