This is an open-access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work, first published in the Journal of Medical Internet Research, is properly cited. The complete bibliographic information, a link to the original publication on https://www.jmir.org/, as well as this copyright and license information must be included.
Various techniques are used to support contact tracing, which has been shown to be highly effective against the COVID-19 pandemic. To apply the technology, either quarantine authorities should provide the location history of patients with COVID-19, or all users should provide their own location history. This inevitably exposes either the patient’s location history or the personal location history of other users. Thus, a privacy issue arises where the public good (via information release) comes in conflict with privacy exposure risks.
The objective of this study is to develop an effective contact tracing system that does not expose the location information of the patient with COVID-19 to other users of the system, or the location information of the users to the quarantine authorities.
We propose a new protocol called PRivacy Oriented Technique for Epidemic Contact Tracing (PROTECT) that securely shares location information of patients with users by using the Brakerski/Fan-Vercauteren homomorphic encryption scheme, along with a new, secure proximity computation method.
We developed a mobile app for the end-user and a web service for the quarantine authorities by applying the proposed method, and we verified their effectiveness. The proposed app and web service compute the existence of intersections between the encrypted location history of patients with COVID-19 released by the quarantine authorities and that of the user saved on the user’s local device. We also found that this contact tracing smartphone app can identify whether the user has been in contact with such patients within a reasonable time.
This newly developed method for contact tracing shares location information by using homomorphic encryption, without exposing the location information of patients with COVID-19 and other users. Homomorphic encryption is challenging to apply to practical issues despite its high security value. In this study, however, we have designed a system using the Brakerski/Fan-Vercauteren scheme that is applicable to a reasonable size and developed it to an operable format. The developed app and web service can help contact tracing for not only the COVID-19 pandemic but also other epidemics.
Since the first case of a previously unidentified coronavirus was reported in Wuhan, China, on December 8, 2019, the COVID-19 pandemic has affected the whole world. According to the World Health Organization (WHO), as of January 25, 2021, the number of COVID-19 cases worldwide was about 97 million, 2.1 million of which were reported to have been fatal [
Therefore, it is imperative to understand the disease propagation and timing in order to take appropriate and timely measures. For example, when 97 patients with COVID-19 were confirmed at a call center in South Korea in March 2020, the Korea Centers for Disease Control and Prevention and the local government formed a joint response team and carried out an epidemiologic investigation using contact tracing [
Ferretti et al [
An active measure against the COVID-19 pandemic requires, for example, telehealth screening and management and remote testing, but privacy regulations may pose barriers to such information dissemination. Accordingly, there are claims that privacy regulations should be relaxed for health information exchange in the context of the COVID-19 pandemic [
To resolve such issues, applications and technologies are being developed that digitally execute contact tracing while protecting user privacy [
This study aims to propose the PRivacy Oriented Technique for Epidemic Contact Tracing (PROTECT) protocol for digital contact tracing that offers privacy protection by using homomorphic encryption. The proposed system exchanges location data in an encrypted format between the user and the quarantine authorities. By using a novel secure proximity computation technique, the PROTECT protocol makes it possible to identify whether the user has been in contact with any patient with COVID-19 by using only the encrypted location information. This method differs from the privacy protection technologies used in existing contact tracing systems in that it identifies the contacts with encrypted distances, and thus, it can identify whether the user has been in contact with patients with COVID-19 without exposing the user’s location information. It can be said the proposed system uses a privacy-preserving technique of a higher order. In this paper, we first propose a new algorithm for proximity computation and the PROTECT protocol that utilizes this algorithm. Next, we introduce the quarantine app and web service that we have developed to apply the proposed PROTECT protocol to COVID-19 contact tracing and verify that the proposed protocol is practical through experimentation. Finally, we discuss the key results of the study, how it differs from previous studies, and its limitations.
The key to a privacy-preserving contact tracing system is to protect the location information of not only the patient but also the user, along with the ability to check for proximity. To achieve this, in this study, we used homomorphic encryption and proximity in a discrete grid system to develop a new, secure proximity computation method, and propose a new protocol called PROTECT that applies such a method to deliver data safely among the user, quarantine authorities, and the patient.
The basic method to check for proximity is to compute the distance between two known locations, but this leads to unnecessary location-related privacy issues [
Homomorphic encryption is a cryptosystem that supports computation on encrypted data. The result of encrypted computation is also a ciphertext whose decryption returns the same value as if the operation were performed over plain data. Homomorphic encryption has broad applications in cloud environments since it can be used to outsource storage and computation without data leakage.
In the last decade, there have been significant improvements in the efficiency of homomorphic encryption. Lattice-based schemes such as Brakerski-Gentry-Vaikuntanathan (BGV) [
The BFV scheme consists of five polynomial-time algorithms Setup, Enc, Dec, Add, and Mult. Note that we use symmetric-encryption, which is faster and has better noise growth compared to the public-key variant.
Setup (1λ): For the security parameter λ, choose a parameter set and sample a secret key
Enc (
Dec (
Add (
Mult (
The BFV scheme satisfies the homomorphic property if parameters are chosen properly. In other words, if
In this study, we converted the two location points to a hexagonal grid system and defined that any two points that belong to the same or adjacent grids are “proximate.” The proximity between locations in a continuous space, for example, Euclidean space must be checked with comparison operations; such computation is expensive in a homomorphically encrypted system. The proximity in a discrete space, however, can be computed with a few equality checks, which can be efficiently calculated over encrypted data.
We choose the hexagonal grid system to transform the continuous location information into discrete grids. A hexagonal grid system allows for a simpler definition of neighborhood than triangular or square grids do, so as to reduce the computation overhead. As shown in
The transportation network company Uber Technologies Inc introduced a discrete global grid system called Hexagonal Hierarchical Spatial Index (H3) that is based on multiresolution hexagonal grids [
We denote by
Comparison of (A) triangular, (B) square, and (C) hexagonal grids.
Local
We also define a metric function as follows:
which can be computed as follows:
where
We use the metric
In the following, we present two properties of
Distance between two points
If
If ‖P–Q‖ <
In case of a highly contagious epidemic such as COVID-19, a single patient may cause a reproliferation; thus, the examination scope should be rather conservatively set to be broad. The WHO recommends massive testing for all suspected cases of COVID-19 [
The proposed protocol PROTECT involves three parties—the user, the quarantine authorities, and the patient with COVID-19. The overall protocol flow is shown in
In this study, we assume that the quarantine authorities are semihonest and that the patient honestly provides their location history to the authorities. The WHO recommends that, as essential surveillance for COVID-19 considering the potential for rapid exponential growth of COVID-19 cases in populations, new cases should be identified, reported, and data included in epidemiological analysis within 24 hours. National authorities should consider including COVID-19 as a mandatory notifiable disease with requirements for immediate reporting [
Flowchart of the Privacy Oriented Technique for Epidemic Contact Tracing (PROTECT) protocol.
The patient is a user who has been tested positive for COVID-19 and provides 2-week GPS location history to the quarantine authorities. At this time, the location information of the patient is not encrypted.
The quarantine authorities are those individuals who oversee the quarantine system at the municipal or national level. The quarantine authorities receive the location information provided by the patient, encrypt it, and upload it to the server. The encrypted patient location information is then sent to the users who have installed the app. In addition, the quarantine authorities receive the result of the computation at the local user device in the encrypted format, decrypt that result, and then send the decrypted result back to the user. In this process, the quarantine authorities have no access to the personal location information stored on the local user device.
The user computes, on the individual local device, the proximity between their own location information and the encrypted patient location information received from the quarantine authorities. Here, homomorphic encryption makes it possible to execute computation between the encrypted location information and nonencrypted location information. The computation result is encrypted, as shown in
In this section, we provide technical details of proximity computation in the PROTECT protocol. Throughout this section,
Before the protocol starts, the quarantine authorities and the user encode their data locally into the IJ co-ordinates by using the
The server sets the parameters for BFV and generates a secret key . The server generates ciphertexts
On receiving the ciphertexts, the user securely computes the proximity between and . This procedure consists of homomorphic evaluation of the proximity function followed by a ciphertext randomization process.
First, the user homomorphically evaluates
This is an encryption of the vector (
Hence, the user randomizes the ciphertext
The quarantine authorities decrypt
In order to apply the PROTECT protocol to COVID-19 contact tracing, we have built a mobile app for patients with COVID-19 and other users, as well as a web service for the quarantine authorities. We also empirically verified the practicality of the PROTECT protocol through performance indicators related to resource consumption such as response time, CPU utilization, and memory consumption on the local device.
The smartphone app for the user is as shown in
Screenshots of the user application: (A) main screen, (B) GPS data recording setup screen, (C) list of GPS data by day stored on the user's local device, (D) list of encrypted GPS data per patient received from the quarantine authorities, and (E) location history comparison and result.
The role of the quarantine authorities is to manage COVID-19 patient information and to propagate test results. For this purpose, we built a web service as shown in
Screenshots of the web service developed for quarantine authorities: (A) list of confirmed patients’ GPS data, (B) list of contact trace histories, and (C) register of new confirmed patients’ GPS data.
To assess the practicality of the app that implements the proposed PROTECT protocol, we installed the developed app on two smartphone models—Samsung Galaxy S20 Plus and Galaxy Note 8—and conducted performance tests. The detailed specifications of the testing devices are as in
Specifications of testing devices.
Specifications | Galaxy S20 plus | Galaxy Note 8 |
Release Year | 2020 | 2017 |
Chipset | Samsung Exynos 9 Octa 990 | Samsung Exynos 9 Octa 8895 |
Processor | Octa core |
Octa-core |
GPU | ARM Mali-G77 MP11 | ARM Mali-G71 MP20 |
RAM | 8 GB | 6 GB |
To satisfy 128-bit security level while maintaining an appropriate size for computation, the base ring dimension was set to 8192, which indicates that the proximity computation for 8192 time points can be executed simultaneously. At the same time, the computation time for the entire data is determined by the size of the base ring dimension. When GPS data is collected every
It is not necessary to use all time points to compare the time points of the user and the patient. The location information can be trimmed through various methods. It is not necessary to compare all time points for periods where the patient has stayed at a single location for a long time, such as while sleeping or working. In case many patients were present at the same location at the same time, a single computation shall suffice. Furthermore, the occasions wherein the patient has certainly made no contact, such as while driving alone, can also be excluded. Such preprocessing of data can be applied before encryption by the means of epidemiological investigation, when the quarantine authorities collect the location history data of the patients.
If the number of data points refined by the quarantine authorities is
As for the proposed PROTECT protocol, the computation times may vary depending on the processing power of the user’s smart device. The test results for computation time in Samsung Galaxy S20 Plus and Note 8 are as presented in
Results of proximity computation tests on testing devices.
Test | Galaxy S20 Plus | Galaxy Note 8 |
Average CPU utilization (%) | 2.158 | 5.425 |
Maximum memory consumption during computation (MB) | 57.57 | 58.6 |
Computation time ( |
3.246 | 6.967 |
Size of encrypted data (MB) ( |
1.08 | 1.08 |
Size of encrypted data (MB) ( |
0.814 | 0.814 |
Since S20 Plus has a more powerful processor than that of Note 8, it can be seen that is smaller. When S20 Plus is to compute 1,000,000 encrypted data points received from the quarantine authorities,
In addition, the CPU utilization level also varies depending on the processing power of the device. Samsung Galaxy S20 Plus shows a lower average CPU utilization level than that of Note 8. In case of memory consumption during computation, no significant difference was observed. As for CPU utilization and memory consumption, the proximity computation is repeated in batches of 8192, so the increase in the overall time points does not result in several fold increases.
This study proposed the PROTECT protocol, which utilizes homomorphic encryption to protect privacy while performing digital contact tracing. For this, a novel secure proximity computation technique has been developed so that the location data can be encrypted and exchanged between the user and the quarantine authorities, while the potential COVID-19 patient contact can be identified with encrypted distances only. This method differs from the privacy protection measures used in existing contact tracing systems in that it identifies contacts with encrypted distances, enabling a far higher level of privacy-preserving contact tracing. Our proposed protocol assumes the existence of a centralized organization that already collects the location history of patients and checks for proximity without exposing the location information of the patient to the user or that of the user to the organization. The Bluetooth-based method proposed by Apple and Google requires adoption by a majority of the population for contact tracing to take effect. Our proposed protocol, however, can exhibit the effect of contact tracing for those who have installed the app, no matter how small the number of such users is, provided that the quarantine organization encrypts and provides the patient data collected so far. In addition, the user does not have to provide their location information to the government, which is an advantage against psychological repulsion, one of the greatest hindrances against promoting the use of such an app.
Furthermore, in order to apply the PROTECT protocol to the COVID-19 pandemic, we built a mobile app for patients and users and a web service for the quarantine authorities. In addition, the performance indicators related to resource consumption, such as computation time, CPU utilization, and memory consumption, verify that this protocol is practical enough to be applied to actual COVID-19 quarantine measures.
Contact tracing in Euclidean space is not secure in terms of privacy. To check for proximity under the Euclidean system, one must first compute the Euclidean distance between the two known locations. This, however, leads to an unnecessary location privacy issue. In order to calculate proximity between the locations of two parties, whoever executes that calculation—be it one of the two parties or an entirely separate third party—must possess the location information of both parties. This implies that at least one party must reveal their location information to another party. On the other hand, as previously discussed, the PROTECT protocol can only determine that two locations are in the same or adjacent grid through secure proximity computation.
Since the hexagonal grid system recognizes a wider range as adjacent than the Euclidean distance method, contact tracing in Euclidean space might appear to be more efficient than the PROTECT protocol. Suppose that we need to test everyone who is within a Euclidean distance of
As COVID-19 is highly contagious, the spread of COVID-19 cannot be covered by the Euclidean space. Rather, the examination scope should be expanded sufficiently. As mentioned earlier, many international organizations are already recommending mass testing for COVID-19 [
A circle with radius
Inline graphic 2.
The proposed protocol and system also have limitations shared by all contact tracing methods that make use of digital technologies. First, there is the limitation of the performance of the smartphone device itself. The accuracy of the GPS location data of each device may vary. GPS, especially, when compared to Bluetooth, is relatively less accurate in an urban setting with many indoor environments and high-rise buildings. Such limitations of the device performance can be complemented by using indoor positioning data such as Wi-Fi and Bluetooth, as well as geomagnetic location measurement techniques. In fact, the indoor positioning data collection technologies have seen much improvement through the advancement of technologies such as fingerprinting.
Second, in this study, all patients with COVID-19 are considered. However, in actual quarantine scenarios, we only need to compare to the patients in the corresponding region, thus reducing the total time taken for the comparison. Third, the homomorphically encrypted computation logic was developed in the same language for both the web server and the mobile app. Thus, there were inefficiencies to make it run within an Android app, such as porting Microsoft SEAL (Simple Encrypted Arithmetic Library) to WebAssembly with a JavaScript interface and then running it on a JavaScript engine within a browser. This should be addressed by directly invoking SEAL C++ APIs (application programming interfaces) using JNI (Java Native Interface) for Android applications. Resolving such inefficiencies would enable the development of a practical solution that is applicable to actual quarantine scenarios.
In order to prevent the location privacy issue related to the calculation of proximity using location information, Gruteser and Grunwald [
In contrast, the secure proximity computation method used in this study substitutes the problem of proximity calculation with the computation of identity or adjacency of two grids by mapping the exact location information to a predefined grid system, and then executes the calculation under homomorphic encryption, thus being safe in terms of location privacy and excellent in terms of computation.
Furthermore, from a system-wise perspective, most existing apps, such as TraceTogether [
The whole world is facing an unprecedented global pandemic situation and is trying to overcome this crisis by all means. Various information technology solutions are being actively suggested in this context. Owing to the potential risk of privacy leaks, however, the adoption rates are low and there has been no case of a
In this study, we have described the development of a new proximity computation algorithm that can identify proximity occurrences without exposing the COVID-19 patient location and the user location to one another by homomorphically encrypting the location information. We propose PROTECT, a privacy-preserving contact tracing protocol that uses this algorithm, for use during the current COVID-19 pandemic. In order to apply this protocol to COVID-19 quarantine measures, the proposed protocol has been implemented as a smartphone app for patients and the public and a web service for quarantine authorities. Homomorphic encryption of the BFV scheme is used to design a system applicable to a reasonable scale, and through experiments under various conditions, it has been verified that this service is practical enough to be implemented in a real-world scenario. We hope that this approach that intends to resolve the issue through new technologies contributes to the early discovery and suppression of other potential diseases in future.
application programming interface
Brakerski/Fan-Vercauteren
Brakerski-Gentry-Vaikuntanathan
Cheon-Kim-Kim-Song
Hexagonal Hierarchical Spatial Index
Java Native Interface
Organisation for Economic Co-operation and Development
Privacy Oriented Technique for Epidemic Contact Tracing
Simple Encrypted Arithmetic Library
fast fully homomorphic encryption scheme over the torus
World Health Organization
None declared.