Journal of Communications and Information Networks

With the rapid development of cloud computing, cloud storage has enabled the provision of high data availability, easy access to data, and reduced infrastructure costs from outsourcing of data to remote servers. Many users prefer cloud storage services to relieve the burden of maintenance costs as well as the overhead of storing data locally. Moreover, users are able to access their data from anywhere and at any time instead of having to use dedicated machines.

Although cloud storage offers many advantages to users, there are still various security concerns. A remote server cannot be fully trusted because it may not only be curious about the users data but also abuse the data. When users outsource their data to a remote server, the physical access to the data is actually lost and the administration of the data is delegated to the server as well. Thus, it is necessary to guarantee the privacy of users sensitive data. The most common way of achieving privacy is to encrypt the data before outsourcing them. This approach provides end-toend data privacy as soon as the data leave the users possession. While such a solution guarantees the privacy of sensitive data, it also brings difficulties for the server to perform any meaningful function, especially search functions, on the encrypted data.

Consider a search function on plaintexts. A user sends query keywords to the server in order to retrieve corresponding documents. After searching, the server will return the search results to the user. However, during the search process, both the knowledge of the contents stored on the server and the query keywords are exposed to the semi-trusted server. Fortunately, encryption is a positive way to protect the privacy of users data, but at the same time it disrupts search functionality. A trivial way to search is to download all the ciphertexts, decrypt them, and then search on the plaintexts. However, this is impractical. Consequently, a method that provides data confidentiality and preserves search functionality simultaneously is needed as this is an open problem.

SE has been proposed. It is not only an encryption scheme but also supports keyword search on encrypted data. In SE schemes, a user can outsource a collection of encrypted data to the server while maintaining the ability to search them. From the aspect of security, the privacy of documents and keywords is maintained. The two main branches of SE are SSE and PEKS. SSE is related to the private key primitive. It allows only the private key holder to produce ciphertexts and to create trapdoors for search. PEKS, on the other hand, is related to the public key primitive. It enables a number of users who know the public key to produce ciphertexts but only allows the private key holder to create trapdoors for search.

This article surveys the practical techniques of SE. The main contributions of this paper are (1) a review of the most meaningful SE approaches, mainly focusing on SSE and PEKS, and (2) analysis and classification of these approaches. The similarities and differences of these schemes are also examined and the outstanding issues for further studies discussed. The remainder of this paper is organized as follows: the model and security requirements for SE are given in Section 2. A review of SSE techniques is given in Section 3. A review of PEKS techniques is given in Section 4. Finally, conclusions and valuable issues for further work are given in Section 5.

A searchable encryption scheme includes three parties: a trusted data owner O, a semi-trusted server S, and a collection of users who are authorized to search. The task for each party is as follows:

• Data owner: A data owner would like to outsource a collection of documents D={D₁, D₂, …, D_n} together with some keywords. The data owner needs to encrypt the documents and keywords in a particular manner, in order to easily search them afterward, then sends the ciphertexts to the server.

• Data user: If an authorized user wants to search the documents that contain a particular keyword, she/he has to submit the trapdoor of this query keyword to the server. After searching, the server returns the documents that contain this keyword to the user.

• Server: A server performs search tasks. When the server receives a trapdoor of a query keyword from a user, it searches over ciphertexts and then returns related documents to the user. We assume that the server is honest-butcurious. This means the server will follow the protocol correctly, but it may analyze the data received and attempt to obtain some additional information.

In a searchable encryption scheme, the security of the documents and keywords stored on the server should be guaranteed. In addition, the security of query keywords should also be assured. Moreover, the following two security items should also be protected^[1]:

• Search pattern: Search pattern is defined as any information that can be derived from knowledge of whether two search results are from the same keyword.

• Access pattern: Access pattern is defined as a sequence of search results (D(w₁), …, D(w_n)), where D(w_i)is the search results of wi. In other words, D(w_i)is a collection of documents in D that contains the keyword w.

