Privacy Preserving Index for Encrypted Electronic Medical Records

Abstract

With the development of electronic systems, privacy has become an important security issue in real-life. In medical systems, privacy of patients’ electronic medical records (EMRs) must be fully protected. However, to combine the efficiency and privacy, privacy preserving index is introduced to preserve the privacy, where the EMR can be efficiently accessed by this patient or specific doctor. In the literature, Goh first proposed a secure index scheme with keyword search over encrypted data based on a well-known primitive, Bloom filter. In this paper, we propose a new privacy preserving index scheme, called position index (P-index), with keyword search over the encrypted data. The proposed index scheme is semantically secure against the adaptive chosen keyword attack, and it also provides flexible space, lower false positive rate, and search privacy. Moreover, it does not rely on pairing, a complicate computation, and thus can search over encrypted electronic medical records from the cloud server efficiently.

Introduction

The security and privacy of electronic medical records (EMRs) have been drawn attention, because now medical systems usually adopt cloud services. Users can acquire services or aids from clouds. However, privacy protection of personal sensitive information is a major security issue during communications, and EMRs as well. The private data in the open network server should be accessed by the owner at anytime. Furthermore, we would like that attackers cannot obtain any useful information from private data.

There are many ways to protect privacy of data, for instance, depending on encryption algorithm. A user stores encrypted data in the open server, and retrieves all the encrypted data through network when he needs. Whenever the user needs a segment of those data, he retrieves all the encrypted data, and then picks needed ones. This method is secure against the hostile server or attackers, but it is quite inefficient. The large amount of data transmission is not afforded, since the user might owns weak devices in cloud computing. A new method to get rid off unnecessary data transformation is essential. Keyword search over encrypted data is presented to overcome this problem, which is also referred to as Keyword-Searchable Encryption.

Nowadays, the file storage system is a common application as well as a cloud storage; for example, iCloud and Dropbox. For different purposes, multiform secure cloud services have been proposed [1–4]. However, for keyword-searchable encryption, the file server is defined as an honest-but-curious server [5–9], which means the server responds any users’ request correctly but it wants to infer the content of those data. Keyword-searchable encryption is appropriate in this system. The user is able to encrypt his data using any encryption such as DES or AES, and then attaches the searchable ciphertext which is generated by using keyword-searchable encryption. When the user needs his data, he only computes the trapdoor of keywords and send it to the server. Finally, the server tests and looks for searchable ciphertexts which correspond to the trapdoor, but it can not get any significant information from the results of search or trapdoor.

Related work

The first notion, proposed by Song et al. [9], allows the user to set up individual trapdoor to search encrypted data. Song et al.’s scheme is based on the hash function, and they presented the security requirements. Since then, lots of searchable encryption schemes are more powerful using fields as tags to achieve multi-keywords search [6–8] and improve the efficiency. Moreover, searchable public key encryption schemes [10–15] are practically used in the email system. There are plenty of studies have been proposed to discuss security and efficiency [16, 17]. However, most of schemes are based on pairing, a kind of complicated computation. Goh [18] proposed an index called Z-index based on Bloom filter without pairing.

Contributions

In this paper, we propose an efficient secure index scheme to realize the keyword-searchable encryption to support keyword search over encrypted data. Because of pairing-freeness, our scheme is more applicable to cloud storage. We also give the formal security proof to analyze that this scheme is semantically secure against the adaptive chosen keyword attack.

The rest of the paper is organized as follows. Preliminaries about the relevant research, and the assumptions are depicted in section “Preliminaries”. Then, we briefly review Goh’s scheme [18] in section “Review of Goh’s secure index scheme”. The proposed P-index and its security analysis are presented in section “Position index scheme (P-index)”. Finally, we conclude this paper in section “Conclusions”.

Preliminaries

We will briefly present EMRs and the framework and security model of the secure index in section “Electronic medical record (EMR)”, “Framework of keyword-searchable encryption with secure index” and “Security model of secure index” respectively and then the hardness assumption is given in section “Hardness assumption”.

Electronic medical record (EMR)

An electronic medical record is a notion providing a system to manage electronic medical or health information for individual patients [19–21]. The EMR is a digital record that can be shared across different health care settings. With networks, different hospitals can conveniently access the EMRs if needed. In addition, the EMRs are designed instead of the paperwork records. In practice, EHRs include a range of data of patients, including demographics, medical history, medication and allergies, immunization status, laboratory test results, radiology images, vital signs, personal statistics like age and weight, and billing information.

