Privacy-Preserving Identification of Target Patients from Outsourced Patient Data

The most common mutation in human population is called single nucleotide polymorphism (SNP). It is the variation in a single nucleotide at a particular position of the genome (risch2000searching, ). There are about 5 million SNPs observed per individual and sensitive information about individuals (such as disease predispositions) are typically inferred by analyzing the SNPs. Two kinds of nucleotides (or alleles) are observed for each SNP: (i) major allele is the one that is observed with a high frequency and (ii) minor allele is the one that is observed with low frequency. The frequency of the minor allele in a given population is denoted as the minor allele frequency (MAF). Each SNP includes two nucleotides, one inherited from the father and the other one from mother. For simplicity, we represent the value of a SNP $i$ as the number of its minor alleles, and hence $SNP_{i}\in\{0,1,2\}$. A SNP is represented by an (ID, value) pair, where the ID is taken from a large standardized set of strings and the value is in $\{0,1,2\}$. In the following sections, if we mention a SNP (or SNPs) without mentioning the ID or value, we mean both parts.

Let $G$ be an additive group of prime order $p$ and $g_{1}\in G$ be the generators of $G$ and $g_{2}\in G$ is a random element from $G$. Let $e:G\times G\rightarrow G_{T}$ be a function which maps two elements from $G$ to an element in the target group $G_{T}$ having prime order $p$. The tuple $(G,G_{T},p,e)$ is an symmetric bilinear group if following properties hold:
(a) the group operations in $G$, $G_{T}$ are efficiently computable.
(b) the mapping $e$ from $G$ to $G_{T}$ is efficiently computable.
(c) the mapping $e$ is non-degenerate: $e(g_{1},g_{2})\neq 1$.
(d) the mapping $e$ is bilinear: for all $a,b\in\mathbb{Z}_{p}$, $e(g_{1}^{a},g_{2}^{b})=e(g_{1},g_{2})^{ab}$. Based on the symmetric bilinear group, we design an encryption algorithm to encrypt phenotypes of patients.

As shown in Figure 1, the system consists of three types of entities: clients, hospitals, and a cloud service provider (CSP). The hospital collects biological samples from patients and sequences them with patients’ consent. In parallel, the hospital records various phenotypes of patients (e.g., height, eye color, and blood type). Instead of storing all genotype and phenotype data locally, the hospital encrypts the data and outsources them to the CSP. The client (e.g., a medical researcher) queries the CSP for different association studies on datasets of several hospitals. Before sending a query to the CSP, the client needs authorization from the involved hospital(s). If the client gets such an authorization, the corresponding computation is allowed to be conducted over all hospitals’ datasets. Upon receiving a query from a client, the CSP first constructs the identification of target group of patients (e.g., case and control groups) by running the query over the encrypted phenotype data, and then executes the other algorithms (e.g., GWAS) over the encrypted genotype data of individuals in the identified groups (e.g., case and control groups).

In the proposed scheme, we make an assumptions to make sure that the data model is uniform across hospitals. We assume there exists a common set of terms applied to describe all the phenotypes across hospitals (referred as “phenotype attributes”). That is, all the hospitals use the same terms to describe the same phenotypes.

For efficiency, we represent the value of a phenotype attribute in a binary format (as $0$ or $1$). $1$ means that the patient matches the phenotype attribute while $0$ denotes the opposite. For instance, Table 2 illustrates a partial taxonomy of phenotypes that includes different height ranges in centimeters, as well as presence of breast cancer.

The value of each SNP is set to represent its number of minor alleles ($0$, $1$, or $2$) (see the details in Section 3.1). Based on these settings, the phenotype and SNP dataset for hospital $i$ are represented as in Tables 2 and 3, respectively. In the following sections, when we mention phenotype, it means both phenotype attribute and value, and when we mention SNP, it means both SNP identity and value.

The query mechanism is designed to find target groups of patients for specified phenotypes. In the proposed scheme, the query includes two parameters: (i) a list of phenotypes of interest and (ii) a parameter to set the size of matching groups (e.g., case and control groups). As an instance, we use case and groups to illustrate the query mechanism. For simplicity, we assume the size of case and control groups to be equal, but it can be customized to support different sizes.

