An Efficient Searchable Encryption Against Keyword Guessing Attacks for Sharable Electronic Medical Records in Cloud-based System

Abstract

Preserving the privacy of electronic medical records (EMRs) is extremely important especially when medical systems adopt cloud services to store patients’ electronic medical records. Considering both the privacy and the utilization of EMRs, some medical systems apply searchable encryption to encrypt EMRs and enable authorized users to search over these encrypted records. Since individuals would like to share their EMRs with multiple persons, how to design an efficient searchable encryption for sharable EMRs is still a very challenge work. In this paper, we propose a cost-efficient secure channel free searchable encryption (SCF-PEKS) scheme for sharable EMRs. Comparing with existing SCF-PEKS solutions, our scheme reduces the storage overhead and achieves better computation performance. Moreover, our scheme can guard against keyword guessing attack, which is neglected by most of the existing schemes. Finally, we implement both our scheme and a latest medical-based scheme to evaluate the performance. The evaluation results show that our scheme performs much better performance than the latest one for sharable EMRs.

Introduction

In recent years, cloud computing has gained increasing attention because it provides a more convenient and cost-efficient solution for users to manage the data [1]. Due to the tremendous benefits of cloud computing, the electronic medical records (EMRs) providers are willing to deploy their EMRs storage and application services into the cloud instead of maintaining a specialized data center [2]. Since EMRs involve lots of information about patients’ privacy, it is important to prevent the contents of EMRs from being revealed to both unauthorized users and the cloud server.

The basic way to protect EMRs from being disclosed to the unauthorized users is user authentication. In current medical information systems, smart card based authentication schemes [3–7] are widely used to verify the correctness of remote users. He et al. proposed an efficient authentication scheme [3] which can be deployed in the mobile cloud environment. Chaturvedi et al. [5] found the security vulnerabilities of previous works, and proposed an improved three-factor remote user authentication scheme. Khan et al. [7] proposed a more cost-efficient scheme which can defend both active attacks and passive attacks. Although the user authentication is a reliable technique to protect EMRs, it is hard for the authentication schemes to keep the cloud server from accessing EMRs.

To prevent the sensitive information of EMRs from being revealed to the cloud server, patients/practitioners are willing to encrypt EMRs [8]. Encrypting EMRs before outsourcing would be a reliable solution for protecting EMRs, but it makes data utilization, such as keyword search, a very challenge task [9]. To solve this problem, Boneh et al. [10] have designed the first public key encryption based searchable encryption (PEKS) to allow users to search over the encrypted data. Hereafter, many follow-up schemes [11–13] have been proposed to enrich the functionalities of the searchable encryption. With PEKS, users can quickly sort out the information of interest from a large amount of data without leaking sensitive information to the cloud server. Recently, some cloud-based EMRs systems [14, 15] have applied PEKS to build a secure storage environment.

All aforementioned PEKS schemes require secure channels to transmit some sensitive information. Otherwise, a potential eavesdropper can easily get the sensitive information and break the system. To solve the secure channel problem, Beak et al. [16] have proposed a novel PEKS scheme, referred to as SCF-PEKS, which guarantees the secure keyword search without secure channels. Following this work, Rhee et al. have designed two SCF-PEKS schemes [17, 18] based on an enhanced security model. To improve efficiency, Gu et al. [19] have proposed a productive solution that requires no pairing operation in the encryption procedure. In addition, Fang et al. [20] proposed a new scheme, whose security does not rely on random oracles. And afterwards, Fang et al. proposed the improved scheme [21] which is secure against keyword guessing attack (IND-KGA). In 2015, Guo et al. [22] proposed an very efficient SCF-PEKS scheme that is practical to deployed in the cloud-based EMRs system.

However, existing SCF-PEKS solutions only consider the scenario with the one-receiver setting. In other words, these solutions assume that there is only one receiver in the system. In reality, one patient/practitioner would like to share her electronic medical record with a wide range of users [14]. For example, a patient may share her electronic medical record with her family, her friends or her practitioner. And, with the consent of the patient, a practitioner may share the electronic medical record with other practitioners to discuss the rehabilitation program. In the existing SCF-PEKS schemes, the EMR owner, referred to as the sender in this paper, has to encrypt each keyword for each receiver. If many receivers are authorized to search over the sender’s EMR involving many keywords, it would incur noticeable overhead in terms of the computation overhead and the storage overhead. For example, if there are fifty authorized receivers can search over the sender’s EMR which contains fifty keywords, the sender has to generate 2,500 ciphertexts corresponding for these keywords. Even worse, the sender has to outsource these ciphertexts to the cloud server, which will increase the communication overhead. On the view point of the EMRs provider, more storage space should be rented from the cloud with the increasing consumption of the storage. Hence, a more cost-efficient solution in the multi-receiver setting is required.