Consider the following scenario: A user, Alice, wants to store a set of documents on a server because of limited storage resources. As the server is semi-trusted, Alice has to encrypt the documents before outsourcing them. If Alice needs some documents containing a particular keyword, she will need to submit some information in terms of query keywords to the server. Then, the server will search the ciphertext to determine which document contains the query keyword. Fig.1 shows the model of SSE schemes.

A general searchable symmetric encryption scheme includes four polynomial-time algorithms:

• Keygen(1^k): a key generation algorithm run by the data owner. It takes a security parameter k as input, and outputs a secret key K.

• BuildIndex(K, D): a keyword index generation algorithm run by the data owner. It takes a secret key K and a set of documents D as inputs, and outputs a keyword index I.

• Trapdoor(K, w): a keyword trapdoor generation algorithm run by the user. It takes a secret key Kand a query keyword w as inputs, and outputs the trapdoor T_w for the keyword w.

• Search(I, T_w): a keyword search algorithm run by the server. It takes a keyword index I and a trapdoor T_w as inputs, and outputs a set of documents D(w) that contains query keyword w.

A searchable symmetric encryption scheme should satisfy various security requirements. The privacy of documents, search index, and query keywords should be protected, as well as the search pattern and access pattern. Song, et al. ^[2]argued that their scheme is provably secure because the server cannot learn any information about the plaintext by knowing the ciphertext. However, this kind of security is not strong enough in the context of SSE. IND1-CKA and the stronger IND2-CKA security model, which address the security of keyword indexes, have been proposed by Goh^[3]. In both security models, an adversary A cannot learn the contents of a document from its index. In the IND1-CKA model, it is assumed that the indexes are built from documents with the same number of keywords. Conversely, in the IND2-CKA model, this assumption is not necessary. However these two models do not consider the security of trapdoors. Curtmola, et al. ^[1]introduced new adversarial models that consider the security of trapdoors. The first is a non-adaptive model, IND-CKA1, in which the adversary does not consider the trapdoors and search results of previous searches when he or she chooses challenge search queries. The other is an adaptive model, IND-CKA2, in which the adversary chooses their challenge search queries with the knowledge of trapdoors and search results previously obtained. In this article, we primarily focus on the IND-CKA1 and IND-CKA2 security models to compare various schemes.

3. 3. 1 Single keyword search

1) SSE schemes with sequential scan. Song, et al. ^[2] proposed the first SSE scheme. In their solution, search is performed by sequentially scanning the entire ciphertext. The underlying idea of this scheme is that the ciphertext is obtained by XORing each of the keywords in the plaintext with a sequence of pseudorandom bits. Thus, it is allowed to directly search on the ciphertext.

The scheme comprises three steps: encryption, search, and decryption.

Firstly, encryption is performed by the user, Alice. Suppose Alice wants to encrypt a document containing a sequence of keywords W₁, …, W_l. The encryption for each keyword W_i is as follows. First, Alice encrypts W_i by using function E with key k″and obtains the ciphertext X_i which is n bits. That is, X_i=E_k″(W_i). Then X_i is split into left part L_i and right part R_i, where L_i is the first(n-m)bits and R_i is the latter m bits of X_i. Then Alice generates a sequence of values S₁, …, S_i, where S_i is(n-m)bits long. To encrypt n-bits X_i, Alice takes value S_i, sets , and outputs the ciphertext , where k_i=f_k′(L_i). Finally, Alice outputs all the ciphertext C_i to the server. Fig.2 shows the procedure utilized for encryption in this scheme.

Secondly, search is performed by the server. When Alice wants to search documents containing the keyword W, she computes X=E_k″(W) and k =f_k′(L), and sends< X, k> to the server. Then, the server searches for X in the ciphertext by checking whether $C\oplus X$ is of the form< s, F_k(s)> for some s. If this C exists, the server sends the entire ciphertext for the document containing the query keyword to Alice.

Finally, Alice decrypts the ciphertext. For each C_i in the ciphertext, Alice generates S_i using pseudorandom generator, then she XORs S_i and the first(n-m)bits of C_i to obtain the L_i. With the knowledge of L_i, Alice can compute k _i and eventually recover W_i.

