Ling Huaze, Xue Kaiping*, Wei David S.L., Li Ruidong

1. School of Cyber Security, University of Science and Technology of China, Hefei, Anhui 230027, China;2. Computer and Information Science Department, Fordham University, NY 10458, USA;3. College of Science and Engineering, Kanazawa University, Kakuma-machi, Kanazawa 920-1192, Japan

Abstract: As more and more enterprises and individuals choose to outsource their encrypted private data to the cloud, Searchable Encryption (SE), which solves the issue of keyword-searching over encrypted data, is becoming much more important. To overcome typos and semantic diversity existing in query requests, fuzzy search is introduced to achieve a misspelling-tolerate search-supported encryption scheme. However, current schemes of fuzzy search over encrypted data not only bring in high computing and communication overhead in multi-user scenarios but also are unable to cover all kinds of error types under the premise of an effective accuracy. In this paper, we thus propose a multi-user multi-keyword fuzzy searchable encryption scheme. Specifically, we introduce the permuterm index to support multi-keyword wildcard search which can solve more kinds of misspelling with a higher degree of correctness. Moreover, by letting the cloud server re-encrypt indexes user encrypt, our scheme supports unshared-key multi-user fuzzy search, reducing users' computing overhead effectively and improving the level of privacy-preserving. The results of experiments demonstrate that, compared with existing schemes, our scheme not only has a better accuracy rate, but also supports more varieties of misspelling keyword search with acceptable computational overhead.

Keywords: encrypted cloud storage; proxy re-encryption; privacy preservation; searchable encryption

1 Introduction

With the advent of the era of cloud computing, more and more enterprises and individuals choose to outsource the storage and management of their data to reduce their local management costs. However, private data must be encrypted before uploaded to avoid data leakage and abuse[1,2]. Meanwhile, essential data management including efficient keyword searching is necessary. In such a computing environment where the encrypted data have no semantics and no logic, it would be challenging to do content-related searches. A simple solution is to download all files and decrypt them locally, transforming the search over encrypted files to plaintext searching. However, such a solution makes outsourcing data to the cloud pointless and brings huge overhead. Therefore, we expect a solution to do searching directly over ciphertext possible.

Searchable Encryption (SE) is such a solution proposed to do a content-related query over ciphertext, which usually has three steps: index generation, encryption, and matching of encrypted index and query. Once a data user sends an encrypted query, the cloud server should be able to return the corresponding files, of which the encrypted index exactly match the encrypted query, without knowing any information. During the process, cloud service should be able to provide search services with the same level of querying quality, usability, and flexibility as plaintext search, and at the same time it should also guarantee the privacy protection for users’ uploaded sensitive data.

However, errors in the keywords are unavoidable in the real world, which may make SE not return correct results. Thus fuzzy search[3,4]is proposed to achieve search tasks with misspelled or partially spelled query keywords. In fuzzy search, keywords are decomposed into several substrings through keyword transformation, and will be stored in bloom filters. Finally, the cloud server calculates the Euclidean distance between bloom filters of indexes’ substrings and queries’ substrings. And the files, of which the indexes have the least Euclidean distance will be returned.

Although many schemes have been proposed in terms of fuzzy searchable encryption[3-6], they still have many problems. Firstly, different methods of keyword transformation greatly affect the correctness and efficiency of the searching. Due to deficiencies in the methods to transform keywords, the accuracy rate of existing schemes is still low. Secondly, many schemes adopt locality-sensitive hashing (LSH) functions from the same hash family to generate the bloom filter. Benefiting from the feature of LSH functions that similar substrings (Euclidean distance between them is within a threshold) are mapped to the same positions of bloom filter with a high probability, these schemes can achieve matching of error keywords. However, once the error degree of keywords is higher than the threshold set by LSH, the accuracy rate of the fuzzy search will significantly decrease, which makes it difficult to support the multi-keyword fuzzy search scenario. Besides, the methods of keyword transform in existing schemes cannot support wildcard, which causes they cannot achieve the fuzzy search with more kinds of misspellings. Therefore, a more effective misspelling-tolerate method of keyword transformation is needed.

Moreover, to make fuzzy search schemes more practical, they should be efficient and effective in a multi-user scenario, where data users can query multiple repositories owned by different owners, meanwhile, a repository can be searched for multiple users. Some searchable encryption schemes in multi-user scenarios have already been proposed[7-9]. But unfortunately, as far as we know, there are no schemes that can support fuzzy search efficiently. Secure k-nearest neighbor (secure KNN), homomorphic encryption and attributed based encryption (ABE) are widely used in the multi-user searchable encryption. The schemes based on the first two algorithms often bring huge computational overhead, since when users make queries in different repositories, he/she must encrypt his/her query several times with the corresponding secret key of each data owner. Although the ABE-based schemes can decrease the times of encryption, it can not support fuzzy search. Thus, straightforwardly applying these schemes to the fuzzy search scenario is unfeasible and we need to explore a new solution to achieve multi-user fuzzy searchable encryption considering both searchable encryption and keyword transformation method.