The system is a centralized system and developed to deal with the state of the patient at all times [22]. It eliminates data replication since there is only one modifiable file in the storage server. Due to all the patient information storing in a single file, extracting and accessing medical data are quite effective and efficient for the examination of possible trends and long term changes. The well known standard of EMRs is HL7. For the security purpose, we would like the EMRs are accessed by the eligible doctors or hospitals. Therefore the privacy becomes an important issue in the EMRs [23]. In this paper, we consider this issue to propose a privacy preserving index for EMRs based on keyword-searchable encryption. In the proposed scheme, the eligible party is able to access EMRs securely.

Framework of keyword-searchable encryption with secure index

In a keyword-searchable encryption scheme, an encrypted document with secure index must follow the format: [E _K (M), id, I _id ], where E is a secure symmetric encryption¹, K is the key, M is the plaintext of the document, the identity of document is denoted by id, and I _id is the secure index. Here, M could be the EMR.

Definition 1

A searchable encryption scheme with secure index consists of following polynomial algorithms:

• KeyGen. This algorithm sets the public parameters and the user’s key.

• Trapdoor. This algorithm, run by the user, takes the keyword w and key K as input, then returns the trapdoor T which is used to search.

• BuildIndex. This algorithm, run by the user, takes the keyword w, the identity of the document D _id and key K as input, then returns the secure index I _id .

• SearchIndex. The server performs the algorithm to take the trapdoor T and secure index I _id as input. Finally, it outputs 1 if it finds I _id corresponding to T; otherwise, outputs 0.

Security model of secure index

For proving the security, we have to consider the possible adversary’s behaviors. Usually, we adopt the security game to simulate the adaptive chosen keyword attack [18]. Formally, there are two roles in the game: one is the adversary 𝒜, and the other is challenger 𝒞. 𝒞 must reply 𝒜’s queries, and finally will use 𝒜’s output to break a hard problem.

The interaction between 𝒜 and 𝒞 is modelled by the following game as follows:

• 1. $\mathcal {A}$ adaptively queries trapdoor and secure index of keywords W = [w ₁, ..., w _m ] with corresponding identity of the document.

• 2. When $\mathcal {A}$ wants to challenge, it generates set $W'=[w'_{1},...,w'_{m}]$ and a keyword pair (w ₀, w ₁) to $\mathcal {C}$, where $w_{0},w_{1}\notin W'$, and both of them are not queried for the trapdoor.

• 3. $\mathcal {C}$ randomly chooses $b \longrightarrow \{0,1\}$ and takes the keyword $w_{b}$ into the document $W'$. Finally, $\mathcal {C}$ generates the index of keywords $W'+ \{w_{b}\}$, and then returns $I_{b}$ to $\mathcal {A}$.

• 4. $\mathcal {A}$ can keep on querying the index and trapdoor with a restriction that $\mathcal {A}$ cannot ask for keywords $w_{0},w_{1}$.

• 5. Eventually, $\mathcal {A}$ outputs a value $b'$.

We define that A wins this game if and only if $b = b'$, while the adversary $\mathcal {A}$ has an $\epsilon$-advantage to win such that the advantage is $Adv_{\mathcal {A}}\left (1^{k}\right )=|Pr[b_{\mathcal {A}}=b]-1/2|>\epsilon$. Therefore, the secure index is said to be indistinguishable against the adaptive chosen keyword attack (IND-CKA) if $\epsilon$ is negligible.

Hardness assumption

There are a few hardness assumptions described as follows. They are used to prove the security of our secure index in this paper.

Pseudorandom generator

Pseudorandom Generator is randomly one-way function, and it applies in stream cipher. If $G:\{0,1\}^{n}\longrightarrow \{0,1\}^{*}$ is $\epsilon _{g}$-pseudorandom-generator with the following properties:

• (1) G is a deterministic algorithm which can efficiently compute and input $s\in \{0,1\}^{n}$, then output $G(s)\in \{0,1\}^{*}$.

• (2) There exists Algorithm $\mathcal {A}$ to query to G function with most t times. If $\mathcal {A}$ guesses G is a Pseudorandom Generator Function, then outputs 1; Otherwise, outputs 0. $\mathcal {A}$’s advantage is denoted by

  $$\left|Pr\left[A^{G(s)}=1\right]-Pr\left[A^{R}=1\right]\right|<\epsilon_g $$

  where R is a real Random Generator.