In this scheme, the privacy of plaintext and the query keyword is maintained. However, it has a low search efficiency and the search time is linear in the length of the document collection, because the server needs to scan the entire ciphertext of a document when it determines whether a certain keyword is contained in the document. In addition, the plaintext is vulnerable to statistical attack according to the frequency of the query keyword occurring in the document.

2) SSE schemes with secure index. Document-based Index: To improve search efficiency, Goh^[3]proposed a secure index construction using pseudorandom functions and Bloom filters^[4]. With a Bloom filter, one can quickly determine whether an element belongs to a set. In this scheme, the pseudorandom function is applied twice to each keyword in the document. Then, the outputs are mapped to the Bloom filter. With the knowledge of the Bloom filter, it is much easier to determine whether a document contains a certain keyword.

Unlike the scheme proposed by Song, et al. ^[2], this scheme is based on a secure index. The advantage of this scheme is that the server only needs to search over the search indexes instead of scanning the entire ciphertext. As a result, the search efficiency is improved. However, the server also has to search each index and the search work for a query is linear in the number of documents, even if only one document contains the query keyword. We denote this kind of secure index as document-based index, in which the index corresponds with the documents.

Keyword-based Index: Another kind of secure index, called a keyword-based secure index, was proposed by Curtmola, et al. ^[1]. In this keyword-based secure index, one keyword corresponds to many document identifiers. In this scheme, the search time for a query keyword is linear in the number of documents containing the query keyword. Consequently, compared with the document-based index, keyword-based index is more efficient in searching a query. However, updating a keyword-based index when documents are added, deleted, or modified in the collection is difficult.

3) Dynamic SSE scheme. Van Liesdonk, et al. ^[5] proposed a dynamic SSE scheme that can deal with document updates. In their scheme, the search time is logarithmic in the keywords stored in the server. The basic scheme extends to two schemes, both of which support document updates. The first scheme is interactive, whereas the second is no interactive. Kamara, et al. ^[6]proposed an extension of Curtmola, et al. 's scheme to support updates, which is based on PRFs and XORs. However, updates would leak some information about the trapdoors. Subsequently, Kamara and Papamanthou^[7]proposed a new dynamic tree based SSE scheme. In their proposed scheme, no information is leaked after the updating operation. Stefanov, et al. ^[8]proposed an efficient dynamic SSE scheme with a small information leakage. Various researchers have also focused on the dynamic property^[9, , ^[10,11,12]. A comparison of several classic SSE schemes is given in Tab.1. In the table, n denotes the size of the documents set, r denotes the number of documents containing query keyword ω, m denotes the size of the keywords space and p denotes the number of cores.

Cash, et al. ^[13]and Zhang, et al. ^[14]recently focused on attacks on the SSE scheme, whereas Ishai, et al. ^[15] focused on improving its security. Further, Kamara and Moataz^[16]focused on improving its functionality, while Asharov, et al. ^[17]focused on improving its performance.

3. 3. 2 Fuzzy keyword search In the SSE scheme, a user submits the trapdoor of a query keyword to the server, and the server returns the documents containing the query keyword. However, if the query keyword does not match a preset keyword, such as “campus” and “compus”, the keyword search will fail. Fortunately, fuzzy keyword search can deal with this problem as it can tolerate minor typos and formatting inconsistencies. Li, et al. ^[18]constructed a fuzzy keywords collection using “edit distance” to quantify keywords similarity. Kuzu, et al. ^[19]used gram to construct fuzzy sets and LSH and Bloom filter to construct a ranking search scheme. Because a semi-honest server may only return a fraction of the results, Wang^[20]proposed a verifiable fuzzy keyword search scheme that not only supports fuzzy keyword search, but also provides proof to verify whether the server returns all the search results. Several other proposed schemes also support fuzzy keyword search^[21,22].

