Yilun Wu , Xicheng Lu , Jinshu Su ＊, Peixin Chen , Xiaofeng Wang , Bofeng Zhang

1 College of Computer, National University of Defense Technology, Changsha 410073, China

2 National Laboratory for Parallel and Distributed Processing, National University of Defense Technology, Changsha 410073, China

* The corresponding author, email:sjs@nudt.edu.cn

I. INTRODUCTION

The rapid growth of cloud users has affirmed that cloud storage services are becoming the inseparable part of people’s life. Users can enjoy a more convenient and cost efficient storage environment than maintaining a local storage infrastructure. Despite the fact that cloud storage services provide huge convenience for users, data confidentiality and privacy will be put at risk when users outsource the data to a remote cloud server. Naturally, encrypting the data before outsourcing is a solution to protect data privacy. However, this will make data utilization, such as keyword search, a very challenging task [1].

To enable users to quickly sort out the information of interests from large encrypted data, searchable encryption has been proposed and enriched by many schemes [2-4]. Instead of decrypting the whole data, these schemes allow users to search over the encrypted data and only decrypt the corresponding files.Subsequently, some following searchable encryption schemes [5-9] have been proposed to solve the problems caused when the data owner shares the data with multiple users.This scenario, referred to as multi-user setting, requires the data owner to delegate the search ability to data users via secure channels. Besides that, these schemes enrich the functionalities of searchable encryption, such as fuzzy keyword search [5], ranked keyword search [6], multi-keyword search [7], etc.Furthermore, some schemes [8,9] improve the searchable encryption by combining two or more functionalities together. However, these schemes share some limitations.

In this paper, the authors propose a novel public key based keyword search scheme to support multi-owner keyword search without secure channels.

First, most of the existing schemes only consider the scenario of a single data owner.Rather than only one data owner, most cloud providers in reality serve multiple data owners who are able to share their data with each other. Since the data sharing is becoming increasingly important on the user side, how to let data users quickly and securely find out the information of interests from multiple data owners’ data becomes a challenge problem. Due to the massive transmissions of secret keys, it is not reasonable to directly extend the existing schemes from one data owner to multiple data owners.

Second, the data owner needs to establish a secure channel for each data user, which is used to prevent the transmitted secret information from being revealed. Since resources of the data owner are limited, it is expensive to establish plenty of secure channels if the number of data users is large. Some schemes [10-12] based on public key encryption have been proposed to remove secure channels from searchable encryption. Despite of the removal of secure channels, these solutions are still far from being deployed in a real public cloud.In these schemes, the data owner has to encrypt each keyword for each user, which will dramatically increase the resources consumption when the number of data users is large.Besides that, some existing schemes [13,14]require the data owner to stay online to help data users search over the remote encrypted data. It is very inconvenient that data users cannot perform keyword search in their time of needs when the data owner is offline, even if they possess secret keys or trapdoors. Moreover, if many data users request the search at the same time, the data owner will undertake heavy computation and communication load.It is very impractical because the resources of any user are considered as limited in cloud.

To solve the aforementioned problems,we propose a novel searchable scheme which considers the scenario in multi-owner setting without secure channels. Each data owner can enjoy sharing his own data and delegating the ability of search to data users in the cloud without sending secret key to each data user.Instead, the cryptographic primitive called proxy re-encryption is utilized to help data owners delegate the ability of search to data users via the cloud server, without revealing any additional information. More than that,our scheme is a non-interactive keyword search solution, which means that there is no interaction between data owners and data users. More precisely, in the whole process of our scheme, each user only need to communicate with the cloud server. We summarize our main contributions as follows.

First, we consider the scenario of multiple data owners and propose a novel scheme to enable keyword search in a group. Each member in the group could be a data owner,as well as a data user. Meanwhile, our scheme supports dynamic user adjustment in group,including user addition and user revocation.Second, our proposed scheme does not rely on secures channels. Neither secret keys nor trapdoors will be transmitted in our scheme.Moreover, our scheme can still guarantee the secure keyword search under insecure channels. Furthermore, our scheme terminates interactions between data owners and data users,which will dramatically improves the user experience. Third, we evaluate the performance of our scheme, which is distinguished from most of the public key based keyword search schemes.