In this paper, we propose a novel SCF-PEKS scheme, aiming to reduce both the computation overhead and the storage overhead for sharable EMRs in the multi-receiver setting. In our scheme, the sender only needs to generate one ciphertext for each keyword, no matter how many receivers our scheme has. In addition, our scheme guarantees the IND-KGA secure as the scheme in [22]. Our contributions can be summarized as follow: First, our SCF-PEKS scheme is a low overhead solution which is practical in the cloud. Comparing with existing works, the sender undertakes less computation tasks and costs less storage space in our scheme. Second, our scheme is IND-KGA secure that can guard against the keyword guessing attack. Moreover, our scheme requires no secure channel, meaning that no secret information will be transmitted on channels. Finally, we present a comprehensive comparison between our scheme and some other SCF-PEKS schemes. Our comparison consists of both the theoretical analysis and the performance evaluation. Both of them prove that our scheme is a better solution in the cloud.

The remainder of the paper is organized as follows. In “Statement”, we present the system model, the security model, the design objectives and some algorithm definitions. The cryptographic primitives and assumptions are introduced in “Preliminaries”. “section*.19Details of our proposed section*.19scheme” gives the details of our proposed scheme, followed by the security analysis and theoretical comparison in “Analysis”. The performance is evaluated in “section*.32Performance section*.32evaluation”. Finally, we conclude the paper in “section*.33Conclusion”.

Statement

System model

As illustrated in Fig. 1, there are three entities involved in our system.

Fig. 1

System model

Sender

The sender is an entity who has one EMR which will be shared with some authorized users. To protect the privacy of the EMR, the sender should encrypt it before outsourcing. In addition, to enable authorized users to efficiently search over the encrypted EMR, the sender should generate a secure index involving some keywords for the EMR. After that, the sender outsources the encrypted EMR together with the corresponding index to the cloud server. To delegate the search ability to authorized users, the sender computes a re-encryption key for each authorized user, and sends these keys to the cloud server. The number of the keys depends on the number of authorized users.

Receivers

In our scheme, receivers are the authorized users who can perform the keyword search on the sender’s encrypted EMR. Each receiver requests the search by generating a trapdoor associated with a certain query keyword, and obtains the sender’s encrypted EMR from the cloud server if the query keyword is involved in the index.

The cloud server

The cloud server is an entity which stores the sender’s EMR, and performs the search operation after receiving the trapdoor from one receiver.

Security model

In this paper, we assume that there is no secure channel in the EMRs system, meaning that each entity is forbidden to transmit any secret information, such as secret keys and trapdoors, via transmission channels. Otherwise, a potential eavesdropper will get the secret information, and try to break the system. Similar to existing work, we consider a semi-trust cloud server, which honestly follows our proposed scheme, but curiously learns the underlying meanings of the sender’s EMR. In other words, the cloud server will try to learn the content of the sender’s EMR by decrypting it. In addition, the cloud server is also interested in retrieving the keywords from the index and the trapdoors.

Design goal

Our goals consists of the following aspects:

• Security. First, the confidentiality of the sender’s EMR should be guaranteed in our scheme. The cloud server cannot retrieve any EMR from the encrypted data. Second, the cloud server cannot learn any keyword from neither the index nor the trapdoors. Third, the trapdoors should not be linkable, which means the trapdoors should be totally different even if they contain the same keyword. In this paper, our scheme should also guard against the keyword guessing attack.

• Low Storage Overhead. As the main purpose in this paper, our scheme should require less storage overhead than other SCF-PEKS solutions. Since the data will be outsourced from the sender to the cloud server, reducing the storage overhead is equivalent to reducing the communication overhead.

• Low Computation Overhead. The sender should cost acceptable computational resources on generating the index for the EMR and computing the re-encryption key for each receiver. In addition, our scheme should achieve better search efficiency when receivers request the keyword query.

Algorithm definition

We define some algorithms used in our scheme as follows. The detail of each algorithm will be introduced in “Details of our proposed scheme”.