Motivated by these observations, we propose an efficient multi-user multi-keyword fuzzy search scheme over encrypted cloud storage. Specifically, we develop a novel method of keyword transformation by introducing permuterm index, which can tolerate a higher degree of misspelling and support wildcard query. Meanwhile, in order to avoid the sharp decrease of accuracy rate caused by the increase of fuzzy keywords, our scheme stores the substrings in bloom filter directly and distinguishes substrings by using keyword length as a mark. And we apply an improved secure KNN where the index/query will be encrypted by users and re-encrypted by the cloud server in our scheme. Users can encrypt original indexes or queries with their keys for only one time, which greatly reduces the computing overhead. The main contributions of our work are summarized as follows:

(Ⅰ) We propose an efficient fuzzy search scheme over encrypted cloud storage in multi-user multi-keyword scenario. By applying an improved secure KNN where cloud server will re-encrypt owners’ data and users’ queries, our scheme largely reduce the computational overhead of users in multi-user scenario.

(Ⅱ) We also design a novel data transformation method by introducing permuterm index to make our scheme have a high degree of error tolerance and support wildcard query. Besides, in order to avoid the sharp decrease of accuracy caused by the increase in the number of fuzzy keywords in multi-keyword scenario, our scheme stores the substrings to bloom filter directly and distinguishes substrings by using keyword length as a mark.

(Ⅲ) We analyze the security strenth of our scheme, and evaluate the performance by conducting experiments, which shows that our scheme has higher accuracy, higher error tolerance, and less computational overhead while ensuring confidentiality, indistinguishability of query and privacy preservation.

The remainder of this paper is organized as follows. In Section 2, we introduce the system model, security assumption and design goals of our work. Preliminaries including bloom filter, permuterm index and secure KNN are introduced in Section 3. And the details of our multi-user multi-keyword fuzzy searchable encryption scheme are shown in Section 4. Then, we present the security analysis and performance evaluation in Sections 5 and 6 respectively. Then, the related work is given in the Section 7. Finally, we conclude our work in Section 8.

2 Problem statement

2.1 System model

Our system model consists of four main entities, namely trusted authority (TA), data owner (DO), data user (DU), and cloud service provider (CSP). Figure 1 illustrates the construction of our system.

Figure 1. System Model

Figure 2. An example of bloom filter.

(Ⅰ)TA is responsible for generating, distributing and managing system parameters, and it is trusted by all entities in the system. During the system initialization, TA generates pairs of secret key and switch key according to users’ privileges, then distributes them to users and the cloud server respectively.

(Ⅱ)DO has a collection of files, and prefers to upload them to the cloud server sharing with other users. Before uploading the files, DO needs to build an encrypted index based on a set of keywords, which will also be uploaded to the cloud sever.

(Ⅲ)DUs make requests to the CSP by sending encrypted query, expecting the data files which match the keywords in his/hey query.

(Ⅳ)CSP provides the services of data storing, querying, and computing for DO and DU. Upon receiving the query from DU, CSP conducts keyword search and returns the matched files according to the keywords in the query.

2.2 Security assumption

Following References [7,8], we assume the CSP is “honest-but-curious”’. In this model, the CSP would fulfill its duties as a service provider by following the designated protocols and procedures honestly. At the same time, the CSP is curious and it may collect and analyze the data uploaded by users to obtain some additional information. In this paper, we consider two threat models Known Ciphertext Model and Known Background Model. They have been introduced in other related works[3,4].

(Ⅰ) Known ciphertext model. In this model, the CSP or adversaries has the full access rights to encrypted files, encrypted indexes, and encrypted queries uploaded by data users and data owners. Besides, the CSP or adversaries will record the results of each search request in an attempt to get useful information from them[10].

(Ⅱ) Known background model. The CSP or adversaries in this model can get additional background information, such as the similarities or differences between two given queries. Combined with background information, the CSP or adversaries can analyze the similarity between the target index and the known index, even can determine whether a certain keyword is in the index with a high probability. Specially, the CSP or adversaries cannot obtain the plaintext- ciphertext pair available for query as users’ secret key are not available.

2.3 Design goals

In this paper, our scheme intends to achieve efficient fuzzy search in multi-user multi-keyword scenario. Therefore, our design has the following security and performance goals.

(Ⅰ) Multi-keyword fuzzy search with wildcard enable. Our multi-keyword fuzzy search scheme should support not only common misspelling but also wildcard search that tolerates more types of spelling errors. For example, the file which have a index information, secure should be returned for a wildcard query with keywords “se*re, informa*”.