II. RELATED WORK

Since Song et al. [2] presented the first practical searchable encryption scheme, many follow-up schemes have been proposed in the literature [3,4,20-22]. All these scheme only allows the data owner to search over the encrypted data, which are not inappropriate for data sharing services in the cloud. In light of this problem, some schemes [5-9,19] have been proposed to support multi-user searchable encryption, implying that the data can also be searched by authorized users. To delegate the search ability, the data owner requires a secure channel to transmit some secret information, such as the secret key or the trapdoor,to each data user. Considering the cost of building the secure channels, Beak et al. [10]proposed the first scheme, referred to as secure channel free searchable encryption (SCFPEKS), aiming to remove the secure channels from searchable encryption. Rhee at al. [11]introduced an enhanced security model and constructed a scheme in this model. To improve the efficiency, Gu et al. [12] presented a novel SCF-PEKS scheme without pairing operation. If there are many data owners who are willing to share their data with each other, a new searchable encryption is required. For the solutions with secure channels, each data owner has to establish a secure channel with a data user, and transmits the secret information via the channel. It means that the both the computation overhead and communication overhead increase with the number of data owners. For the SCF-PEKS schemes, each data owner has to encrypt each keyword for each data user.The computation overhead and storage overhead will increase not only with the number of data users, but also with the number of keywords. Therefore, it is significant to design a searchable encryption without secure channels in multi-owner setting.

III. PROBLEM STATEMENT

In this section, we describe the formulation of our scheme, including a system model, the corresponding security model and our design objectives.

3.1 System model

The system model consists of three entities:the manager,usersandthe cloud server. In our scheme, we consider that the manager is an initiator who creates a group. The manager takes charge of the group management,including adding a new user and removing a revoked user. Each user in the group is considered as an authorized user, which means that the user simultaneously plays two roles: a data owner and a data user. As a data owner, the user can share his encrypted data with other authorized users in the group. And as a data user, the user can search over the encrypted data of others in the group. After the manager permits a new user to join the group, the new user needs to upload the public key to the cloud server. Then the manager publishes a notification to the cloud server, which informs each authorized user to download the public key of the new user and generate a re-encryption key for the new user. After that, the new user can enjoy searching over the encrypted data of others in the group. Analogously, to enable the authorized users to search over the data of the new user, this new user needs to generate a re-encryption key for each authorized user and uploads these keys to the cloud server. To revoke an user from the group, the manager only needs to request the cloud server to delete all the re-encryption keys related to the revoked user. Since our scheme utilizes the proxy re-encryption technique to delegate the ability of search from data owners to data users, no secret key will be transmitted under the transmission channels, which implies that the secure channels are not necessary in our schemes. This is equivalent to saying that data owners can delegate the search ability to data users via the cloud server instead of directly interacting with data users. Each data owner generates a secure index and encrypts the data only using his secret keys and the public key of the cloud server. If the user performs a search, he only needs to use his secret key to generate a trapdoor.

3.2 Security model

In this work, we consider that there is no secure channel in our system. All the information transmitted can be intercepted by an adversary who can eavesdrop on transmission channels. It means that no secret information is allowed to be transmitted via transmission channels. Meanwhile, we consider the honest but curious cloud server like most of the existing works. The cloud server will honestly follow our proposed protocol, but curiously try to learn as much additional information as possible from the obtained data. It is worth noting that we ignore the collusion between the cloud server and revoked users. In addition,no authorized user will help the cloud server find out additional information. Moreover, the cloud server will not help revoked users to keep the privilege which they ever owned in the group.

3.3 Design objectives

Our scheme aims to achieve the following objectives.

1) Security.Even in the environment without secure channels, our scheme should still prevent the cloud server from learning additional information, and keep the contents of the documents, the keywords in the index, and the keyword in trapdoors as secret.

2) Efficiency.Our scheme should achieve an acceptable efficiency from a user’s perspective.

3) Efficient User Adjustment.Our scheme should assure that the user adjustment is efficient and secure. Only the authorized users can perform the search over the encrypted data shared in the group. The revoked users will lose the privilege of the search.