• GlobalSetup(λ): The algorithm takes the security parameters λ as input, and outputs the global parameter $\mathcal {G}\mathcal {P}$.

• KeyGen($\mathcal {G}\mathcal {P}$): Given the global parameter $\mathcal {G}\mathcal {P}$, the algorithm outputs a public/secret key pair (p k,s k).

• Enc($\mathcal {G}\mathcal {P},\mathcal {M},sk_{S}$): Given the global parameter $\mathcal {G}\mathcal {P}$, an electronic medical record M and a sender’s secret key s k _S , the algorithm encrypts the record and outputs the corresponding ciphertext.

• IndexGen($\mathcal {G}\mathcal {P},sk_{S},\mathcal {W}$): The algorithm inputs the global parameter $\mathcal {G}\mathcal {P}$, a sender’s secret key s k _S and a keyword set $\mathcal {W}$, outputs the secure index.

• ReKeyGen($\mathcal {G}\mathcal {P},sk_{S},pk_{R}$): Given the global parameter $\mathcal {G}\mathcal {P}$, a sender’s secret key s k _S and a receiver’s public key p k _R , the algorithm outputs a re-encryption key.

• Trapdoor($\mathcal {G}\mathcal {P},sk_{R},w^{\prime }$): Given the global parameter $\mathcal {G}\mathcal {P}$, a receiver’s secret key s k _R and a query keyword $w^{\prime }$, the algorithm outputs the trapdoor.

• Search($\mathcal {G}\mathcal {P},\mathcal {I},\mathcal {T}, rk$): Given the global parameter $\mathcal {G}\mathcal {P}$, the index $\mathcal {I}$, the trapdoor $\mathcal {T}$ and a re-encryption key rk, the algorithm outputs 1 if $w=w^{\prime }$, otherwise outputs 0. Noting that keyword w is involved in $\mathcal {I}$, and query keyword $w^{\prime }$ is involved in $\mathcal {T}$.

• Dec($\mathcal {G}\mathcal {P},\mathcal {C},sk_{R},rk$): Given the global parameter $\mathcal {G}\mathcal {P}$, a ciphertext $\mathcal {C}$, a receiver’s secret key s k _R , and a re-encryption key rk, the algorithm outputs the record if each input parameter is correct.

Preliminaries

Bilinear map

Let $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$ be two cyclic groups of a large prime p. Let g be a generator of $\mathbb {G}_{1}$. A bilinear map can be defined as $\hat {e}:\mathbb {G}_{1} \times \mathbb {G}_{1} \to \mathbb {G}_{2}$ if following three conditions hold. 1) Bilinear: for any $a,b\in \mathbb {G}_{1}$, $\hat {e}(g^{a},g^{b})=\hat {e}(g,g)^{ab}$. 2) Non-degeneracy: $\hat {e}(g,g)\neq 1$. 3) Computability: Given $u,v\in \mathbb {G}_{1}$, $\hat {e}$ can be efficiently computed.

Assumptions

Let $\mathbb {G}$ be a cyclic group of a large prime p with a generator of g. The following assumptions hold in our scheme.

Divisible Decision Diffie-Hellman (DDDH) assumption [23]:

Given (g,g ^a,g ^b,r) where a,b,r are randomly chosen in $\mathbb {Z}_{p}$, we define the advantage function of an adversary $\mathcal {A}$ as:

$$\begin{array}{@{}rcl@{}} \textsf{Adv}_{\mathbb{G}_{1},\mathcal{A}}^{DDDH}(\lambda) = |\textsf{Pr}[\mathcal{A}(g,g^{a},g^{b},g^{a/b})=1]\\ - \textsf{Pr}[\mathcal{A}(g,g^{a},g^{b},g^{r})=1]| \end{array} $$

where, λ is the security parameter. We say that DDDH assumption holds if $\textsf {Adv}_{\mathbb {G}_{1},\mathcal {A}}^{DDDH}$ is negligible for $\mathcal {A}$.

Divisible Computation Diffie-Hellman (DCDH) Assumption [23]:

Given (g,g ^a,g ^b) where a,b are randomly chosen in $\mathbb {Z}_{p}$, the advantage for an adversary $\mathcal {A}$ to computer g ^a/b is negligible.

Inverse Computational Diffie-Hellman (InvCDH) assumption [23]:

Given (g,g ^a) where a are randomly chosen in $\mathbb {Z}_{p}$, the advantage for an adversary $\mathcal {A}$ to computer g ^1/a is negligible.

SCF-PEKS secure against Keyword Guessing Attack (IND-KGA)

In this subsection, we review the definition of SCF-PEKS against keyword guessing attack (IND-KGA) [21]. We first review the IND-KGA game. Let $\mathcal {A}$ be an outside adversary who makes the keyword guessing attack, and $\mathcal {B}$ be a challenger. The security game is defined as follows.

• Setup: Both the algorithm GlobalSetup(λ) and the algorithm KeyGen($\mathcal {G}\mathcal {P}$) are executed by $\mathcal {B}$. Then the generated $\mathcal {G}\mathcal {P}$ and p k _R are given to $\mathcal {A}$.

• Query 1: $\mathcal {A}$ asks $\mathcal {B}$ for the trapdoor for any query keyword from the keyword space. $\mathcal {B}$ responds the trapdoor $\mathcal {T}=$ Trapdoor($\mathcal {G}\mathcal {P},sk_{R},w$) to $\mathcal {A}$.

• Challenge: Once Query 1 is over, $\mathcal {A}$ outputs two query keywords (w ₀,w ₁), and sends these two keywords to $\mathcal {B}$. Noting that neither w ₀ nor w ₁ is queried in Query 1. Upon receiving the keywords, $\mathcal {B}$ chooses a random value γ ∈ {0, 1}, creates a challenge Trapdoor($\mathcal {G}\mathcal {P},sk_{R},w_{\gamma }$), and sends it to $\mathcal {A}$.

• Query 2: $\mathcal {A}$ continues to request a number of trapdoors as in Query 1. It is worth noting that $\mathcal {A}$ cannot query w ₀,w ₁.

• Guess: $\mathcal {A}$ outputs the guess $\gamma ^{\prime }$, and wins the game if $\gamma ^{\prime } = \gamma$.

The advantage for $\mathcal {A}$ to win IND-KGA game is

$$ \textsf{Adv}_{\mathcal{A}}^{IND-KGA}(\lambda) = |\textsf{Pr}[(\gamma^{\prime} = \gamma)]-1/2|. $$

(1)

The scheme is said to be IND-KGA secure if the advantage $\textsf {Adv}_{\mathcal {A}}^{IND-KGA}(\lambda )$ is negligible.

Details of our proposed scheme

In this section, we present the details of our proposed scheme. Each entity in our scheme invokes at least one of the algorithm mentioned in “Algorithm definition”. Roughly, our scheme can be divided into four main stages: Initialization, Data Processing, Search and Record Retrieval.

Initialization

The cloud server runs GlobalSetup(λ) to generate the global parameter $\mathcal {G}\mathcal {P}$, where λ is the security parameter. Specifically, the cloud server takes λ to generate two cyclic groups $\mathbb {G}_{1}$ and $\mathbb {G}_{2}$ with the same prime order p, having g as a generator of $\mathbb {G}_{1}$. Then the cloud server initializes a bilinear map $\hat {e}:\mathbb {G}_{1} \times \mathbb {G}_{1} \to \mathbb {G}_{2}$, and chooses a hash function $H:\{0,1\}^{*}\to \mathbb {Z}_{p}$. In addition the cloud server selects a random value s k _C from $\mathbb {Z}_{p}$ as the secret key, and computes the corresponding public key $pk_{C} = g^{sk_{C}}$. Thus, the global parameter can be denoted as $\mathcal {G}\mathcal {P} = \{\mathbb {G}_{1},\mathbb {G}_{2},g,p,\hat {e},H, pk_{C}\}$.

After that, the sender runs KeyGen($\mathcal {G}\mathcal {P}$) to generate the public/secret pair. More precisely, the sender randomly chooses a secret value s k _S from $\mathbb {Z}_{p}$ as the secret key. Then the sender computes $pk_{S} = g^{1/sk_{S}}$. Similarly, each receiver $R_{i}\in \mathcal {R}$, where $\mathcal {R}$ is the receiver set, can generate his secret key $sk_{R_{i}}\in \mathbb {Z}_{p}$ and public key $pk_{R_{i}} = g^{1/sk_{R_{i}}}$, respectively.

Data processing