Prior to outsourcing the data to the CSP, a hospital first encrypts its phenotype dataset by using the proposed pairing-based encryption algorithm that supports efficient search over encrypted phenotypes (as discussed in Section 5). A query is generated by the client with input phenotype attributes and sent to the CSP. The proposed scheme allows a client to form the case and control groups based on multiple phenotype criterion (e.g., an association study for a particular type of cancer can be conducted only on males within a specific age range). The CSP, using the properties of the proposed pairing-based encryption, can check whether an encrypted patient’s record (in a hospital’s dataset) contains the phenotype attributes inside the query. If all the phenotype attributes in the query are included in a patient’s record, the record is added into case group. In contrast, if a patient’s record does not include any of the phenotype attributes in the query, the patient’s record is added into the control group. Note that the query is encrypted without disclosing any phenotype information to the CSP and the CSP cannot learn any information from the search process. Thus, the CSP identifies the individuals in the case and control groups in a privacy-preserving way. The case and control groups may possibly contain patients from multiple hospitals. Specifically, given a query from a client and transform keys (detailed in Section 5.6) from hospitals that authorize the client to access their data, the CSP can search multiple hospitals’ phenotype datasets (encrypted by using different secret keys). Thus, the search result is not limited to one hospital’s dataset.

Our threat model is consistent with previous work (lu2015privacy, ; schneider2019episode, ). Client, hospital(s), and the CSP are assumed to be semi-honest, that is, they honestly follow the protocol while trying to learn extra information during the protocol. A hospital may try to use its own data and knowledge to infer another hospital’s data either via collusion with the CSP or exploring the common patient records in different hospitals. The CSP may analyze the stored ciphertext and observe the encrypted queries. Based on this information, the CSP may try to extract sensitive information. Also, a client may try to infer patients’ data without having proper access authorization. Specifically, we consider following attacks:

We thoroughly analyze all these attacks and robustness of the proposed scheme against them in Section 6.

In the proposed scheme, hospitals independently encrypt and outsource their phenotype datasets to a CSP and the CSP conduct search operation over the outsourced federated data (from multiple hospitals) to identify target group of patients. To process phenotype data in an efficient and privacy-preserving way, we propose a novel encryption mechanism to encrypt the phenotype data. The proposed encryption scheme allows different hospitals to encrypt their phenotype data independently with their own secret keys. Moreover, the encryption algorithm supports identification of case and control groups efficiently, without information leakage. Furthermore, the identification process requires less communication compared with secure multi-party computation-based approaches (schneider2019episode, ) and less computation compared to homomorphic encryption-based approaches (akavia2019setup, ). In general, the execution of privacy-preserving identification of target group of patients can be divided into seven phases: data preprocessing, initialization, key generation, data encryption, client authorization, query generation, identification of case and control groups. We now present a high-level overview of these seven phases while the rest of this section provides in-depth details.

In this section, we present the procedures we use to preprocess the phenotype data, so that the processed data matches the data format requirements.

In this section, we present the procedures during the initialization so that all algorithms use the same initial parameters.

In this section, we present the procedures to generate the required keys in the system.

In this section, we describe the proposed phenotype data encryption algorithm, which supports efficient privacy-preserving search and update.

In the proposed scheme, a client needs to get authorization from a hospital before it can access to (operate on) a hospital’s data. Meanwhile, the hospital is capable to authorise the client in fine-granularity and the CSP should not learn the data that the hospital authorises the client to access. In this section, we first present a simple client authorization mechanism, which requires a client to generate a query for each hospital that authorizes the client to access its data. In addition, this mechanism allows a client to access a hospital’s data without any limitations once it is authorized. Then, to achieve flexible authorization and let the client generate a single query that can be used to operate on all authorized hospitals’ datasets, we further present an improved mechanism. The improved mechanism supports per-query based fine-grained authorization and it allows a single query to access multiple hospitals’ data.

The query is generated based on client’s input that specifies phenotype data of interest. Then, the query is executed over encrypted phenotype data. Algorithm 6 shows query generation based on the input of a single phenotype. The client first applies the hash function $H$ on the input phenotype attribute and value, obtaining $\alpha_{c,k}$ ($k\in\mathbf{A}$) as the output. Then, the client computes a group element $g^{r_{c,k}}$, where $r_{c,k}$ is selected during the generation of authorization request. $g^{r_{c,k}}$ is included in the query. Afterwards, the client computes the other part of the query: $g^{-r_{c,k}\alpha_{c,k}}PK_{c}^{r_{c,k}}$. To support multiple phenotypes in a query, the client can iteratively invoke the SinglePhenotypeQueryGen algorithm. In detail, given a set $\Delta$ of phenotypes, for each phenotype inside $\Delta$, the client calls SinglePhenotypeQueryGen to encrypt it. The result $q_{c,k}$ ($1\leq k\leq n$) is stored in a vector $\mathbf{v}_{c}$, which has the same dimension and the same order of phenotype attributes as $\mathbf{A}$. For the phenotypes whose phenotype attributes are in $\mathbf{A}$ but not in $\Delta$, the corresponding value is set to $0$ in vector $\mathbf{v}_{c}$. $q_{c}$ is a set and it includes the vector $\mathbf{v}_{c}$. Finally, in addition to $\mathbf{v}_{c}$, the size $N$ of case and control groups is also included in $q_{c}$ before $q_{c}$ is sent to the CSP.