IV. NOTATIONS AND PRELIMINARIES

4.1 Notations

●a dictionary ofDithat containsmkeywords.

●Ii: a secure index ofDiincluding keywords inWi.

●T: the trapdoor for a query keyword.

4.2 Preliminaries

1) Bilinear Map:Letandbe two cyclic groups of a large primep. Letgbe a generator ofA bilinear map can be defined asif the following three conditions hold.1)Bilinear: for any2)Non-degeneracy:3)Computability: Givencan be efficiently computed.

2) Symmetric Key Encryption:A symmetric key encryptionSKEis a triple ofPPTalgorithms:

SKE.Gen(1k)→K: Inputs a security parameter 1k, the key generation algorithmSKE.Genoutputs a keyK.

SKE.Enc(K,m)→c: Inputs a keyKand a messagem, the encryption algorithmSKE.Encoutputs a ciphertext.

SKE.Dec(K,c)→m: Inputs a keyKand a ciphertextc, the decryption algorithmSKE.Decoutputs a message.

V. DETAILS OF OUR SCHEME

In this section, we describe the details of our proposed scheme. The entire process of our schemes contains six main phases:System Initialization,Re-encryption Keys Collection,Data Setup and Outsourcing,Trapdoor Generation,SearchandDocuments Retrieval. Finally, we explain how to add in a new user and remove a revoked user.

5.1 System initialization

The cloud server takes a security parameterto generate two cyclic groupsandwith the same prime orderp, havinggas a generator of. Letbe a bilinear mapThen, the cloud server chooses a hash functionFinally, the cloud server randomly choos-es a secret valueand computesThus, the global parameter is

AfterGPhas been generated, each userinUrandomly selects two valuesand computesThen the user keepsas secret and publishesto the cloud server.

5.2 Re-encryption keys collection

In order to delegate the search ability to other users inU, userUineeds to generate a re-encryption key for each user. First,Uidownloads public keysfrom the cloud server, and computes the re-encryption key set. UserUithen uploadsto the cloud server. The cloud server constructs a matrix to store each received set. Table 1 shows an example of the matrix with four users.

5.3 Data setup and outsourcing

Before outsourcing the document collectionDito the cloud server, and userUi, which is considered as the data owner, needs to build a secure index. Then,Uihas to encrypt the data.Assume that the data ownerUihas already extracted a dictionaryWiofDiwhich containsmkeywords.

1) Index Generation:Uicomputes token

for each keywordwinWi. Then the data owner creates an identifier setIDwof the documents that contains the keywordw. After that, the data ownerUiutilizesto encryptIDwby applying symmetric key encryption:

Finally, the secure index can be constructed as:

2) Data Encryption:To encrypt the data to be outsourced, userUifirst chooses a random valuerDfrom, and generates a key:

3) Outsourcing:After everything is ready,the data ownerUioutsources {Ii,Ci,K′D} to the cloud server, and deletes the outsourced data in local storages.

5.4 Trapdoor generation

In order to hide the query keyword from the cloud server, one authorized userUj, considered as a data user, has to encrypt the keyword instead of directly sending it to the cloud server. Concretely, for a query keywordthe data userUjcomputes a trapdoor:

Then,Ujsends trapdoorTto the cloud server, and waits for search results from the cloud server.

5.5 Search

Upon receiving the trapdoor from the data userUj, the cloud server performs the search to find out the related documents. As a matter of fact, trapdoorTcan be used to search over the encrypted data from all users in the group.In this paper, we only use the encrypted data ofUito explain how phaseSearchworks. The detailed description of phaseSearchconsists of following four steps.

First, the cloud server picks out the re-encryption keyrki→jfrom the matrix, and generates token

Second, the cloud server extractsfromby running the algo-rithmwhereAccording tothe cloud server can pick out the matched document subsetin which each document involves the query keywordIt is worth noting that the cloud server can execute this step as soon as the index is received.

Table I An example of the re-encryption key matrix

Table II Theoretical comparison among the schemes without secure channels

Finally, the cloud server returns the search resulback to the data userUj.

