PPContactTracing: A Privacy-Preserving Contact Tracing Protocol for COVID-19 Pandemic

The Paillier cryptosystem is an additive, partially homomorphic, and asymmetric encryption scheme with public key and private key pair as ($n$ and $g$) and ($\lambda$ and $\mu$) respectively  [10].

The encryption of a plaintext message $m$ with public key ($n$, $g$) is done as follows:

$\displaystyle c~{}=~{}E(m,r;g,n)~{}=~{}\mbox{mod}(g^{m}\times r^{n},n^{2}),$

(1)

where $r$ is a random integer satisfying $0<r<n$. The incorporation of this random value ensures that the same plaintext is encoded as different ciphertexts under the same public key.

A ciphertext message $c$ is decrypted as follows:

$\displaystyle D(c;\lambda,\mu,n)$

$\displaystyle=$

$\displaystyle\mbox{mod}\left(\frac{\mbox{mod}(c^{\lambda},n^{2})-1}{n}\times\mu,n\right).$

(2)

It supports the following homomorphic properties:

• •

  The sum of two plaintexts $m_{1}$ and $m_{2}$ is equivalent to the decrypted product of corresponding ciphertexts $c_{1}$ and $c_{2}$ :

  $\displaystyle\mbox{mod}(m_{1}+m_{2},n)=D(\mbox{mod}(c_{1}\times c_{2},n^{2});\lambda,\mu,n)$

  (3)

• •

  The product of a scalar $s$ with a plaintext $m_{1}$ is equivalent to the decrypted exponentiation of the corresponding ciphertext $c_{1}$ with the scalar:

  $\displaystyle\mbox{mod}(s\times m_{1},n)=D(\mbox{mod}(c_{1}^{s},n^{2});\lambda,\mu,n)$

  (4)

The threat model is constructed for two sets of parties; the healthy person and infected person. For the healthy person, we consider a semi-honest adversary model. In the semi-honest adversary model, the client performs their computation honestly but tries to learn maximum information from the data they receive. For the infected person, in the protocol described in section III we assume that the infected person trusts the server with their data which is true in the case of a contact tracing scenario where the infected person gets interviewed by the contact tracers at the healthcare authority. In addition, we have discussed an extension in the section VI-A where the infected party also maintains a zero-trust model like the healthy person.

Partitioning a geographic space is a pretty standard terminology and can be done either using geohashes for square shaped grid cells or hexagonal using the H3 grid which is a global geo-spatial indexing system. An example of the square shaped grid is shown in Figure 1. This 3-dimensional grid is made accessible to all the users.

The proposed protocol takes as input, the geographic location (GPS coordinates of latitude and longitude) along with the time stamp of the location as the third dimension and maps this spatio-temporal location to discrete point-intervals. There lies a trade-off between the precise tracing of individuals and the amount of data that needs to be processed. If the time interval is made very small say 30 seconds, it will give more finer details of contact contact tracing compared to a time interval of 5 minutes but definitely with a significant increase in the bulk of data storage and computational resource requirements. The appropriateness of time interval and actual partitioning scheme can be decided based on the experiments and implementation details.

Let us suppose the landscape $L$ is divided into square grid cells ${l_{1},l_{2},l_{3},\ldots l_{n}}$ in order. Based on the client-server model, the user can be considered as the client $S_{A}$ and the diagnosed infected user as the server $S_{B}$. The locations visited by the entity can be represented by a bit vector of same length as the number of square grid cells. If a grid cell $l_{i}$ has been recently visited, it is represented by a corresponding bit value of $1$ else the replaced with a $0$ value maintaining the same order as of the original grid cells. Let us represent the bit vectors for the client $S_{A}$ and the server $S_{B}$ by $\overrightarrow{{t_{i}}^{A}}$ and $\overrightarrow{{t_{i}}^{B}}$ respectively. Each entity encrypts every bit of their trajectory using a public/private key pair. In the client-server model, let $(p_{A},s_{A})$ and $(p_{B},s_{B})$ be the corresponding keys. The encryption and decryption are represented as functions: $Enc_{p_{k}}()$ and $Dec_{s_{k}}()$ using the public key/secret key pair as $(p_{k},s_{k})$ respectively.

The client-server interacts in the following manner to obtain the set intersection.

1) The client $S_{A}$ encrypts each bit of its trajectory bit vector ${t_{i}}^{A}$ using its public key $p_{A}$