Pseudorandom function

Pseudorandom Function is randomly one-way function. (i.e. input and output pair as $(x_{1},f(x_{1},k)),$ $(x_{2},f(x_{2},k)),$ $...,$ $(x_{m},f(x_{m},k))$), then no adversary can predict $f(x_{m+1},k)$ from $x_{m+1}$. If $f:\{0,1\}^{n}\times \{0,1\}^{s} \longrightarrow \{0,1\}^{p}$ is $\epsilon _{f}$-pseudorandom-function with the following properties:

• (1) $f(x,k)$ denotes $f_{k}(x)$ that can be efficiently computed and take $x\in \{0,1\}^{n}$ and key $k\in \{0,1\}^{s}$ as input.

• (2) There exists Algorithm $\mathcal {A}$ queries to f function with most t times. If $\mathcal {A}$ guesses f is a Pseudorandom Function, then outputs 1; Otherwise, outputs 0. $\mathcal {A}$’s advantage is denoted by

  $$\left|Pr\left[A^{f(.,k)}=1\right]-Pr\left[A^g=1\right]\right|<\epsilon_f $$

  where g is Random Function.

Pseudorandom permutation function

Pseudorandom Permutation Function is 1-to-1 and randomly one-way function, would is collision resistance. If $\Pi :\{0,1\}^{u}\times \{0,1\}^s \longrightarrow \{0,1\}^{u}$ is $\epsilon _{p}$-pseudorandom-permutation with the following properties:

• (1) $\Pi (x,k)$ denotes $\Pi _{k}(x)$ that can be efficiently computed and take $x\in \{0,1\}^{u}$ and key $k\in \{0,1\}^{s}$ as input.

• (2) There exists Algorithm $\mathcal {A}$ queries to $\Pi$ function with most t time. If $\mathcal {A}$ guesses $\Pi$ is a Pseudorandom Permutation Function, then outputs 1; Otherwise, outputs 0. $\mathcal {A}$’s advantage is denoted by

  $$\left|Pr\left[A^{\Pi(.,k)}=1\right]-Pr\left[A^{E(.)}=1\right]\right|<\epsilon_p $$

  where E is Random Permutation Function.

Review of Goh’s secure index scheme

Goh’s Z-index scheme is composed of the following algorithms:

• KeyGen($l,t$): Given security parameter l and a number t, then generates a pseudorandom function $f:\{0,1\}^{k}\,\{0,1\}^{*}\rightarrow \{0,1\}^{p}$ and t independent hash functions $h_i:\{0,1\}^{*}\rightarrow \mathbb {Z}^{*}_{m-1}$ for all i, $1\leq i\leq t$. Finally, it returns the user’s key $K_{priv}$.

• Trapdoor($w,K_{priv}$): This algorithm takes the keyword w and key set $K_{priv}=[k_{1},...,k_{t}]$ as input, then computes the trapdoor $T=[x_{1},...,x_{t}]$ and delivers to the server where $x_i=f_{k_{i}}(w)$ for all i, $1\leq i\leq t$.

• BuildIndex($W,K_{priv}$): This algorithm takes keyword set $W=[w_{1},...,w_{n}]$ and key $K_{priv}=[k_{1},...,k_{t}]$ as input, where n is the number of keywords. It builds the index works as follows:

  • (1) For each keyword $w_{i}$ for $1\leq i\leq n$ as input, this algorithm first performs Trapdoor $(w_{i}, K_{priv})$ to obtain the trapdoor $T_{i} = (x_{1} = f_{k_{1}}(w_i), ..., x_{t} = f_{k_{t}}(w_i))$

  • (2) It takes $x_{1},...,x_{t}$ and the identity of document id as input for pseudorandom function to generate codeword $y_1 = f_{id}(x_1),..., y_{t} = f_{id}(x_t)$.

  • (3) It takes the codeword $y_{1} ,..., y_{t}$ as input for hash function $h_1~h_{t}$ to get $h_{1}(y_1), ..., h_{t}(y_t)$.

  • (4) Given an array d which all bits initially are ‘0’. As Bloom Filter [24], it sets that the correspond positions $h_{1}(y_1), ..., h_{t}(y_t)$ in array d modify to ‘1’ for total $(n* t)$ hash value. Building secure index $I_{id}$ is completed as Fig. 1.