3. 3. 3 Conjunctive keyword search Conjunctive keyword search allows a user to obtain documents containing several keywords during a single query. It is more efficient and suitable for real applications than single keyword search. A trivial procedure is to perform single keyword search for each keyword separately and then deal with the results. However, it is inefficient and leaks some information to the server. Golle, et al. ^[23]proposed the first two conjunctive keyword search schemes. The communication cost of their first scheme is linear in the number of documents, but the major job can be done offline. Their second scheme requires only constant communication and there is no need to do anything offline. Ballard, et al. ^[24]presented two conjunctive keyword search constructions, one based on the nonstandard shamir secret sharing technique and the other on bilinear pairings. However, in their case, the trapdoor size is linear in the number of documents being searched. Cash, et al. ^[25]extended conjunctive query to Boolean query. Faber, et al. ^[26] extended Cash, et al. ′s scheme^[25]to support range, substring, wildcard, and phrase queries. In their system, the least frequent keyword is queried first, and the search results are then applied to other keywords. Theirs is the first sublinear SSE construction supporting Boolean query. Several other studies have also been conducted on this topic^[27,28].

3. 3. 4 Ranked and verifiable keyword search Ranked keyword search can optimize search results by returning the most relevant documents. This can reduce network traffic and enhance system usability. Swaminathan, et al. ^[29], Zerr, et al. ^[30], and Wang, et al. ^[31,32]achieved ranked search in the single keyword search paradigm using an order-preserving function. Cao, et al. ^[33]were the first to present a multi-keyword ranked search scheme with“coordinate matching”measurement. However, their search results are ranked based on the number of matching keywords without considering the importance of Different keywords. Consequently, their results are not very accurate. Sun, et al. ^[34]proposed a multi-keyword ranked search scheme using“cosine measure”techniques. Their scheme achieves better-than-linear search efficiency at the expense of search accuracy. Xia, et al. ^[35]recently proposed a dynamic multi-keywords ranked search scheme that uses a secure tree. Chen, et al. ^[36]proposed a multi-keyword ranked search scheme based on hierarchical clustering index to improve search efficiency. In their scheme, the search time has a linear growth when the size of the data collection has an exponential growth. Other studies have also been conducted on ranked search^[37,38,39].