$$c_{i}=Enc_{p_{A}}({t_{i}}^{A})$$

(5)

This ciphertext $c_{i}$ $(1\leq i\leq n)$ is then sent to the server.

2) The server receives the encrypted ciphertext $c_{i}$ $(1\leq i\leq n)$ and processes on top of this encrypted ciphertext to obtain

$$d_{i}={(c_{i})}^{t_{i}^{B}}.Enc_{p_{A}}(0)$$

(6)

This processed ciphertext $d_{i}$ $(1\leq i\leq n)$ is then sent to the client.

3) The client decrypts the received ciphertext $d_{i}$ using its secret key $s_{A}$

$$t_{i}=Dec_{s_{A}}({d_{i}})$$

(7)

These $t_{i}^{\prime}s$ fetches the information of the set intersection or possible matches based on following:

$$t_{i}=\left\{\begin{matrix}1&if\ l_{i}\in S_{A}\bigcap S_{B}\\ 0&if\ l_{i}\not\in S_{A}\bigcap S_{B}\end{matrix}\right.$$

(8)

The proposed protocol preserves the privacy of both client and server. The client shares its encrypted trajectory bit vector $c_{i}$ to the server. The server processes the ciphertext and sends the processed ciphertext $d_{i}$ to the client. The client then decrypts the received processed ciphertext to obtain information about the matching or overlapping regions based on decrypted bits $t_{i}$. Positions where $t_{i}$’s are $1$ represent the overlapping or matched locations else they have no suspicion of contact. The privacy of the server is preserved by multiplication of the ciphertext by encrypted zero after exponentiation with the trajectory bit vector $t_{i}^{B}$ of the server in step 2 of the set operation phase. This operation is exploiting the additive homomorphic property that allows exponentiation and multiplication on the ciphertexts equivalent to the scalar multiplication and addition in the corresponding plaintexts.

$$\begin{matrix}d_{i}&=&{(c_{i})}^{t_{i}^{B}}.Enc_{p_{A}}(0)\\ &=&\ Enc_{p_{A}}(t_{i}^{A}\times t_{i}^{B}+0)\\ &=&Enc_{p_{A}}(t_{i}^{A}\times t_{i}^{B})\\ \end{matrix}$$

(9)

Multiplication of encrypted zero is equivalent to addition of zero in the plaintext. Thus, it makes no difference to the result but helps to preserve the privacy of the server. If this multiplication by encrypted zero is not done in the processed ciphertext, then it may leak the trajectory bit vector $t_{i}^{B}$ of the server.

$$d_{i}=\left\{\begin{matrix}c_{i}&if\ \ t_{i}^{B}=1\\ 1&if\ \ t_{i}^{B}=0\end{matrix}\right.$$

(10)

The setup is same as the proposed protocol. The bit vectors $\overrightarrow{{t_{i}}^{A}}$ and $\overrightarrow{{t_{i}}^{B}}$ represent the client $S_{A}$ and the server $S_{B}$. $(p_{A},s_{A})$ and $(p_{B},s_{B})$ as the (public key, secret key) pairs.

The client-server interacts in the following manner to obtain the set intersection.

1) The client $S_{A}$ encrypts each bit of its trajectory bit vector ${t_{i}}^{A}$ using its public key $p_{A}$

$$c_{i}=Enc_{p_{A}}({t_{i}}^{A})$$

(11)

This ciphertext $c_{i}$ $(1\leq i\leq n)$ is then sent to the server.

2) The server receives the encrypted ciphertext $c_{i}$ $(1\leq i\leq n)$ and processes on top of this encrypted ciphertext to obtain

$$d=\prod_{i}^{n}{(c_{i})}^{t_{i}^{B}}.Enc_{p_{A}}(0)$$

(12)

This processed ciphertext $d$ is then sent to the client.

3) The client decrypts the received ciphertext $d$ using its secret key $s_{A}$

$$t=Dec_{s_{A}}({d})$$

(13)

This $t$ gives the information about the cardinality of the set intersection.

The proposed protocol preserves more privacy of both client and server. The client gets to know the cardinality of the set intersection whereas the server does not get any information in the whole process.

The client encrypts its trajectory bit vector and sends the encrypted trajectory bit vector $c_{i}$ to the server. The server processes the ciphertext and sends the processed ciphertext $d$ to the client. The client decrypts $d$ and obtains $t$ which gives the information about the cardinality of the set intersection or the matching regions.