(Ⅱ) No predefined dictionary. No predefined dictionary is a standard requirement of existing schemes, so our scheme should also not have a predefined dictionary.

(Ⅲ) High result accuracy. Our scheme is to provide users with keyword search function over ciphertext, so it is necessary to ensure high accuracy.

(Ⅳ) Less computational overhead in multi-user scenario. The computing overhead of users in our scheme should be significantly reduced, which means data user should encrypt an index for only one time when searching multiple repositories.

(Ⅴ) Privacy guarantee. The CSP or external adversary should be prevented from obtaining any additional information from encrypted indexes, encrypted queries or search results. Besides, the query information of different users should also be confidential to other users.

3 Preliminaries

3.1 Bloom filter

Bloom filter is proposed by Bloom in 1970[11], which is widely used to determine whether an element belongs to a collection. Bloom filter is initialized as am-bit bit arrayAof with all bits set as 0. Given a setS={a1,a2,…,an} , bloom filter inserts each elementai∈Sinto the bit array. It useslindependent hash function:H={hj|hi:S→[1,m], 1≤j≤l} to set thehj(ai)-th bit in the array to 1. Testing whether a setShas the elementq,qwill be mapped tolpositions by calculatinghj(q), 1≤j≤l. If any of bit value corresponding to theselpositions equals 0, it meansq∉S; otherwise, it means eitherq∈Sorqproduces a false positive. Figure 2 is a simple example, where “x” and “y=b” can both be considered as an element in the set where “a”, “b” belong to, but actually “x” is not such an element. For more details, References[12,13] are good references.

Following the analysis of Reference[11], the false positive probabilityfis

(1)

wherenis the number of elements expected to be stored in the bloom filter,lis the number of hash functions used to implement the bloom filter, andmis the length of the bloom filter. Based on the excepted number of elements and false positive probability, we can choose the length of bloom filtermand number of hash functionslas Equation1.

3.2 Permuterm index

Permuterm index is a common index structure used to deal with wildcard query, such as the query with keywords “*earch”, “se*rch”, “searc*”. Here “*” represents characters of any length. To generate the corresponding permuterm index for a keyword, a character “” are added to the end of the keyword to present the ending. Then the keyword will be rotated bit by bit. For the keyword with a wildcard character “*” in it, the permuterm index will be the string, of which the end is “*”. For the keyword without a wildcard character, the index will be the set of all the possible string generated by rotation. Now we use two specific examples to explain the establishment of permuterm index. Keyword “model” will be transformed into “model”, “odelm”, “delmo”, “elmod”, “lmode”, and keyword “mod*l” will be transformed into “lmod*”.

3.3 Secure KNN

Secure KNN was proposed by Wong et al[14]solving the problem of KNN computation on an encrypted database. KNN algorithm is mainly used to search in a point set to find out k nearest points to a given point q. As the distance between two points can be computated as the product of their coordinate vector, secure KNN set the encryption secret key as a matrix and the decryption key as the inverse of the matrix, can be offset in distance comparison. Here is a brief introduction to the process of the secure KNN.

(Ⅰ) Key generation(n)→κ. The key generation algorithm takes the length of the coordinate vectornas the input and returns a invertible matrixMn×nas the secret keyκ.

(Ⅱ) Coordinate vector encryption(κ,P)→Eκ(P). Given the coordinate vector of a pointP=pn×1and the secret keyκ, the encrypted pointEncκ(P)=MT·pwill be returned.

(Ⅲ) Query encryption(κ,Q)→Encκ(Q). This algorithm takes a query pointQ=qn×1, which is also a n-dimensional vector, and the secret keyκas inputs. Then it outputs the encrypted pointEκ(Q)=M-1·q.

(Ⅳ) Distance comparison(Eκ(P1),Eκ(P2),Eκ(Q))→Ture or False. Given encrypted points and query pointEκ(P1),Eκ(P2) andEκ(Q), the system calculate whether (Eκ(P1)-Eκ(P2))T·Eκ(Q)>0 to determine whetherP1is nearer to the queryQthanP2.

3.4 Proxy re-encryption

Proxy re-encryption is an encryption technology that can transform a ciphertext encrypted by Alice to the ciphertext under Bob’s key without decrypting. It was proposed by Blaze et al[15]and formally defined by Ateniese et al[16]. In a general proxy re-encryption scheme, there are five polynomial time algorithms KenGen, ReKey, Encrypt, ReEncrypt, Decrypt, here is a brief introduction to the process of the Proxy re-encryption.

(Ⅰ) KeyGen(1k)→(pki,ski). Given the security parameter 1k, the KeyGen algorithm takes a key pair (pki,ski) as the output.