Verifiable keyword search can detect whether the search results are complete and correct. This can verify inaccurate search results caused by software or hardware failure, storage corruption, or even malicious behavior by a semi-honest server trying to save computation resources. Studies have also been conducted on verifiable keyword search^{[40,41,42, [43]}. However, these studies are based on MHT (Merkle Hash Tree) and signature techniques, which have expensive communication and computation overhead. Chai, et al. ^[44]proposed a verifiable searchable encryption scheme. Wang, et al. ^[45]focused on verification of an empty set as a search result.

Consider the following scenario: Bob sends an email with corresponding keywords to Alice. In order to protect the contents of the email and keywords, both are encrypted with Alices public key. However, in this case the email server cannot make a routing decision according to the keywords. Therefore, it is necessary to give the email server the ability to decide whether a certain keyword is contained in an email or not. Meanwhile, the email server cannot learn anything about the contents of the email and keywords. To achieve this goal, Boneh, et al. ^[46] proposed the first scheme supporting keyword search in a public key system. Fig.3 shows the model of PEKS schemes.

When user Bob wants to send Alice an email with a number of keywords, W₁, …, W_k, Bob sends the following ciphertext: E_Apub(M), PEKS(A_pub, W₁), …, PEKS(A_pub, W_k), where M is the content of the email, Apub is Alices public key, and PEKS is an algorithm supporting keyword search. Then, Alice produces a trapdoor T_ω of keyword W and sends T_ω to the gateway. After searching, the gateway returns the emails containing W to Alice. A general PKES scheme contains four polynomial-time algorithms:

• KeyGen(1^k): a key generation algorithm run by Alice. It takes a security parameter k as input, and outputs a public/private key pair A_pub, A_priv.

• PEKS(A_pub,W): a public key encryption algorithm preserving search ability that is run by Bob.It takes the public key Apub of Alice and a keyword W as input, and outputs ciphertext S of W.

• Trapdoor(A_priv, W): a keyword trapdoor generation algorithm run by Alice. It takes Alices private key A_privand a query keyword W as input, and outputs the trapdoor T_ω of query keyword W.

• Test(A _pub, S, T_ω): a test algorithm run by the mail server. It takes Alices public key Apub, a ciphertext S of keyword W′ and a trapdoor of query keyword W. If W=W′, this algorithm outputs “yes”; otherwise, it outputs “no”.

In PEKS schemes, the security of the ciphertexts of a keyword (the output of the PEKS algorithm ) should be guaranteed. We argue that the ciphertexts should not leak any information about a keyword even under an adaptive chosen keyword attack. In such an attack model, an active attacker has the ability to obtain trapdoors T_W for any keyword W except the challenge keywords. The attacker chooses two challenge keywords W₀and W₁for a challenger. The challenger randomly chooses b∈ 0; 1 and sends the ciphertext of W_b to the attacker. The attacker needs to determine the number b with the knowledge of trapdoors for other keywords. We refer to this kind of security model as PK-CKA2 security, in which the attacker cannot determine whether the ciphertext is from W₀or W₁. For a detailed definition of this PK-CKA2 security, please see Ref. [46]. This security definition is predominantly used in the remainder of this paper.

4. 3. 1 Single keyword search

The first PEKS scheme was proposed by Boneh, et al. ^[46]. It was based on IBE (Identity Based Encryption)^[47,48]and consisted of three stages. First, the message sender encrypts her/his message and keywords with the receivers public key in a particular way. The ciphertext is E_Apub(M), PEKS(A_pub, W₁), …, PEKS(A_pub, W_k), where M is the message content, and Apub is the public key of the receiver. Next, the receiver sends the trapdoor T_ω of query keyword W to the server. Finally, the server searches over the ciphertexts and determine whether a certain keyword is in a particular ciphertext.

The scheme requires two groups, G₁, G₂, of prime order p, which is determined by a security parameter and a bilinear map e: G₁×G₁→G₂. In addition, the scheme requires two hash functions H₁: {0, g}^*→G₁ and H₂: G₂→{0, 1}^{log p}. The detailed algorithm is as follows:

• KeyGen(1^k): The input is a security parameter k that is used to determine the size, p, of the two groups G₁and G₂. In addition, it needs to pick a random element α∈Z_p* and a generator g of G₁. Finally, it outputs a public key A_pub=[g, h=g^α]and a private key A_priv=α.

• PEKS(A_pub, W): It first computes t=e(H ₁(W), h^r)∈G ₂, where r is a random element in group Z_p^*. Then, it outputs PEKS(A_pub, W)=[g^r, H₂(t)].

• Trapdoor(A _priv, W): It outputs a trapdoor T_W of certain keyword W, T_W=H₁(W)^α∈G₁.

• Test(A_pub, S, T_W): It tests whether H ₂(e(T_W, g^r))=H₂(t). If so, it outputs “yes”; otherwise, it outputs “no”.

On one hand, this scheme has been proven PKCKA2 secure in the Random Oracle model under the difficulty of the Bilinear Diffie-Hellman problem. However, trapdoors should be transmitted over a secure channel, to ensure only the server receives them. Furthermore, trapdoors are produced by using a deterministic encryption, thus the server can store them for further use. On the other hand, the efficiency is not sufficiently high as the PEKS algorithm requires one pairing and two exponentiations. In addition, the test algorithm requires one mapping and the search complexity is linear in the number of keywords per document.

Many studies have been conducted on methods of constructing PEKS schemes. Some typical methods are introduced and classified into three categories based on their security below.

1) Traditional PEKS: Abdalla, et al. ^[49]proposed a generic solution for transforming an anonymous IBE scheme into a PEKS scheme. They also constructed a PEKS scheme based on temporary keyword from hierarchical IBE. In their scheme, a trapdoor is produced along with a time interval [s, e], and the mail server is only allowed to test whether a certain keyword w is in the ciphertext during this time interval. This method effectively prevents the server from searching a keyword in the past or future.