5.6 Documents retrieval

After receiving the search result, the data userUjfirst retrieves the symmetric keyKDas follows.

Then, the userUjusesKDto decryptand retrieves the documents that involves the query keyword.

5.7 User adjustment

If a new user has been agreed by the manager to join in the group, the manager requests the cloud server to add a line and a column to the matrix. Then, this new user needs to generate a re-encrypting key set for authorized users in the group, and uploads the set together with his public key to the cloud server. When the authorized users are online, the cloud server will send the public key of the new user to the authorized users and inform them to generate a re-encryption key for the new user. All collected re-encryption keys will be added into the matrix. Revoking a user from the group is very efficient. The manager only needs to inform the cloud server to delete the re-encryption keys related to the revoked user.

VI. SECURITY ANALYSIS

In this section, we first analyze the confidentiality of the encrypted data, the privacy of the keyword in the index and the trapdoor. Then,we prove that our scheme can defense against the eavesdropper who can intercept the transmitted information.

Before we prove the security of our scheme,we first review some hard assumptions.

Definition 1.Discrete Logarithm (DL) Assumption: Letbe a cyclic group of a large prime p with a generator of g. Given(p,g,ga)wherethe probability of computing a is negligible infor a PPT adversary.

Definition 2.Diffie-Hellman (DH) Assumption: Letbe a cyclic group of a large prime p with a generator of g. Given(p,ga,gb)wherethe probability of computing gab is negligible infor a PPT adversary.

Definition 3.Divisible Computation Diffie-Hellman Assumption: We first introduce the divisible computation Diffie-Hellman (DCDH)problem [15]: Letbe a cyclic group of prime order p and g is assumed to be a generator of.Given(g,gx,gy), where,compute gx/y. The DCDH assumption [15] is presented as follows: there is no such a PPT adversary who can solve DCDH problem with non-negligible probability.

Theorem 1.The probability for the cloud server to extract the plaintext of documents from the encrypted versions is negligible if the symmetric key encryption is secure.

Proof:According to the design of our scheme, the cloud server can also possess the public keys of users, the re-encryption key sets andbesides the encrypted documents.Since the data ownerUiuses keyKDto encrypt each document, the cloud server has to obtain keyKD. Or the cloud server cannot extract the plaintext as long as the symmetric key encryption is secure. Due to the definition of keyKD, the probability for the cloud server to compute keyKDis equivalent to the probability of computingThat is to say, the cloud server needs to computeby using the pub-lic keysand the re-encryption key setIf the cloud server computeswith non-negligible probability, it proves that the cloud server finds a solution to solve DCDH problem with non-negligible probability. That contradicts the DCDH assumption. In conclusion, it is hard for the cloud server to extract the plaintext of documents from the encrypted data.

Theorem 2.The probability for the cloud server to extract the keyword from index Ii or trapdoor T is negligible.

Proof:We first analyze the security of the keyword in the index, and then prove the keyword in the trapdoor is hidden from the cloud server.

Case 1 (Security of the index):LetbeZ. Thus, the tokenin the index can be denoted asAccording to DL assumption, the cloud server cannot computeui·H(w) with non-negligible probability, which implies that the cloud server cannot retrieveH(w) from the index.

Case 2 (security of the trapdoor):The proof is in this case similar toCase 1. According to DL assumption, the cloud server cannot computefrom the given trapdoorandg. In addition,is the secret key which is held by userUjonly. Hence, the cloud server cannot retrieve the keyword from the trapdoor.

In conclusion, the keywords both in the index and the trapdoor are secure.

Theorem 3.An eavesdropper cannot generate any plaintext from the intercepted data with non-negligible probability.

Proof:The confidentiality of the encrypted data and the privacy of the keyword have been proved in Theorem 1 and Theorem 2. In this theorem, we only prove that the eavesdropper cannot extract the identifiers of documents in the index. The identifiers are encrypted by using the symmetric key encryption with keySince the eavesdropper can only possessgsandthe probability for the eavesdropper to compute the key is equivalent to cracking the DH assumption. Therefore, the identifiers of the documents can be protected from being revealed to the eavesdropper.