• SearchIndex($I_{id},T$): The server receives the trapdoor T, and then this algorithm works as follows:

  • (1) This algorithm takes T and the identity of document id as input to compute the codeword $y_{1} = f_{id}(x_1),..., y_t = f_{id}(x_t)$.

  • (2) It takes $y_{1} = f_{id}(x_1),..., y_{t} = f_{id}(x_t)$ as input to obtain the hash values $h_{1}(y_1), ..., h_{t}(y_t)$. It then checks positions in the array s which is based on these t values as t positions. All t positions are 1, which is denoted that the keyword w is in the document with identity id. The server returns the corresponding encrypted document to the user.

Fig. 1

Goh’s secure index

The Z-index scheme has following advantages. The time complexity of each document is $O(1)$ for search via hash function. By the identity of document to compute codeword causes one keyword in different documents mapping to different values. Indices and encrypted documents are independent, which supports any secure symmetric encryption for documents. Indeed, the Z-index also has some disadvantage. To use Bloom filter exists the collision problem, it incurs false positive, i.e. a keyword $s_{j}$ is not in the set S, but by Bloom filter to check $s_{j}$ that is in S as showed in Fig. 2. In Goh’s Z-index, the size of the Bloom filter in array d is m bits and the false positive rate is $(1/2)^{r}$, the relation is $m = n' * r / \ln 2$, where $n'$ is the total number of all keywords in the all documents. $n'$ makes the index space become very large for frequent uploading new indices, since Bloom filter must provide sufficient space such as $(n'*t)$ to resist the collision.

Fig. 2

An example of false positive in Goh’s scheme

Position index scheme (P-index)

In this section, we propose an efficient secure index scheme named position index (P-index, for short); moreover, we also give the security analysis of P-index.

A new construction

The proposed P-index scheme is a new construction composing with four algorithms as before.

• KeyGen $\left (1^{l}\right )$: This algorithm takes security parameter $1^{l}$ to generate the secret key $k\in \{0,1\}^{l}$ for the user. It decides $\Pi$, G, and h, where $\Pi :\{0,1\}^{l}\times \{0,1\}^{*}\rightarrow \{0,1\}^{r}$ is the pseudorandom permutation function, $G: \{0,1\}^{r}\rightarrow \{0,1\}^{*}$ is the pseudorandom generator, and $h: \{0,1\}^{*}\rightarrow \{0,1\}^{\lg n}$ is the hash function.

• Trapdoor($w,k$): Takeing the keyword w and the user’s secret key k as input, the algorithm outputs the trapdoor $T_{w}$ where $T_w=\Pi _{k}(w)$.

• BuildIndex($id, W, k$): Given the identity of the document id, keyword set $W=\{w_{1},...,w_{n}\}$, and the secret key k, the algorithm generates the index $I_{id}$ via the following steps: (Fig. 3 shows an example of P-index.)

  • (1) The algorithm takes each keyword $w_{i}$ from set W to get the trapdoors $T_{1},...,T_{n}$ where $T_i=\Pi _{k}(w_i)$.

  • (2) It takes id and $T_{1},...,T_{n}$ as input, and then computes $x_i=\Pi _{id}(T_i)$ and $key_i=<D_{i},S_{i,1},S_{i,2}>$ for all i, $1\leq i\leq n$ where $D_{i},S_{i-1},S_{i-2}\in \{0,1\}^{r}$ are generated by $G(T_{i} \oplus id)$. It returns $x_{1},...,x_{n}$ and $key_{1},...,key_{n}$ as the codewords.

  • (3) It builds an array d with n elements and an array s with $2n$ elements, whereas the length of an element is r bits. It sets $y_{1},...,y_{n}$ where $y_i=h(x_i)$ as a pointer and randomly and uniformly chooses two positions $p_{i,1},p_{i,2}$ of the array s. Therefore, hash functions h must be different in different indices, because of different numbers for different keywords. It finally computes $p_{i,1}\oplus D_{i}$ and inserts it into the $y_{i}$th position of the array d, computes $p_{i,2}\oplus S_{i,1}$ into the $p_{i,1}$th position of the array s, and $p_{i,1}\oplus S_{i,2}$ into the $p_{i,2}$th position of the array s.

  • (4) When the collision occurs in $y_{i}$th position of the array d, a pointer linked list is using to resolve the collision. There is an example as Fig. 3 to denote the collision in which three different $x_{i}$ mapping to the same $y'$. Eventually, this algorithm returns an index $I_{id}=<s,d,id,h>$.