Di Crescenzo and Saraswat^[50]introduced the first PEKS scheme without bilinear maps. Their scheme, transformed from Cocks IBE scheme^[51], is based on a variant of the quadratic residuosity problem. The scheme has been proven PK-CKA2 secure in the RO model. However, it has to calculate 4k Jacobi symbols in order to test whether a certain keyword is in a document, where k is a security parameter. Further, the search time is linear in the number of ciphertexts. Moreover, it has a high storage and communication overhead.

Khader^[52]proposed a PEKS scheme based on k-resilient IBE. The scheme is PK-CKA2 secure without an RO model. However, PEKS algorithm is inefficient and involves the calculation of four exponentiations to test whether a certain keyword is in a ciphertext. The scheme was also used to construct another two schemes: one supporting conjunctive keyword search; the other requiring no secure channel to transmit the trapdoors.

2) Secure Channel Free PEKS: Boneh, et al. ’s scheme^[46]has the limitation that a secure channel is required to transmit the trapdoors; thus, only the server can learn the trapdoor. However, it is not practical as building a secure channel is expensive. To overcome this problem, Baek, et al. ^[53]proposed SCF-PEKS (Secure Channel Free PEKS), which does not require a secure channel. This new PEKS scheme adds the servers public/private key pair; hence, only the server can search over the ciphertext. Rhee, et al. ^[54]subsequently enhanced the security of Beak, et al. ’s model^[53]. In their security enhanced model, an attacker can obtain the relationship between ciphertexts and a trapdoor. Recently, Emura, et al. ^[55]extended the security of the SCF-PEKS scheme to an adaptive SCF-PEKS scheme based on the anonymous IBE. This model allows an attacker to test query keywords adaptively.

3) Against Keyword Guessing Attack: Byun, et al. ^[56]first raised an off-line KGA (Keyword Guessing Attack) because of the small space for keywords. They also stated that Boneh, et al. ’s scheme is vulnerable to off-line keyword guessing attacks. Yau, et al. ^[57]asserted that the SCFPEKS^[53] and PKE/PEKS^[58]schemes are also vulnerable to this attack. They showed that an outside adversary can capture the trapdoor from a public channel (outside KGA), while an inside adversary, such as a malicious server, can capture the trapdoors from either a public or secure channel. Rhee, et al. ^[59]proposed a scheme against outside KGA that introduces a random variable in the trapdoor computation to make the trapdoors indistinguishable. Fang, et al. ^[60]proposed a concrete SCF-PEKS against outside KGA.

For inside KGA, Jeong, et al. ^[61]showed that constructing a secure and consistent PEKS scheme against KGA is impossible when the number of possible keywords is bounded by some polynomial. Xu, et al. ^[62]presented a PEKS scheme that supports fuzzy keyword search. In their scheme, more than one keywords share the same fuzzy keyword trapdoor such that the server cannot learn the exact keyword. However, their scheme has limitations in terms of security and efficiency. Chen, et al. ^[63]proposed a new PEKS framework, called dual-server PEKS, which is secure against inside KGA.

Tab.2 compares several classic PEKS schemes. In the table, n denotes the size of the documents set, v denotes the number of distinct keywords per document, p denotes the symmetric prime order pairing, l denotes the length of the keyword in characters, J denotes the Jacobi symbol, and e denotes the exponentiation.

4. 3. 2 Conjunctive keyword search