In this stage, the sender prepares the necessary data which will be outsourced to the cloud server, including a secure index, the encrypted EMR, and a re-encryption key set. The sender first extracts a keyword set $\mathcal {W}$ from the electronic medical record M. Then the sender runs IndexGen($\mathcal {G}\mathcal {P},sk_{S},\mathcal {W}$) to generate a secure index. Specifically, for each keyword $w\in \mathcal {W}$, the sender computes:

$$ \tau_{w} = {pk_{C}}^{sk_{S}\cdot H(w)}. $$

(2)

Thus, the index can be denoted as $\mathcal {I}=\{\tau _{w}\}_{w\in \mathcal {W}}$.

In order to encrypt the electronic medical record $M\in \mathbb {G}_{2}$, the sender runs Enc($\mathcal {G}\mathcal {P},\mathcal {M},sk_{S}$). More precisely, the sender chooses a random value k from $\mathbb {Z}_{p}$, and computes:

$$ C_{1} = M \oplus \hat{e}(g^{sk_{S}},g^{k}), C_{2} = g^{k}. $$

(3)

The encrypted record is denoted as $\mathcal {C}=\{C_{1},C_{2}\}$.

Besides that, the sender should also generate a re-encryption key $rk_{S\to R_{i}}$ for each receiver $R_{i}\in \mathcal {R}$ by invoking the algorithm:

$$ \text{\textsf{ReKeyGen}}(\mathcal{G}\mathcal{P},sk_{S},pk_{R_{i}}) : rk_{S\to R_{i}} = pk_{R_{i}}^{sk_{S}}. $$

(4)

The re-encryption key set can be denoted as $\mathcal {R}\mathcal {K} = \{rk_{S\to R_{i}}\}_{R_{i}\in \mathcal {R}}$.

Finally, the sender outsources the secure index $\mathcal {I}$, the encrypted record $\mathcal {C}$ and the re-encryption key set $\mathcal {R}\mathcal {K}$ to the cloud server.

Search

To search over the encrypted record $\mathcal {C}$, one receiver R _i needs to compute the trapdoor for a query keyword $w^{\prime }$ by invoking Trapdoor($\mathcal {G}\mathcal {P},sk_{R_{i}},w^{\prime }$). More specifically, the receiver chooses a random value $r\in \mathbb {Z}_{p}$, and computes:

$$ T_{1}={pk_{C}}^{r},T_{2}={pk_{C}}^{H(w^{\prime})\cdot r \cdot sk_{R_{i}}}. $$

(5)

Then, the receiver R _i sends the trapdoor $\mathcal {T}_{w^{\prime }} = \{T_{1},T_{2}\}$ to the cloud server.

Upon receiving the trapdoor, the cloud server performs Search($\mathcal {G}\mathcal {P},\mathcal {I},\mathcal {T}_{w^{\prime }}, rk_{S\to R_{i}}$) to check whether the encrypted record $\mathcal {C}$ involves the keyword $w^{\prime }$. Precisely, for each τ _w in $\mathcal {I}$, the cloud server check if

$$ \hat{e}(\tau_{w},T_{1}) = \hat{e}(T_{2},rk_{S\to R_{i}})^{sk_{C}}. $$

(6)

Search outputs 1 only if Eq. 6 holds, which implies $w=w^{\prime }$. In that case, the cloud server sends $\{\mathcal {C},rk_{S\to R_{i}}\}$ back to the receiver R _i . Otherwise, sends ⊥.

Record retrieval

Once the receiver R _i gets $\{\mathcal {C},rk_{S\to R_{i}}\}$ from the cloud server, he decrypts the ciphertext $\mathcal {C}$ to retrieve the record M by invoking Dec($\mathcal {G}\mathcal {P},\mathcal {C},sk_{R},rk_{S\to R_{i}}$). The record can be retrieved as follows:

$$ M = {C_{1}}\oplus {\hat{e}(rk_{S\to R_{i}},C_{2})^{sk_{R_{i}}}}. $$

(7)

Analysis

Correctness

We first show that the correctly generated index can be correctly searched if the receiver R _i generates the correct trapdoor. It is equivalent to proving the correctness of Eq. 6. Assume that there is a keyword $w\in \mathcal {W}$ that satisfies $w=w^{\prime }$, we have:

$$\begin{array}{@{}rcl@{}} \hat{e}(\tau_{w},T_{1})& =& \hat{e}({pk_{C}}^{sk_{S}\cdot H(w)},{pk_{C}}^{r})\\ & =& \hat{e}(g^{H(w)\cdot r \cdot {sk_{C}}}, g^{sk_{S} \cdot {sk_{C}}})\\ & =&\hat{e}(g^{H(w)\cdot r \cdot {sk_{C}}} , g^{\frac{sk_{S}}{sk_{R_{i}}}\cdot sk_{R_{i}}\cdot {sk_{C}}})\\ & =& \hat{e}(g^{H(w)\cdot r \cdot sk_{R_{i}}\cdot {sk_{C}}}, g^{sk_{S}/sk_{R_{i}}\cdot {sk_{C}}})\\ & =& \hat{e}({pk_{C}}^{H(w^{\prime})\cdot r \cdot sk_{R_{i}}},pk_{R_{i}}^{sk_{S}\cdot {sk_{C}}})\\ & =& \hat{e}(T_{2},rk_{S\to R_{i}}^{sk_{C}}). \end{array} $$

(8)

Then, we show that the receiver R _i can correctly retrieve the record M. It is equivalent to proving the correctness of Eq. 7. We have

$$\begin{array}{@{}rcl@{}} && {C_{1}}\oplus {\hat{e}(rk_{S\to R_{i}},C_{2})^{sk_{R_{i}}}}\\ &= & M \oplus \hat{e}(g^{sk_{S}},g^{k}) \oplus {\hat{e}(g^{sk_{S}/sk_{R_{i}}},g^{k})^{sk_{R_{i}}}}\\ &= & M \oplus \hat{e}(g^{sk_{S}},g^{k}) \oplus \hat{e}(g^{sk_{S}},g^{k}) = M \end{array} $$

(9)

Therefore, the receiver R _i can successfully perform the keyword search on the encrypted record, and decrypt it.

Security analysis

In this subsection, we analyze the security of our proposed scheme. The security of EMRs and the security of the corresponding keywords are discussed in Theorem 1 and Theorem 2, respectively. We first prove that the cloud server cannot retrieve plaintext of any EMR if both DCDH assumption and InvCDH assumption hold. Then, by constructing two equivalent games, we prove that the keywords in our scheme are secure against keyword guessing attacks in standard model.

Theorem 1

The electronic medical record M is secure if both DCDH assumption and InvCDH assumption hold in $\mathbb {G}_{1}$.

Proof

As show in Eq. 3, the probability for an adversary $\mathcal {A}$ to decrypt the record is equivalent to computing $g^{sk_{S}}$. According to our scheme, the cloud server could obtain $g^{1/sk_{S}},g^{sk_{S}/sk_{R_{i}}},g^{1/sk_{R_{i}}}$. □

Case 1

As soon as DCDH assumption holds in $\mathbb {G}_{1}$, it is hard for the cloud server to compute $g^{sk_{S}}$ from $g^{1/sk_{S}}$ with non-negligible probability.

Case 2

Denote $sk_{S}/sk_{R_{i}}$ as a, $g^{sk_{R_{i}}}$ as b, thus s k _S can be denoted as a/b. According to InvCDH assumption, it is hard for an adversary to compute $g^{a/b}$ from $(g,g^{a},g^{b})$ with non-negligible probability. Equivalently, the cloud serve cannot retrieve $g^{sk_{S}}$ from $(g,g^{sk_{S}/sk_{R_{i}}},g^{1/sk_{R_{i}}})$ with non-negligible probability.

In conclusion, the cloud server cannot retrieve the record M from the ciphertext $\mathcal {C}$ with non-negligible probability as soon as both DCDH assumption and InvCDH assumption hold in $\mathbb {G}_{1}$.

Theorem 2

Our scheme is IND-KGA secure in the standard model, if DDDH assumption holds in $\mathbb {G}_{1}$.

Proof

Since s k _S is not owned by the cloud server, the cloud server cannot retrieve the keywords from the index. Therefore, this theorem is equivalent to proving that the keywords are secure in our scheme.

Suppose there exists a polynomial-time adversary $\mathcal {A}$ in IND-KGA game. We build a simulator $\mathcal {B}$ that can play a DDDH game. Denote p k _C as g ₁. $\mathcal {B}$ inputs a DDDH instance ($A={g_{1}^{a}},B={g_{1}^{b}},V$), and tries to distinguish $V=g_{1}^{a/b}$ from a random element in $\mathbb {G}_{1}$. We construct the following games to prove the security.