• SearchIndex($T_{w},I_{id}$): This algorithm, run by the server, takes the trapdoor $T_{w}$ to search the corresponding document via P-index $I_{id}$ and works as follows:

  • (1) It takes $T_{w}$ to generate the codeword $x=\Pi _{id}(T_w)$ and $key = G(id \oplus T_w) =<D,S_{1},S_2>$.

  • (2) It computes $y=h(x)$ and points yth position of the array s.

  • (3) If the value in yth position is empty, the algorithm outputs 0. Otherwise, it checks all values on this chain in yth position.

  • (4) The algorithm first gets $p'_{i,1}$ by decrypting $(p'_{i,1}\oplus D_i)$ from the yth position of the array d. It thus gets $p'_{i,2}$ by decrypting $(p'_{i,2}\oplus S_{i,1})$ from the $p'_{i,1}$th position of the array s.

  • (5) Finally, it can get $p''$ by decrypting $(p''\oplus S_{i,2})$ from the $p'_{i,2}$th position of the array s. If $p''=p'_{i,1}$, it outputs 1 in which the server returns the corresponding encrypted documents to the user; otherwise, outputs 0.

Correctness proof.

$$\begin{array}{@{}rcl@{}}p_{i,1}&=&(p'_{i,1}\oplus D_i) \oplus D_{i}, \mbox{in \textit{y}th position of Array \textit{d}.}\\ p_{i,2}&=&(p'_{i,2}\oplus S_{i,1}) \oplus S_{i,1}, \text{in} p_{i,1}\text{th} \text{position of Array} \textit{s}.\\ p_{i,1}&=&(p'_{i,1}\oplus S_{i,2}) \oplus S_{i,2}, \text{in} p_{i,2}\text{th} \text{position of Array} \textit{s}. \end{array} $$

According to Fig. 3, we give an example. Assume the key 1 is $<D_{1,1},S_{1,1},S_{1,2}>$, and $y'=h(\Pi _{id}(T_w))$. Firstly, we check $y'$th position of Array d to get $p_{1,1}$. Secondly, we keep check $p_{1,1}$th position of Array s to get $p_{1,2}$. Finally, to get $p''$ from $p_{1,2}$th position with the key $S_{1,2}$, we accept the trapdoor if $p''=p_{1,1}$.

Fig. 3

An example of the proposed scheme

Security analysis

The security game has been described in section “Security model of secure index”, while the adversary’s behavior is modelled by this game.

Definition 2

An index is the $\epsilon$-IND-CKA index. It is semantically secure against the adaptive chosen keyword attack in the random oracle model if and only if the advantage of adversary $\mathcal {A}$ is $Adv_{\mathcal {A}} = |Pr[b = b'] - 1/2| <\epsilon$. A’s goal is to guess keywords $w_{0},w_{1}$ which is in the set $W'+\{w_{b}\}$.

Theorem 1

P-index is the $\epsilon _{p}$-IND-CKA index assuming the pseudorandom permutation function $\Pi$ is $\epsilon _{p}$-pseudorandom-permutation.

Proof

First we suppose that P-index is not $\epsilon _{p}$-IND-CKA index. There exists an adversary $\mathcal {A}$ that has with non-negligible advantage $\epsilon$ to win the security game. We construct an algorithm $\mathcal {C}$ that breaks the pseudorandom permutation function $\Pi$. □

$\mathcal {C}$ acts as a challenger and returns $\mathcal {A}$’s queries. $\mathcal {C}$ simulates P-index with asking for oracle $O_{F}$ as random oracle. When the game finishes, $\mathcal {C}$ will use the A’s answer to guess whether F is a pseudorandom permutation function. $\mathcal {A}$ and $\mathcal {C}$ interact as follow:

Index & Trapdoor-queries. $\mathcal {A}$ produces a set W , and queries to $\mathcal {C}$ for the correspond index $I_{W}$. $\mathcal {C}$ maintains $O_{F}$-list to store the queries, it bases on $O_{F}$-list to return BuildIndex and Trapdoor for $\mathcal {A}$’s queries. If the keyword does not exist in $O_{F}$-list, the $O_{F}$ will set a random value for this query and save into $O_{F}$-list; otherwise, $O_{F}$ returns the value as before following $O_{F}$-list.

Challenge. After several queries, $\mathcal {A}$ generates a challenge, included a keyword set $W'$, and selects keyword pair $(w_{0},w_1)$, where $w_{0},w_{1}\notin W'$ have been never asked Trapdoor by $\mathcal {A}$. The challenger $\mathcal {C}$ randomly choices $b\in \{0,1\}$ and obtain a set $W'+\{w_{b}\}$, then computes index $I_{W'+\{w_{b}\}}$. Finally, $\mathcal {C}$ sends $I_{W'+\{w_{b}\}}$ to $\mathcal {A}$.

More queries. $\mathcal {A}$ can keep on asking BouldIndex and Trapdoor queries for keywords $w_{i}$ which is restricted that $w_{i}\neq w_{0},w_{1}$.

Output. Eventually, $\mathcal {A}$ outputs a bit $b'$. When $b=b'$, $\mathcal {C}$ outputs 1 to denote that $\mathcal {C}$ guesses F is a pseudorandom permutation function; otherwise, outputs 0.

$\mathcal {C}$’s output is based on $\mathcal {A}$’s answer. While F is a pseudorandom permutation function($\Pi ,PRP$), the environment of $\mathcal {C}$’s simulation is correct. That is said

$$\begin{array}{@{}rcl@{}} Adv_{\mathcal{A}} & = & \left|Pr[b=b']-\frac{1}{2}\right| \\ & = & \left|Pr[b=b'|\Pi:PRP]-\frac{1}{2}\right| \\& = & \left|Pr\left[\mathcal{C}^{\Pi_{k}(.)}=1|\Pi:PRP\right]-\frac{1}{2}\right|\geq \epsilon_p \end{array} $$

(1)

If F is a real random permutation function($E,RP$), the trapdoor of $w_{0},w_{1}$ can not be guessed, since the trapdoor from F is real random. It also is not based on the trapdoor or the index to analysis, thus algorithm $\mathcal {A}$ guesses $b=b'$ with probability $1/2$ as follow:

$$\begin{array}{@{}rcl@{}} Pr[\mathcal{A}|win]& = &|Pr[b=b'|E:RP]| \\ & = &\left|Pr\left[\mathcal{C}^{\Pi_{k}(.)}=1|\Pi:RP\right]\right|\\ & = &1/2 \end{array} $$

(2)

Because of $(1),(2)$, the advantage of $\mathcal {C}$ is

$$\begin{array}{@{}rcl@{}} &&Adv_{\mathcal{C}}\\ &&=\left|Pr\left[\mathcal{C}^{\Pi_{k}(.)}=1|\Pi:PRP\right]-Pr\left[\mathcal{C}^{E(.)}=1|E:RP\right]\right|\\ &&=\left|Pr\left[\mathcal{C}^{\Pi_{k}(.)}=1|\Pi:PRP\right]-\frac{1}{2}\right|\geq \epsilon_p \end{array} $$

(3)

With above results, we show that if the pseudorandom permutation function $\Pi$ is $\epsilon _{p}$-pseudorandom permutation, P-index is $\epsilon _{p}$-IND-CKA index. This is, the proof of Theorem 1 is complete, while P-index will be the IND-CKA index if and only if P-index uses the secure function to building the trapdoor.

Comparisons

Now we compare our scheme to Goh’s [18] in terms of space cost and false positive in Table 1. We list the following notation for comparisons.

Table 1 Comparison of space and other attributes with Goh’s and the proposed scheme

Notation:

• n: number of keyword in the document

• $n'$: total number of keyword in all documents

• t: number of hash functions in Bloom filter

• r: length of an element of array s

Due to $n'\geq n$, P-index uses more extra space to meet lower false positive rate; however, in the worst case, the space cost is total $4nr$ bits. To build a Bloom filter in Z-index has to predict the number of all keywords, so space cost of Z-index is $n't$ bits. Our scheme is flexible in the space. However, it does not adopt the bilinear pairing that is a complicated computation, and thus it is more efficient than some schemes [11–15].

Conclusions

In this paper, we have proposed a new secure index scheme for keyword-search over encrypted ERMs, referred to as P-index. The main properties of P-index are flexible space and lower false positive on secure channel, and P-index maintains the efficient searching, which would be suitable for the mobile device or other lower computational machine. The proposed P-index is semantically secure against the adaptive chosen keyword attack in the random oracle model assuming that the pseudorandom permutation function is intractable to break.