(Ⅱ) ReKey(pkA,skA,pkB,skB)→rkA→B}. The ReKey algorithm takes two key pairs (pkA,skA,pkB,skB) as the input, and a re-encryption keyrkA→Bwill be returned.

(Ⅲ) Encrypt(pki,m)→ci. This algorithm takes user’s public keypki, and a messagem∈Mas inputs. Then it outputs the ciphertextci.

(Ⅳ) ReEncrypt(cA,rkA→B)→cB. Given a ciphertextcAand corresponding re-encryption keyrkA→B, the ReEncrypt algorithm will returncBas output.

(Ⅴ) Decrypt(ski,ci)→m. Given user’s secret keyskiand ciphertextci, the Decrypt algorithm outputs the messagemor a error symbol ⊥ indicated that the ciphertextciis illegal.

4 Basic construction of our scheme

4.1 Overview

In our scheme, to achieve fuzzy search, all the keywords in both queries and indexes need to be transformed into permuterm indexes. The system starts with system intialization. Before DOs upload their files, they first generate corresponding index for each file, which consists of multiple keywords. After keyword transformation, DOs directly store the permuterm indexes to bloom filter, which can increase the accuracy rate in multi-keyword scenario. Then they encrypt and upload corresponding bloom filter together with files they own to CSP. In order to efficiently support the multi-user scenario, upon receiving the uploaded files and indexes, CSP will re-encrypt the bloom filters, and then store them to wait for querying. Similarly, when DUs want to access some files, they first generate related keywords, and then transform them into permuterm indexes, which are stored in a bloom filter. After DUs send encrypted bloom filter as query, CSP will re-encrypt this bloom filter, and return the files of which have the matching encrypted bloom filter.

We will introduce the details of our whole construction in the following subsections, which includes system initialization, keyword transformation, index generation, index encryption, index conversion, query generation and search.

4.2 System initialization

4.3 Keyword transformation

For a file setF={f1,f2,…,fn} , DO first extracts keywords from each file. Then he/she transforms keywords into permuterm indexes. The strings in these indexes are finally split into the corresponding substrings, which will represent the index of each file by combining with the length of the original keywords. The details of the process is shown in line 2-11 of Algorithm 4.1. The rotate(s,i) in the algorithm represents the function to rotate stringsforibit.

Algorithm 4.1Keyword transformation and index/query generation

Output: The index/query for a fileB;

1 for each word in K do

2 L=len(word);

3 if ‘*’ in word then

4 word=replace( ‘*’, ‘’);

6 gram=out. split();

7 else

9 for i in range( len(s)-5, 0, -1) do

10 out=rotate(s, i) + L;

11 gram=out. split();

12 for each element in gram do

13 for i=1 to l do

14 seat=hl(element);

15 B[seat]=1;

16 Return B.

As an example, the permuterm index for “fuzzy” is “fuzzy”, “uzzyf”, “zzyfu”, “zyfuz”, “yfuzz”. Then, the final representation is {“fuzzy5”, “uzzy5”, “f5”, “zzy5”, “fu5”, “zy5”, “fuz5”, “y5”, “fuzz5”}. In such a way, a wildcard keyword like “tur*” or a misspelled keyword like “fuzsy” can still be represented in a unified way with an accurate keyword and matched with “ture” and “fuzzy”, as shown in Figure 3.

4.4 Index generation

As keywords of an index are transformed into a substring-based set, we uselindependent hash functions,H={hi|hi:S→[1,m], 1≤i≤l}, to hash each substringsin the set with the lengthLof the original keyword together. For each keyword, we will havelpositionshi(s|L) and set corresponding positions in the m-bit bloom filter to 1, which is shown in line 12-15 of Algorithm 1. In this way, each file has an bloom filter as the index, which is shown at the bottom of Figure 3.

4.5 Index encryption

The entire encryption process in our scheme can be divided into two parts, i.e., the encryption of index at owner side and the re-encryption at CSP side. The process enables the indexes encrypted different keys to converted into indexes encrypted by the same key, i.e.,SK, as shown in Figure 4. Users first use their own keys to encrypt indexes as the process of encrypt in Figure 4, then CSP convert the ciphertext under user’s key to the ciphertext under the unified key as the process of re-encrypt in Figure 4.

Figure 3. Keyword transformation and index/query generation.

Figure 4. Encryption of Index.

(2)

whereα1,α2,…,αm-1∈h.

Then, DO encrypts the index using Equation (3), and outsources the encrypted index and encrypted file to CSP. The method to encrypt files is not in the scope of our paper.

(3)

Here,Γ∈l,is an integer error vector randomly selected from some probability distributionsχ∈l.

4.6 Index conversion

After obtaining encryptedEMO, CSP re-encrypts it using Equation(4), making it encryted by M. Then CSP store it.

(4)