Game 1.

Let $V=g_{1}^{a/b}$. Game 1 is essentially the same as IND-KGA game except for the following changes:

• Setup: $\mathcal {B}$ chooses a random value $l\in \mathbb {Z}_{p}$, and sets the receiver R _i ’s public key as $pk_{R_{i}} = B^{l} = g_{1}^{b\cdot l}$. Naturally, the receiver R _i ’s secret key is $sk_{R_{i}} = \frac {1}{b\cdot l\cdot sk_{C}}$. $\mathcal {B}$ send $pk_{R_{i}}$ to $\mathcal {A}$.

• Challenge: Upon receiving keywords (w ₀,w ₁), $\mathcal {B}$ picks a random bit γ ∈ {0, 1}. Then $\mathcal {B}$ sets $T_{1}=A^{l}$ and $T_{2} = V^{H(w_{\gamma })}$, respectively. Finally, $\mathcal {B}$ sends the trapdoor $\mathcal {T}_{w_{\gamma }} = \{T_{1},T_{2}\}$ to $\mathcal {A}$.

□

Game 1 is equivalent to IND-KGA game only if the generated trapdoor is valid. Let $r^{\prime } = a\cdot l$, we can have:

$$\begin{array}{@{}rcl@{}} T_{1}&=& A^{l} = g_{1}^{a\cdot l} = g_{1}^{r^{\prime}} = pk_{C}^{r^{\prime}}, \\ T_{2}&=& V^{H(w_{\gamma})}=g_{1}^{\frac{a}{b}H(w_{\gamma})} = g_{1}^{\frac{a\cdot l}{b\cdot l}H(w_{\gamma})}\\ & =& g_{1}^{H(w_{\gamma}) \cdot r^{\prime} \cdot sk_{R_{i}}}= pk_{C}^{H(w_{\gamma}) \cdot r^{\prime} \cdot sk_{R_{i}}}. \end{array} $$

(10)

Thus, Eq. 10 is equivalent to Eq. 6. For $\mathcal {A}$, Game 1 is equivalent to IND-KGA game. Therefore, the advantage for $\mathcal {A}$ to win Game 1 is:

$$ \textsf{Adv}_{\mathcal{A}}^{Game 1}(\lambda) = \textsf{Adv}_{\mathcal{A}}^{IND-KGA}(\lambda) $$

(11)

Game 2.

Game 2 is essentially the same as Game 1 except that the value $V=g_{1}^{a/b}$ is replaced by a random value $V\in \mathbb {G}_{1}$. Since V is uniform in $\mathbb {G}_{1}$, we have:

$$ \textsf{Pr}[(\gamma^{\prime} = \gamma)] = \frac{1}{2}. $$

(12)

Thus, the advantage for $\mathcal {A}$ to win Game 2 is:

$$ \textsf{Adv}_{\mathcal{A}}^{Game 2}(\lambda) = |\textsf{Pr}[(\gamma^{\prime} = \gamma)] -\frac{1}{2}| < \epsilon^{\prime}, $$

(13)

where $\epsilon ^{\prime }$ is a negligible value.

Since the probability for $\mathcal {A}$ to distinguish Game 1 and Game 2 is equal to the probability to distinguish g ^a/b and random value, we can have:

$$\begin{array}{@{}rcl@{}} \textsf{Adv}_{\mathcal{A}}^{IND-KGA}(\lambda)&= & \textsf{Adv}_{\mathcal{A}}^{Game 1}(\lambda)\\ &\leqslant & \textsf{Adv}_{\mathcal{A}}^{Game 2}(\lambda) + \textsf{Adv}_{\mathbb{G}_{1},\mathcal{A}}^{DDDH}(\lambda)\\ &= & \epsilon^{\prime} + \epsilon = \epsilon, \end{array} $$

(14)

where 𝜖 is negligible if DDDH assumption holds in $\mathbb {G}_{1}$. Hence, the advantage for $\mathcal {A}$ to win IND-KGA game is negligible.

Theoretical comparison