Algorithm 7 shows how to extends the input from a single phenotype to multiple phenotypes. Here, for each phenotype inside the input phenotype data set $\Delta$, the client invokes Algorithm 6. Once all the input data are processed, the algorithm outputs the final query $q_{c}$. Note that all the positions, where phenotype attributes are not included in the input phenotype data are filled with zeros. For example, a client can input a set of pairs of phenotype attribute and value as {(breast cancer, 1), (lung cancer, 0), (blue eye color, 1)} to generate a query. Applying above algorithms, each target phenotype attribute is corresponding to a component $q_{c,i}$ in the query, the remaining that is not included in the input phenotype attribute set is set to $0$. The final query also includes the size $N$ of case and control groups.

Without loss of generality, we present the identification process at the CSP over a single hospital $i$’s dataset. Multiple hospitals’ datasets are processed separately and in parallel. We describe the identification process in two steps. First, we show the search operation over a single phenotype. Then, we extend the algorithm to multiple phenotypes. The details of search over a single phenotype are shown in Algorithm 8. Specifically, given the ciphertext $\hat{c}_{i,j,k}$ of phenotype $k$ of patient $j$ in hospital $i$, we first extract the components $g^{r_{i,j,k}}$, $c_{i,j,k}$, $\bar{c}_{i,j,k}$ from $\hat{c}_{i,j,k}$, denoted as $\hat{c}_{i,j,k,0}$, $\hat{c}_{i,j,k,1}$, and $\hat{c}_{i,j,k,2}$. Based on the input of the query $q_{c,k}$ from client $c$ querying for phenotype $k$, we extract $g^{r_{c,k}},g^{-r_{c,k}\alpha_{c,k}}PK_{c}^{r_{c,k}}$ from $q_{c,k}$, denoted as $q_{c,k,0}$ and $q_{c,k,1}$. With the three pairs ($\hat{c}_{i,j,k,0}$, $q_{c,k,0}$), ($\hat{c}_{j,i,k,1}$, $q_{c,k,1}$), and ($\hat{c}_{i,j,k,0}$ $tk_{i,c,k}$), we compute the bilinear mapping $e$ over each pair and multiply all the results one by one. If the computed result is $1$, the current phenotype matches the query, otherwise, it does not match. The correctness of the algorithm is shown in Eq. 1.

To support a query that contains multiple phenotypes, we extend Algorithm 8 to Algorithm 9. In detail, we first initialize two lists $\Upsilon_{\textit{case}}$ and $\Upsilon_{\textit{control}}$. Then, for each patient with pseudonym $p_{i,j}$ in hospital $i$’s encrypted phenotype dataset $\textit{Dict}_{i}^{P}$, the corresponding encrypted phenotype data $C_{i,j}$ is read. Given the encrypted phenotype data $C_{i,j}$, query $q_{c}$, and transform key ($tk_{i,c,1}$ , $\cdots$, $tk_{i,c,n}$), the per-hospital components of the given data are extracted and passed as the input to the SinglePhenotypeSearch algorithm. For example, both the first element of phenotype data query and transform key are extracted, and then input into the SinglePhenotypeSearch algorithm. If a patient contains all the phenotype data inside a query, the patient’s pseudonym $p_{i,j}$ is added to the case group $\Upsilon_{\textit{case}}$. If a patient does not match query phenotypes, its pseudonym is added to the control group $\Upsilon_{\textit{control}}$. This process is executed until the size of both case and control groups reaches $N$ or until all the data is processed.

Here, we briefly discuss how our scheme can compute GWAS (or other statistics) over identified patients in centralized and decentralized approaches. In a centralized setting, the patient genomic data is also stored at the CSP, and the genomic data of each patient can be encrypted using multi-key fully homomorphic encryption mechanism (e.g., (chen2019efficient, )) for storage at the CSP. Then, after identifying the case and control groups (as in Section 5.8), the CSP can directly execute the GWAS algorithm over the identified patient data using the homomorphic properties of multi-key fully homomorphic encryption mechanism. In a decentralized setting, the patient genomic data is not stored at the CSP. In this case, the CSP can return the identified patients to the client. Based on the identified patients, the client can send requests to all the involved hospitals to get access to their data for computing GWAS in a distributed way (raisaro2018m, ; froelicher2021truly, ).