4.7 Query generation

(5)

whereβ1,β2,…,βm-1∈h, andγ∈pis a positive integer.

(6)

4.8 Search

Upon receiving the search queryTQUfrom DU, CSP first conducts query conversion. Specifically, it convertsTQUto be encrypted under M-1by re-encrypting it with the corresponding switch key MU′ shown as

(7)

Correctness Guarantee: Provided two different encrypted queries, we can compare the similarity between these two indexes and the given query. Since we use the same bloom filter mechanism to generate these query and indexes, the same keyword information will be stored in the same set of each bloom filter. So the repetition of the keyword sets directly affects the distance between the bloom filters and the distance between two bloom filters, that is, the distance between two vectors, is commonly defined as Euclidean distance. So the correctness guarantee for searching holds as follow:

(8)

5 Security analysis

Inspired by Fu’s work, we will analyze the security of our scheme and give a security proof in detail for known ciphertext model and known background model. Before the proof, we give some notations here.

(Ⅰ) History,H=(F,I,Q). An interaction between the users and CSP can be defined as history. A history can be regarded as an instantiation of such an interaction, including a file set to be searched, searchable indexes and a set of words that DU wants to search for.

(Ⅱ) View,V(H)=(Enc(F), Enc(I), Enc(I)). Then during a query, what CSP or adversaries can actually obtain we call as the history’s view. view is generated by encrypting a history with users’ secret key. Additionally, CSP or adversaries can obtain some common information, such as the number of files stored in CSP.

(Ⅲ) Trace of a history, Tr(H)=Tr(q1), …, Tr(qk). A trace of the historyHis the set of the trace of queries Tr(H)=Tr(q1), …, Tr(qk) consisting the sensitive information. Specifically, Tr(qi)={(δj,sj)qi⊂δj,1≤j≤≤|F|} , wheresjis the similarity score between the queryqiand the fileδj.

5.1 In known ciphertext model

Theorem 5.1Our scheme is secure under the known ciphertext model.

ProofFirstly, we need to prove the confidentiality of index/query under the known ciphertext model.

(9)

5.2 In known background model

Under the known background model, CSP or adversaries are able to gain a certain number of index and query pairs. They will infer the indexes stored in CSP by matching the known indexes, or analyze the difference of search result by operating multiple queries on the same index. Meanwhile, CSP or adversaries will obtain selected background information such as a certain amount of the keyword and query pairs and try to recover the encrypted indexes through linear analysis. Intuitively, CSP or adversaries cannot distinguish simulator’s view from the view he owns. So if a simulator can generate an indistinguishable view, we can say that our scheme is secure under the known background model.

Theorem 5.2Our scheme is secure under the known background model.

ProofFirst of all, Yao et al[18]found that if the adversary gets enough ciphertext and corresponding plaintext, he can obtain some information through linear analysing. However, the adversary in our scheme cannot obtain plaintext-ciphertext pair in the known background model. In our scheme, after transforming keywords to vector, it will be extracted with extraction parameters. And these parameters are kept as secret by users. Therefore, even the adversary can obtain some keyword sets, he still cannot get any information through linear analysing under the known background model.

In addition, in order to prove our scheme is secure under the known background model, we denoteSas a simulator that can simulate a viewV′ which is indistinguishable from CSP’s view . Then we construct the simulator as follows:

(Ⅰ) we generateF′,Sselect aδi′∈{0,1}|δi|,δi∈F,1≤i≤≤|F| randomly, and outputsF′={δi′,1≤i≤|F′|} .

The construction is correct since the search result onI(F′) with the query EncM′-1(Q′) is same as the trace which CSP has. Because the hash functions in bloom filter are indistinguishable, the adversary cannot distinguish the output of the linear analysis from a random string. We claim that no probabilistic polynomial-time (P.P.T.) adversary can distinguish the viewV′ fromV(H).

5.3 Privacy preservation in multi-user scenario

In multi-user scenario, different DUs will make queries in the same repository at the same time. These DUs should not be able to know the corresponding queries of other DUs, which can not be guaranteed in some schemes[3,4].

In our scheme, the queries from different DUs for the same repository are encrypted under their own keysMOθas Equation(6). So, even if a DU obtains other DUs’TQUθ, he/she is still not able to decrypt these queries. After receiving DUs’TQUθ, CSP will convertTQUθtoTQas Equation(7) which is encrypted underSK=M-1. And nobody hasSKto decryptTQexcept TA.

Therefore, our scheme can achieve privacy preservation in multi-user scenario.

6 Performance evaluation

In this section, we evaluate the performance of our scheme by implementing our system in PYTHON on a Windows 10 server. We use RFC (Request For Comments) database (RFC)[19]as our data set. We choose approximately 1000 files as our experimental data. In the experiments, we set the false positive probabilityfto 0.01 for the bloom filter. Then, the 20 most frequently occurring words are set as the keywords of files. Meanwhile, the top 10 files will be returned as the final result. Next, we conduct a detailed analysis through our experimental data.