Suppose there are n receivers who are authorized to search on the sender’s EMR which involves m keywords. Let P denote an pairing operation, E denote an exponentiation operation. Let $|\mathbb {Z}_{p}|,|\mathbb {G}_{1}|,|\mathbb {G}_{2}|$ denote the length of the element in $\mathbb {Z}_{p},\mathbb {G}_{1}$ and $\mathbb {G}_{2}$, respectively. We compare our scheme with Rhee et al.’s scheme [18], Fang et al.’s scheme [21] and Guo et al.’s scheme [22], and show the comparison results in Table 1. Noting that both the scheme [21] and the scheme [22] are optimized in the multi-receiver setting before the comparison. To reduce as much computation overhead as possible, some parameters will be calculated only once in both [21] and [22]. For example, in the scheme [21], the ciphertext C ₁ and C ₅ will only be calculated once even though the sender invokes PEKS several times.

Table 1 Comparison among Rhee et al. [18], Fang et al. [21], Guo et al. [22] and our scheme

Computation Overhead

In our scheme, the computational cost for generating the index is m E. Besides, our scheme needs additional n exponentiation operations to generate the re-encryption key set. Comparing with the other three schemes, it is obvious that the sender in our scheme costs less computational resources in the multi-receiver setting. Since an pairing operation P consumes more computation resource than an exponentiation operation E in general, the scheme [18] performs a little better on Search than ours. But our scheme needs less m P operations on IndexGen than the scheme [18]. Overall, the performance in our scheme is more efficient than the scheme [18]. Hence, our scheme offers the best computation efficiency when multiple receivers are authorized to search over the sender’s EMR in computation comparison.

Storage Overhead

On the view point of the sender, the main additional storage overhead is the index in both [21] and[22]. Unlike these two schemes, the sender needs extra storage overhead to store the re-encryption set in our scheme. As illustrated in Table 1, the total additional storage overhead in our scheme is (m + n)$|\mathbb {G}_{1}|$, which is much lower than the schemes in [21] and [22].

Performance evaluation

To show the performance more intuitively, we implement both our scheme and Guo et al.’s scheme [22] in C language using Pairing-Based Cryptographic (PBC) library [24], and compare these two schemes on a computer running Ubuntu Linux with 3.4 GHz Intel Core i3 processor and 4 Gigabyte memory. We adopt the type A elliptic curve with 160-bit group order and 1024-bit field order to build the cryptographic environment. The experiment focuses on evaluating the computation overhead and the storage overhead. Each experimental result is the average value from 10 runs.

Table 2 illustrates the computational performance of both Guo et al.’s scheme and ours. In Table 2(a), we fix the number of receivers as fifty, and conclude that the time for generating the index is linear to the number of keywords. According to Table 2(b), we can get that the number of receivers would influence the time for generating the index. Both Table 2(a) and Table 2(b) demonstrate that our scheme consumes much less computational resources on generating the index than the scheme in [22].

Table 2 Index Generation Time Comparison

Figure 2 shows that the time for search is linearly increasing with the number of keywords in the index. It is worth noting that we consider the worst case, in which each search operation should go through the whole index. Likewise, Fig. 2 proves that our scheme presents the better computational performance on the search.

Fig. 2

The search time for the different number of keywords

Figure 3 illustrates the storage overhead of the index in both [22] and this paper. In our scheme, the storage overhead of the index consists of both the index itself and the re-encryption key set. In our implementation, both $|\mathbb {G}_{1}|$ and $|\mathbb {G}_{2}|$ are 2048-bit length. And the security parameter λ appeared in [22] is set as 2048. As showed in Fig. 3, both the number of keywords and the number of receivers will affect the storage overhead of the index. Apparently, the storage overhead of the index is significantly reduced in our scheme.

Fig. 3

Storage overhead

Conclusion

In this paper, we proposed a low overhead SCF-PEKS scheme which is suitable to be deployed in a medical cloud environment. Our scheme is a practical solution in the multi-receiver setting. By using our scheme, the sender can efficiently delegate the search ability to receivers with both low computation overhead and low storage overhead. Each authorized receiver can easily search over the encrypted EMRs, and retrieve the matched records. Our correctness analysis and security analysis demonstrated that the proposed scheme is soundness and secure against the IND-KGA attack. The comprehensive comparisons, including theoretical comparison and performance evaluation, showed that our scheme can achieve better efficiency in terms of the computation overhead and the storage overhead compared with existing ones. Since our scheme is a more cost-efficient solution, it will be more competitive to be deployed in the cloud. For the future work, we will investigate on enriching the functionalities of the search based on our scheme, such as the fuzzy keyword search and the ranked keyword search.