Park, et al. ^[64]constructed two schemes supporting conjunctive keyword search in public key systems, in which the computation overhead is efficient and trapdoor size is constant. However, the first scheme requires a number of bilinear paring mappings and the number of private keywords is linear in the size of keyword fields. Boneh and Waters^[65]presented a public key scheme based on hidden vector encryption that supports comparison queries, subset queries, and arbitrary conjunctive queries. The attribute values cannot be leaked after decryption. However, the ciphertext size is large because of the use of composite order bilinear groups. In addition, it has a high cost in terms of public key size and encryption operation. Fortunately, the decryption key size and decryption cost are minimized. Shi, et al. ^[66]proposed a scheme supporting multidimensional range query over encrypted data that can be used to share network audit logs. However, it leaks attribute values after decryption. Hwang and Lee^[67]improved the size of ciphertext and private key. Kaze, et al. ^[68]constructed a PEKS scheme supporting disjunctive keyword search that is based on inner-product predicate encryption. However, the ciphertext size and private key size is bounded by some superpolynomial. Lai, et al. ^[69]introduced an efficient PEKS scheme supporting arbitrary monotone Boolean predicates that is based on key-policy attribute-based encryption (KP-ABE)^[70].

4. 3. 3 Fuzzy keyword search Bringer, et al. ^[71]proposed an error-tolerant searchable encryption in the context of public key that is based on functions of LSH (Locally Sensitive Hashing)^[72] and BFS (Bloom Filter with Storage)^[73]. An LSH function can be used to reduce the difference among similar items and a BFS function is used to answer set membership queries. If two keywords are sufficiently similar, the hash values of LSHs output is the same. Inputting the LSH values into BFS achieves error tolerant search. Their scheme has been proven PK-CKA2 secure, and protects the search pattern as well using the PIR technique.

4. 3. 4 Verifiable keyword search The server is assumed semi-honest such that it may just return a part of the search results or even inaccurate results. Zheng, et al. ^[74]dealt with this problem with an attribute based encryption scheme called VABKS (Verifiable Attribute-Based Keyword Search). In this scheme, only the user who satisfies the data owners access control policy is allowed to perform search and verify operations. However, verifying the correctness of search results is expensive. Furthermore, the scheme is vulnerable to off-line attacks because the keyword ciphertext and the search token can be easily obtained by an adversary. Liu, et al. ^[75]proposed a new VABKS scheme, in which a secure channel is not necessary. Their proposed scheme is also relatively efficient in verifying the correctness and integrity of search results.

Since the proposal of SSE and PEKS in 2000 and 2004, respectively, the searchable encryption research field has received significant attention. Progress has been made in the following three main directions.

1) Query Expressiveness. Much research has been conducted on extension of query expressiveness. To make schemes more practical, not only exact single keyword search, but also fuzzy keyword search, range search, and subset search are supported. Query results have also been optimized. For example, ranked keyword search finds the most closely related results and verifiable keyword search verifies the correctness and completeness of the results. However, many schemes improve query expressiveness at the expense of efficiency or security. Therefore, future research should pay attention to the tradeoff between query expressiveness and efficiency or security.

2) Efficiency. From the aspect of SSE, the search complexity in some schemes is linear in the number of documents stored on the server. Further, some schemes achieve sublinear search times, in which the search complexity is logarithmic in the number of keywords in all documents. In addition, some schemes achieve optimal search time, in which the search complexity is linear in the number of documents containing the query keywords. With the advent of the big data era, large scale data now need to be stored on servers. Thus, the question of how to deal with large-scale data efficiently is a direction for further work. Moreover, the documents cannot be

flexibly updated because the search index is related to the keywords. Hence, the question of how to construct an efficient dynamic SSE scheme is another direction for future work. From the aspect of PKES, a large number of schemes are based on pairing maps. As a result, these schemes are inefficient because pairing maps are inefficient algorithms. Thus, construction of practical PEKS schemes is also a direction for future work.

3) Security. On one hand, although virtually all SE schemes achieve provable secure, they do not use a common security model. That is, different schemes use different security models under different assumptions. Hence, it is always difficult to compare their security. Thus, proposal of a standard security model for SE schemes is a direction for future work. Further, most schemes compromise on search pattern and access pattern. Thus, construction of an efficient scheme that does not leak search pattern and access pattern is another direction for future work.

Future work should also focus on the question of how to apply the ideas underlying SE to deal with other kinds of data. For example, how to search encrypted media data containing image data or video data; how to search an encrypted database containing relational database or non-relational database; and how to search structured social network data.