6.1 Comparison

In this subsection, we summarize and compare the existing fuzzy search schemes, of which the results are shown in Table 1. We can see that schemes in References [3,4] use secure KNN to encrypt the index including all the keywords for each file. However, schemes in References [5,6] choose to encrypt letters or substrings of a keyword by Homomorphic encryption supporting wildcard query. Encrypting letters or substrings makes schemes[5,6]to support wildcard queries, but this also leads to the scheme only supporting single keyword search. Due to the encryption based on keywords in References [3,4], these schemes can be applied in multi-keyword scenario, but they are unable to support wildcard query. It is noted that all the existing fuzzy search schemes cannot support the multi-user scenario.

Table 1. Comparison with other fuzzy search schemes.

Table 2. Comparison of the Computational Overhead for One Time Search.

The encryption in our scheme is also based on all the keywords in indexes, we introduce a new keyword transformation method to make our scheme able to support both of wildcard query and keyword misspelling. In particular, we apply an improved secure KNN so that our scheme can support multi-user scenario. In summary, only our scheme can support multi-keyword scenario, wildcard query, multi-user scenario simultaneously.

6.2 Efficiency

Now we assume that a DU makes a query for each of thenDOs, where each index/query hasrkeywords, the average length of all the keywords isL, and the number of hash functions used in bloom filter isl. The computational overhead of index/query generation isrl*Hin Wang’s and Fu’s schemes. But in our scheme, since we introduce the permuterm index, DO/DO needs to conduct extraLtimes rotation operations during index/query generation. Since the secure KNN we apply is more efficient than that adopted in Wang’s and Fu’s schemes, the index encryption only hasm*Dm. But in multi-user scenario, DU in Wang’s and Fu’s scheme needs to conductntimes encryption on the query for different DOs, therefore the overhead of query encryption is much larger than that in ours scheme, which is 2nm*Dm. In our scheme, to achieve efficient fuzzy search in multi-user scenario, CSP needs to conduct index and query conversion uponding receiving corresponding ciphertext, of the overhead ism*Dm,nm*Dmrespectively. But the compared schemes do not have these steps. For the search step, Wang’s and Fu’s schemes have the same computational overhead, which is 2n*Dm. And the computational overhead for the search step in our scheme isn*Dm. We list the detailed analysis results of the computational overhead in Table 2.

(Ⅱ) Experimental results of computational overhead. Figure 5 shows running time of the keyword transformation, index generation, index encryption, index convertion and search.

Figure 5. The computational overhead of our scheme.

Because the index structure in our scheme is a per file-based index, each file needs to generate an index and the generation time increased linearly with respect to the number of files. And the running time of index encryption and index convertion are also linear in the number of files. From Figure 6(a), we can see that when the number of files is 1000, the running time of keyword transformation and the index generation are 1.71 seconds and 2.73 seconds, respectively. The key transformation includes word frequency statistics and the generation of substring set. And the running time of search is mainly affected by the number of files. When the number of files is 1000, the search time is approximately 4.3 seconds. Figure 6(b) shows the running time of index encryption and index convertion are also linear in the number of files which are only one-time efforts.

Figure 6. The performance matrices of accuracy with respect to the number of query keywords.

6.3 Result accuracy

(Ⅰ)The affection of the number of query keywords. Figure 6 shows the trend of accuracy rate with respect to the number of query keywords when there is one fuzzy keyword in each keyword set.

From Figure 6, it’s not hard to see that the search accuracy rates of our scheme are higher than those of the other two schemes when the number of keywords larger than 2, which is always above 95%. The reason for the accuracy improving in our scheme is mainly the use of the new method for index generation.

(Ⅱ) The affection of the number of fuzzy keywords. In order to observe the relationship between the number of fuzzy keywords and the search accuracy, we considered two cases with 5 and 10 query keywords respectively, of which the results are shown in Figure 7 and Figure 8. In Figure 7, due to the number of query keywords is small, the overall accuracy rate shows a downward trend. But our scheme’s accuracy rate decreases much more slowly than Wang’s and Fu’s schemes. And the accuracy rate of our scheme is still acceptable when other two schemes could not return the correct result. In the case with 10 query keywords, the accuracy rate of our scheme appears a turning point when the number of fuzzy keywords reaches 7, which is shown in Figure 8. Then, the accuracy rate of our scheme is gradually reduced and reaches the minimum value of 70% when all keywords are fuzzy keywords. While the accuracy rate of other two schemes is decreased from 100% to 10% sharply as the number of fuzzy keywords is increased from 6 to 10.