VII. PERFORMANCE EVALUATION

In Table 2, we compare our scheme with Beak et al. [10] and Rhee et al. [11]. Assume that there isnauthorized user who can search over the file withmkeywords. Noting that we only consider one file in the comparison. LetEbe one exponential operation,Pbe one pairing operation,be the length of the element inandbe the length of the element in. As shown in Table 2, the time complexity of the index generation isO(n) in our scheme,which isO(m·n) in [10] and [11]. The additional storage in the comparison is the size of both the index and the re-encryption key set.Noting that neither the scheme in [10] nor[11] has re-encryption key set. In Table 2, we can see that the storage cost isO(m+n) in our scheme, which is less than the schemes in both[10] and [11].

In addition, we evaluate our proposed scheme using a real world dataset called Enron Email Dataset [16]. The experiment is executed on a laptop running Ubuntu Linux with 2.5 GHz Intel Core i5 processor and 4 Gigabyte memory. Two C language based source libraries are used to implement our scheme:Pairing-Based Cryptographic (PBC) library[17] and OpenSSL library [18]. To build the cryptographic environment, we adopt the type A elliptic curve with 160-bit group, which can provide 1024-bit discrete logarithm security.All the communication costs are not considered for the moment in our evaluation. Except that the result of the index generation is the average value of 10 trials, others experimental results are the average values generated from 100 trials.

Fig. 1 The average time for generating the re-encryption key set with the different number of authorized users

Fig. 2 The average time for the tokens generation with the different number of keywords in the index

Fig. 3 The search efficiency with the different number of keywords in the index

1) Re-encryption Key Computation:We first evaluate the time consumption by the data owner to generate the re-encryption key set,which is illustrated in Figure 1. We assume that the data owner has already downloaded the public keys of authorized users from the cloud server. As shown in Figure 1, the time for generating the re-encryption key set is linear to the number of the authorized users.Note that the re-encryption key computation is efficient because the time cost is less than 2 second if the number of authorized users does not exceed 500.

2) Index Generation:We focus on analyzing the efficiency of the tokens generation because the pairing operation is considered as expensive. Each keyword in the index is extracted from the real world dataset [16]. As illustrated in Figure 2, the computation time for generating tokens is linear to the number of keywords in the index. If there is 5000 keywords in the index, the data owner costs 37.772 second to generate the token for each keyword. Fortunately, the data owner needs to generate tokens only once.

3) Trapdoor Generation:Since each data user generates the trapdoor for only one query keyword, the computation time for the trapdoor generation is very fast. The average execution time for the trapdoor generation is only 3.758 millisecond. In 100 trials, the maximum and minimum execution time are 3.835 millisecond and 3.699 millisecond, respectively.

4) Search Efficiency:As mentioned above,eachIDwcan be decrypted as soon as the cloud server has received the index. Hence, we do not analyze the efficiency of the second step in phaseSearch. Since the cloud server needs to look up the index to find out the matched token, we evaluate the search efficiency with the different number of keywords in the index,and show the result in Figure 3. It is evident that the search is very efficient in our scheme.Interestingly, the size of the dictionary plays little role in search efficiency. It is prove that the match operation in phaseSearchcan be ignored comparing with the pairing operation.

VIII. CONCLUSIONS

In this paper, we propose a novel public key based keyword search scheme, which supports multi-owner keyword search without secure channels. Moreover, our scheme supports non-interactivity, which means that each data owner and data user in the group can complete his individual tasks without interacting with each other. Instead, each of users in the group only needs to interact with the cloud server.Furthermore, although the removal of secure channels, our scheme can still guarantee the secure keyword search, which will not reveal any additional information to the cloud server nor the eavesdropper. Finally, the experimental results demonstrate that our scheme is an efficient public key based solution.

This work has been partly supported by Natural Science Foundation of China (No.61303264).

[1] W.H Sun, W.J Lou, Y.T Hou, and H Li, “Privacy-preserving keyword search over encrypted data in cloud computing,” in Secure Cloud Computing. Springer, 2014, pp. 189–212.