Here, we show how the proposed scheme supports efficient update of patient phenotype data stored at the CSP. Assume the hospital $i$ wants to update phenotype $k$ of patient $j$. Given the patient pseudonym $p_{i,j}$ and the phenotype ($\textit{P.name}_{k},\textit{P.val}_{k}$), the phenotype encryption algorithm (in Section 5.5) is called to encrypt the phenotype. Once the encryption is completed, the vector of the update query is constructed by inserting the ciphertext at the position where $\textit{P.name}_{k}$ is located in $\mathbf{A}$ and setting the remaining values to $0$. Additionally, the command “update” is added to the query. The update query is sent to the CSP. Upon receiving the update query, the CSP first identifies the entry of the patient $p_{i,j}$, then identifies the location corresponding to the non-zero element inside the vector of the update query, and finally replaces the old cipher with the new cipher from the update query. To insert a new phenotype or to delete an existing phenotype from a patient record, the proposed update algorithm can also be used by directly appending or removing a record from stored ciphertext.

Phenotype data is encrypted and stored at the CSP. This allows the CSP to analyze the stored ciphertext. The encrypted phenotype data can be split into two parts (as in Section 5.5.1). The first part of the encrypted phenotype data is constructed in two steps. Hospital first computes the hash of the phenotype attribute and value. Then, hospital randomly selects a number to mask above hash result and raised the result to the power of a group element. The privacy of this part relies on the hardness of discrete logarithm problem, one-wayness of the hash function, and randomness of the selected number. The second part of the encrypted phenotype data results from directly encrypting phenotype attribute and value. Hospital uses its secret key and invokes symmetric encryption algorithm (e.g., AES) to encrypt the concatenation of phenotype attribute and value. The privacy of the second part relies on the robustness of the utilized symmetric encryption algorithm (e.g., AES). From the above description, we can conclude that both parts of the encrypted phenotype are semantically secure. Thus, the CSP is unable to learn significant information from the ciphertext analysis.

The input of the query includes a set of phenotypes. Each phenotype includes a pair of phenotype attribute and value, which is first hashed and the hash result is lifted as a power of a group element (as in Section 5.7). Additionally, a random mask is selected to hide this result, which enables the encrypted query to be semantically secure. Due to the semantic security of the query, the CSP is unable to learn the query content from the query analysis.

Since the ciphertext of phenotype genotype data is stored at the CSP, the CSP is responsible for conducting search over the ciphertext. For the search operation, the CSP applies the query to search over the ciphertext of phenotype data. If a phenotype is included in the query, the corresponding search result is $1$, otherwise, it is $0$. Through the execution of the search process, the CSP can learn the number of matching phenotypes of each patient. However, for each matching phenotype, its value can either be 0 or 1, and the CSP cannot distinguish between the two. Thus, the CSP cannot learn any information about the query and ciphertext from the search operation.

Access control is designed through the transform key (as discussed in Section 5.6). A client selects random numbers $r_{c,k}$ ($1\leq k\leq n$) and sends them to the target hospital. The hospital generates the transform key ($tk_{i,j,k}=g^{\frac{-r_{c,k}(SK_{i}-c)}{SK_{i}-\alpha_{c,k}}}$) by lifting these numbers into the power of a group element. Due to the randomness of $r_{c,k}$ and the hardness of the discrete logarithm problem, the CSP is unable to extract any information from the transform key. Analyzing the search operation, the output of using incorrect transform key is $0$, which does not disclose any information to the CSP, as described in Section 6.3. Therefore, the proposed authorization scheme is robust against the unauthorized access.

Each hospital independently encrypts its phenotype data and genotype data with its own secret key. Even if several hospitals collude with each other, they cannot get any advantage to infer another hospital’s data.

If one or more hospitals collude with the CSP, the CSP cannot obtain any advantage to infer the remaining hospitals’ data since each hospital’s data is encrypted independently. However, as we clarified in Section 4.4, we do not consider following case. For instance, if the search (at the CSP) includes two hospitals and if one of these hospital collude with the CSP, the CSP can learn which patients of the other (victim) hospital has the considered phenotype as a result of the search operation (but not the genomic data of the identified patients). To provide the common search functionality, this attack is unavoidable, and hence we do not consider it in this work.