Figure 7. The accuracy rates with respect to the number of fuzzy keywords in the case of 5 query keywords.

Figure 8. The accuracy rates with respect to the number of fuzzy keywords in the case of 10 query keywords.

(Ⅲ) The affection of the type of fuzzy keywords: We first compare our scheme with schemes[3-6]in terms of the capabilities of dealing with all possible types of fuzzy keywords, which is illustrated by Table 3. “yes” means that the index keyword and the query keyword can be matched, and “no” means that they can not be matched. We can see that wildcard query keyword like “im*vement, improv*, *provement” can be solved in our scheme, Kim’s scheme, and Yang’s scheme. General spelling error like “imprvoement, imprdvement” can be solved in our scheme, Wang’s scheme, and Fu’s scheme. And keywords composed of the same letters in different order like “thing, night” can be distinguished in our scheme and Fu’s scheme. In summary, other schemes are only able to deal with a subset of keywords while our scheme is able to deal with all types of fuzzy keywords.

Table 3. Different Types of Fuzzy Keyword.

Then, we measure the accuracy rates when keywords are displayed in different forms, including replacing letters (RL), wildcard query (WQ), and reversing the order of two letters (ROTL). The results are shown in Figure 9. In this part, we set at least 4 fuzzy keywords in a query. In the case of ROTL, we randomly select two keywords and exchange the two letters in each keyword, e.g., from “program” to “prgoram”. The accuracy rates grow from 75% to 90% as the number of query keywords is increased from 4 to 6, and then it stays at 95%. And in order to simulate RL, we randomly choose several letters and replace them with other letters for each keyword. The general trend of RL is the same as that of ROTL. There is a growth period as the number of keywords is increased from 4 to 6, and a stable period from 6 to 10. Meanwhile, RL performs better than ROTL when the fuzzy keywords account for a large proportion. When the number of accurate keywords are more than that of fuzzy keywords, the accuracy of ROTL is higher. As for the case of WQ, we randomly replace several letters with wildcard character “*”. Different from RL and ROTL, the accuracy rate of WQ always stay above 90% as the number of keywords is increased from 4 to 10. Obviously, the accuracy rate of WQ is not affected by the proportion of fuzzy keywords, and it always maintains high accuracy.

Figure 9. The accuracy rates with respect to the types of fuzzy keywords.

The reason for such results is that keyword transformation in our scheme is the permuterm index which is aimed at wildcard query. From these three kinds of fuzzy search, we note that the correct results can be returned when the proportion of fuzzy keywords is more than 50%. And our scheme is the most suitable for the wildcard query.

According to the above experiments, we can draw a conclusion that our scheme is able to maintain high precision in various cases.

7 Relate work

7.1 Searchable encryption

The first construction of searchable encryption[20]was proposed by Song et al. in 2000. On this basis, a lot of work is committed to designing an effective searchable encryption scheme. Cash et al[21]proposed a scalable symmetric searchable encryption (SSE) scheme to support boolean query. To improve the search experience, the multi-keyword rank searchable encryption (MRSE) mechanism is proposed[22-25]where CSP can return the top-kresults according the similarity of keyword sets. At present, the research direction of searchable encryption can be roughly divided into the functional improvement of public key encryption with keyword search (PEKS) and the dynamic security of symmetric searchable encryption (SSE)[26-29]. Existing schemes of PEKS mainly focus on multi-keyword search[7,30]and authorized keyword search[31-35].

7.2 Fuzzy search over encrypted data

Noteworthy, the above schemes only support accurate keyword searches. Thus many attentions have been drawn to fuzzy keyword search over encrypted data. Concretely, the first work[36]focusing on fuzzy search over encrypted data exploited edit distance to quantify keywords similarity between the predefined extend keyword set and the fuzzy keyword. But it only supports the single keyword fuzzy search and needs to predefine extend keyword set. Reference [3] proposed a multi-keyword fuzzy searchable encryption scheme without a predefined fuzzy set.In their work, a keyword is first transformed into a substring set containing the bi-grams of the keyword and evaluate keywords similarity according to the Euclidean distance. For example, the substring set of “fuzzy” is {“fu”, “uz”, “zz”, “zy”}. The problem of this approach is that it’s only able to solve the mistakes with only one letter misspelled. To improve the tolerance of misspelling, Fu et al[4]designed a new method of keyword transformation. Differently, the keyword “fuzzy” is represented as {“f1”, “u1”, “z1”, “z2”, “y1”}. And schemes in References [5,6] introduce wildcard to represent any character in order to tolerate more complicated keyword misspelling. In their work, they choose to split up the keyword and encrypt the substrings of each keyword by homomorphic encryption. Obviously, the computational overhead of these two schemes is extremely high and their work can only solve wildcard query. Therefore, how to improve the fault tolerance and accuracy while bringing less computational overhead is the main problem in fuzzy search over encrypted data.