[2] D.X Song, D Wagner, and A Perrig, “Practical techniques for searches on encrypted data,” in Security and Privacy, 2000. S&P 2000. Proceedings. 2000 IEEE Symposium on. IEEE, 2000, pp.44–55.

[3] D Boneh, C.G DI, R Ostrovksy, and G Persiano,“Public key encryption with keyword search,”in Advances in Cryptology-Eurocrypt 2004.Springer, 2004, pp. 506–522.

[4] R Curtmola, J Garay, S Kamara, and R Ostrovsky,“Searchable symmetric encryption: improved definitions and efficient constructions,” in Proceedings of the 13th ACM conference on Computer and communications security. ACM, 2006,pp. 79–88.

[5] J Li, Q Wang, C Wang, N Cao, K Ren, and W.J Lou, “Fuzzy keyword search over encrypted data in cloud computing.” in Computer Communications (INFOCOM), IEEE, 2010, pp. 1-5.

[6] C Wang, N Cao, J Li, K Ren, and W.J Lou, “Secure ranked keyword search over encrypted cloud data,” in IEEE 30th International Conference on Distributed Computing Systems (ICDCS), 2010,pp. 253–262.

[7] M Li, S.C Yu, N Cao, and W.J Lou, “Authorized private keyword search over encrypted data in cloud computing,” in Distributed Computing Systems (ICDCS), 2011 31st International Conference on. IEEE, 2011, pp. 383–392.

[8] N Cao, C Wang, M Li, K Ren, and W.J Lou, “Privacy-preserving multi-keyword ranked search over encrypted cloud data,” Parallel and Distributed Systems, IEEE Transactions on, vol. 25, no.1, pp. 222–233, 2014.

[9] W.H Sun, B. Wang, N Cao, M Li, W.J Lou, Y.T Hou, and H Li, ”Privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking,” in Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security. ACM, 2013,pp. 71–82.

[10] J Baek, R Safavi-Naini, and W Susilo, “Public key encryption with keyword search revisited,”in Computational Science and Its Applications–ICCSA 2008. Springer, 2008, pp. 1249–1259.

[11] H.S Rhee, J.H Park, W Susilo, and D.H Lee,“Improved searchable public key encryption with designated tester,” in Proceedings of the 4th International Symposium on Information,Computer, and Communications Security. ACM,2009, pp. 376–379.

[12] C.X Gu, Y.F Zhu, and H Pan, “Efficient public key encryption with keyword search schemes from pairings,” in Information security and cryptology. Springer, 2008, pp. 372–383.

[13] W.H Sun, X.F Liu, W.J Lou, Y.T Hou, and H Li,“Catch you if you lie to me: Efficient verifiable conjunctive keyword search over large dynamic encrypted cloud data,” in IEEE Conference on Computer Communications (INFOCOM), 2015,pp. 2110–2118.

[14] B Wang, W Song, W.J Lou, and Y.T Hou, “Inverted index based multi-keyword public-key searchable encryption with strong privacy guarantee,”in IEEE Conference on Computer Communications (INFOCOM), 2015, pp. 2092–2100.

[15] F Bao, R.H Deng, H.F Zhu, “Variations of diffie-hellman problem,” in Information and Communications Security. Springer, 2003, pp.301–312.

[16] “Enron Email Dataset,” https://www.cs.cmu.edu/～./enron/.

[17] “Pairing-based Cryptographic Library,” https://crypto.stanford.edu/pbc/.

[18] “OpenSSL,” https://www.openssl.org/.

[19] B Wang, S Yu, W.J Lou, Y.T Hou, “Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud.” In INFOCOM, 2014 Proceedings, 2014, pp. 2112-2120.

[20] E.J Goh. “Secure Indexes.” IACR Cryptology ePrint Archive, pp. 216, 2003.

[21] P Golle, J Staddon, and B Waters. “Secure conjunctive keyword search over encrypted data.”In Applied Cryptography and Network Security,2004, pp. 31-45.

[22] S Kamara, C Papamanthou, and T Roeder, ”Dynamic searchable symmetric encryption.” In Proceedings of the 2012 ACM conference on Computer and communications security, 2012,pp. 965-976.