In the following, we provide a formal privacy analysis of the proposed scheme. Following previous works (chen2019efficient, ), the allowed leakage includes (i) size pattern and (ii) access pattern. The size pattern discloses the size of the ciphertext, while the access pattern reveals the access frequency of matching patient records. The allowed leakage is not considered violation of our privacy goal. The privacy of the proposed scheme is based on the hardness of discrete logarithm problem, the randomness of selected random mask, and the robustness of applied symmetric encryption (e.g., AES).

The privacy of the proposed scheme can be divided into two elements: phenotype data privacy, and query privacy. The privacy of phenotype data can be further divided into two parts. One part is encrypted by using symmetric encryption algorithm (the third element in a ciphertext, detailed in Section 5.5.1) and the other part is not (the first and second elements in a ciphertext, detailed in Section 5.5.1). Due to the robustness of symmetric encryption algorithm (e.g., AES), the part with the symmetric encryption is also semantically secure. The other part is first protected by a hash function and then masked with a random value. Both the hash result and random mask are put into the power of a group element. Due to the random mask and the hardness of discrete logarithm problem, the ciphertext is semantically secure in the presence of chosen plaintext attack. The query privacy is achieved similarly, relying on the random mask and discrete logarithm problem.

Formally, we define the privacy experiments as follows. Let $\Pi$ be the scheme, the advantage of the adversary is defined as $\text{ADV}_{\mathcal{A}}^{\Pi}(\lambda)=Pr(b^{*}=b)-1/2$, where $b$ and $b^{*}$ are defined below. In the following, we detail the game.

We say the scheme $\Pi$ is privacy-preserving if the advantage of the adversary is negligible, i.e, $ADV_{\mathcal{A}}^{\Pi}\leq negl(\lambda)$, where $negl(\lambda)$ is a negligible function in $\lambda$.

From above defined privacy game, the adversary $\mathcal{A}$ is only allowed to learn the information from Phase 1 and Phase 2. The difference of Phase 2 from Phase 1 is that $\mathcal{A}$ holds the challenged ciphertext and is allowed to ask a query request. Thus, we only need to prove that what the adversary $\mathcal{A}$ can learn from ciphertext request and query request is negligible as follows.

Phenotype data encryption request::

$\mathcal{A}$ submits the dataset $DB$ of phenotype data to ask for encryption from hospital $i$.

If the PhenotypeEnc algorithm is semantically secure, $\mathcal{A}$ is unable to distinguish ciphertext from a random string. The ciphertext of each pair of phenotype attribute and value includes three components. The first component $g^{r_{i,j,k}}$ is randomly selected from $\mathbb{Z}_{p}$, which does not reveal any information. The second component $c_{i,j,k}$ is $g^{-r_{i,j,k}/(SK_{i}-\alpha_{i,j,k})}$. Due to the hardness of discrete logarithm problem, $\mathcal{A}$ is unable to extract the power of a group element. Similarly, $\mathcal{A}$ is unable to distinguish the second component from a random element in $\mathbb{G}$. The third component is encrypted by using a symmetric encryption algorithm (e.g., AES), which is semantically secure.

Therefore, the ciphertext obtained through Encrypt algorithm is semantically secure.

Query request::

First, the transform key is indistinguishable from a random element of group $G$. Second, for each pair of phenotype attribute and value, the query is $(g^{r_{c,k}}$, $g^{-r_{c,k}\alpha_{c,k}}PK_{c}^{r_{c,k}})$, where $PK_{c}$ is an element from ${G}$. Based on the hardness of discrete logarithm problem and the randomness of $r_{c,k}$, the query is indistinguishable from two random elements from ${G}$. Third, given the query and transform key, the adversary $\mathcal{A}$ is capable to run search operation over the ciphertext of phenotype data. Furthermore, $\mathcal{A}$ is also capable to run analysis algorithms on ciphertext of genotype data. However, due to the constraint of issuing client authorization, two datasets should output the same search result. Thus, $\mathcal{A}$ cannot learn any significant information via executing search operation.

Based on above analysis, we can conclude $ADV^{\Pi}_{\mathcal{A}}(\lambda)$ is negligible and the proposed scheme is privacy-preserving.

We use the rsnps tool (rsnps, ) to obtain all the raw patient files from the publicly available OpenSNP dataset (OpenSNP, ). Then, we converted the raw patient files into the VCF format using an open source software named personal-genome-analysis (oga, ). Eventually, we ended up with 1052 valid VCF files. For the phenotype data, we also used the OpenSNP dataset. In total, we collected 1052 records and extracted 1052 phenotype attributes.

In this section, we first show the efficiency and scalability of the phenotype and genotype data encryption algorithms. After that, we present the scalability and efficiency of client authorization and query generation.