7.3 Searchable encryption considering multi-user set

In cloud storage scenario, multiple users upload and download files, the access permission between data owners and data users is a many-to-many relationship. For the calculation between query and index, data users must encrypt their queries under the corresponding key of the data owner. The data owner has to share his/her secret key with data users to support keyword searching, which may lead to privacy disclosure. Meanwhile, it is necessary for data users to encrypt the same query index multiple times for different files from different data owners, which greatly increases the overhead of communication and computation.

Regarding the above challenges in the multi-user setting, many efforts have been made on the searchable encryption by applying a new encryption algorithm[7-9]. Yang et al applied a new homomorphic encryption scheme in a traditional keyword searchable encryption scheme[7], where the calculation result of data encrypted by different keys can be decrypted by the sum of two keys. Considering image retrieval in the multi-user scenario, the scheme in Reference [8] applies an improved encryption algorithm to encrypt images. As for Reference [9], Cheng et al solved the problem of multi-key searchable encryption in database. Based on homomorphic encryption, they introduced two cloud to conduct collaborate computing, ensuring the computability and privacy of data. However, these schemes cannot efficiently or effectively be applied to fuzzy search.

8 Conclusion

In this paper, we proposed a multi-user multi-keyword fuzzy search scheme over encrypted cloud storage. We utilized permuterm index to design a new keyword transformation method, which enables our scheme to achieve wildcard query, making the scheme able to deal with more varieties of misspellings in keywords. By replacing the LSH used in the bloom filter to standard hash function, our scheme improves the accuracy rate when there are multiple fuzzy keywords. Moreover, our scheme adopts a new efficient key conversion protocol where encrypted indexes and queries are re-encrypted by CSP. In such way, our scheme can achieve efficient fuzzy search in the multi-user scenario. Through comprehensive security analysis and the experiments on real data set, we demonstrated that our scheme is efficient, effective, and feasible in the area of searchable encryption.

Acknowledgments

This work is supported in part by the National Natural Science Foundation of China (61972371) and Youth Innovation Promotion Association of Chinese Academy of Sciences (CAS) (Y202093).

Conflictofinterest

The authors declare no conflict of interest.

Authorinformation

LingHuazereceived her bachelor’s degree from the School of Computer Science and Technology, Hefei University of Technology in July, 2018. She is currently a graduate student in Information Security from the School of Cyber Security, USTC. Her research interests include Network security and Cryptography.

XueKaiping(M’09-SM’15)received his bachelor’s degree from the Department of Information Security, University of Science and Technology of China (USTC), in 2003 and the PhD degree from the Department of Electronic Engineering and Information Science (EEIS), USTC, in 2007. From May 2012 to May 2013, he was a postdoctoral researcher with the Department of Electrical and Computer Engineering, University of Florida. He is currently a Professor with the School of Cyber Security and the Department of EEIS, USTC. His research interests include future Internet architecture, transmission optimization, distributed networks and network security. He is a fellow of the IET and a senior member of the IEEE. He serves on the Editorial Board of several journals, including the IEEE Transactions on Wireless Communications and the Ieee Transactions on Network and Service Management.

WeiDavidS.L.(SM’07) received his PhD degree in Computer and Information Science from the University of Pennsylvania in 1991. From May 1993 to August 1997 he was on the Faculty of Computer Science and Engineering at the University of Aizu, Japan. He has authored and co-authored more than 100 technical papers in various archival journals and conference proceedings. He is currently a Professor of Computer and Information Science Department at Fordham University. His research interests include cloud computing, big data, IoT, and cognitive radio networks. He was a guest editor or a lead guest editor for several special issues in the IEEE Journal on Selected Areas in Communications, the Ieee Transactions on Cloud Computing and the IEEE Transactions on Big Data. He Also Served as an Associate Editor of Ieee Transactions on Cloud Computing, 2014-2018, and an Associate Editor of Journal of Circuits, Systems and Computers, 2013-2018.

LiRuidong(SM’07) is an associate professor in College of Science and Engineering, Kanazawa University, Japan. Before joining Kanazawa University, he was an a senior researcher with the Network System Research Institute, National Institute of Information and Communications Technology (NICT). He received a bachelor in engineering from Zhejiang University, China, in 2001. He received a doctorate of engineering from the University of Tsukuba in 2008. He is the founder and chair for the IEEE SIG on big data intelligent networking and IEEE SIG on intelligent Internet edge. He also serves as the chairs for conferences and workshops and organized the special issues for the leading magazines and journals. His current research interests include future networks, big data networking, blockchain, information-centric network, internet of things, network security, wireless networks, and quantum Internet. He is a senior member of the IEEE and a member of IEICEasd.