The processing at the server in step 2 exploits the additive homomorphic property.

$$\begin{matrix}d_{i}&=&{\prod_{i}^{n}(c_{i})}^{t_{i}^{B}}.Enc_{p_{A}}(0)\\ &=&\prod_{i}^{n}((Enc_{p_{A}}(t_{i}^{A}))^{t_{i}^{B}}).Enc_{p_{A}}(0)\\ &=&\prod_{i}^{n}(Enc_{p_{A}}(t_{i}^{A}\times t_{i}^{B})).Enc_{p_{A}}(0)\\ &=&Enc_{p_{A}}(\sum_{i}^{n}(t_{i}^{A}\times t_{i}^{B})).Enc_{p_{A}}(0)\\ &=&Enc_{p_{A}}(\sum_{i}^{n}(t_{i}^{A}\times t_{i}^{B})+0)\\ &=&Enc_{p_{A}}(\sum_{i}^{n}(t_{i}^{A}\times t_{i}^{B}))\\ \end{matrix}$$

(14)

Thus, the privacy of the server is preserved in step 2 of the set operation phase by multiplication of the ciphertext by encrypted zero after exponentiation with the trajectory bit vector $t_{i}^{B}$. Nothing is leaked to the server and the client only gets to know the cardinality of the intersection of the sets after decryption of the processed cipher received from the server.

$$\begin{matrix}t&=&Dec_{s_{A}}({d})\\ &=&Dec_{s_{A}}(Enc_{p_{A}}(\sum_{i}^{n}(t_{i}^{A}\times t_{i}^{B})))\\ &=&\sum_{i}^{n}(t_{i}^{A}\times t_{i}^{B}))\\ \end{matrix}$$

(15)

In our protocol, the client communicates only once a day since there is no need to query for exposure notification more than a day. Therefore, the communication complexity depends on how much data is transferred in a single batch transfer. Current GPS apps used for contact tracing record GPS data every five minutes, hence for simplicity, we also use the same number for our communication complexity analysis. Every five minutes of GPS scan leads to $288$ scans for any given day. Hence, user uploads $288xN$ points in a single batch. Here, $N$ is the total size of the vector used to represent a single GPS scan which is also equal to the total number of cells in the location grid. We use one-hot representation of this vector with $M$ being the size of every element in the one-hot vector. Hence the communication complexity is $O(M*N)$ bits. From a practical standpoint, there is no significant communication overhead for individuals because they query the server only once a day. For the Server, it is possible to scale up receiving endpoint by simply using horizontal scaling or load balancing.
The communication complexity for the download is same as upload in the case of full private set intersection protocol. However, for the case of private set cardinality, the server only returns a single encrypted number to the client indicating whether there is a match or not.

In this setting, we assume that the central server can not be trusted even with regards to the data of infected person. We extend the current method as described in the section 4 by adding one extra server which solely performs the key exchange between the healthy and infected person database. Both healthy and infected party can download the keys from this key exchange server and encrypt their data and upload it for comparison on the computation server responsible for executing the operations mentioned in  6.

From the point of view of public trust as well as stringent security requirements, it is reasonable to put another constraint in the protocol by requiring no data upload by the healthy individual, be it as a plaintext or ciphertext. This can be achieved by having the computation to be performed on-device of the healthy person. However, direct sharing of encrypted or plaintext location information of the infected individual would allow the healthy person to perform brute-force attack and hence leak all of the information about the infected individual. This could be circumvented by having the healthy client know only the public key $p_{A}$ and hence they can only compute the encryption and the operations mentioned in the eq. 6. Then the results of the computation are shared with the server which decrypts the result and returns it back. This would prevent the brute-force attack because the server can enforce rate limiting to limit the queries which can be decrypted by a given healthy individual. If we want to hide the results of the computation from the server, the client can blind the outputs by multiplying with additional blinding factor, making the difficulty of recovering the results as difficult as the factorization problem. In principal, we achieve this extension by sending encrypted result of the computation instead of sending the encrypted plaintext. Note that this could hurt the efficiency of the protocol because now the whole computation load resides on the client device which is a handheld device. Hence, this solution comes with a trade-off between secrecy of the ciphertext vs the efficiency of the overall protocol.