# Fine-Grained Attribute-Based Multikeyword Search for Shared Multiowner in Internet of Things

Authors: Yunhong Zhou; Jiehui Nan; Licheng Wang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

At present, with the popularity of Internet of things (IoT), a huge number of datasets generated by IoT devices are being uploaded to the cloud storage in remote data management service, but a series of security and privacy defects also arises, where one of the best ways for preventing data disclosure is encryption. Among them, searchable encryption (SE) is considered to be a very attractive cryptographic technology, since it allows users to search records in an encrypted form and to protect user’s data on an untrusted server. For the sake of enhancing search permission, attribute-based keyword search (ABKS) is an efficient method to provide secure search queries and fine-grained access authentications over ciphertexts. However, most existing ABKS schemes concentrate on single keyword search, which usually returns redundant and irrelevant results, so it would cost some unnecessary computation and communication resources. Furthermore, existing work in the literature mostly only supports unshared multiowner where a specific data owner owns each file, which is not able to satisfy more desired expressive search. In this work, we propose a novel attribute-based multikeyword search for shared multiowner (ABMKS-SM) primitive in IoT to achieve enhanced access control for users; meanwhile, it can support multikeyword search over ciphertexts and give a formal security analysis in the adaptive against chosen keyword attack (IND-CKA) model. Finally, we have also implemented this prototype to show efficiency when compared with some previous schemes.


---

## Body

## 1. Introduction

With the rapid advances of Internet of things [1, 2] technology, IoT devices produce large quantities of datasets that require being securely stored and efficiently shared among different users. Such increasing extensive industrial datasets are saved on cloud servers [3] due to large storage capacity, high scalability, and flexible availability. A considerable number of individuals and organizations may be tempted to store their files on the third cloud server, reducing local data storage for convenience. Unfortunately, the cloud storage server is semihonest because it is possible to be curious about the user’s stored data in real-world applications [4], and data security concerns have become serious barriers to prevent the widespread usage of cloud storage for IoT. In order to mitigate the concern, the simple and efficient solution is to encrypt the storage of data to prevent information from being exposed to server, but one limitation is that the encryption mechanism inevitably brings about inflexibilities of data accessing when used to some extent, such as querying keywords on encrypted datasets. In addition, a naive approach is to download whole ciphertexts locally and later on decrypt them for querying, but it leads to wasting computational capabilities and storage costs. So, how to search encrypted keywords securely and efficiently is crucial in an IoT environment.The positive approach to solve the above problem is using searchable encryption (SE) [5, 6] in which users can not only search directly over encrypted records just like on plaintext space but also preserve the data’s privacy. Although SE has paid more attention to the industrial and academic fields for many years, the research is not sufficient because most data owners wish to share their datasets with legitimate users authorized by them. Furthermore, with the purpose of protecting privacy, the traditional cloud-based access control system is not suitable anymore, because the server cannot be fully trusted. To solve this issue, attribute-based encryption (ABE) [7–14] achieves flexible access authentications over shared data for users, which is a promising cryptographic tool adopted in searchable encryption. Attribute-based keyword search (ABKS) inherits the advantages of SE and ABE, which not only achieves keyword search on encrypted datasets but also preserves the nature of fine-grained access control.However, for the cloud-based storage system in an IoT environment, the only fine-grained access control is always not adequate. The existing ABKS schemes [15–20] only support single keyword search functions, while it requires massive computational and broadband resources as this retrieval mode returns a lot of irrelevant results. The method to achieve multikeyword search [21–23] was introduced to alleviate the issues. That is to say, when data users use multikeyword search to obtain related records containing multikeyword, the query results enjoy much more desirable accuracy than those using single keyword search. Consequently, how to efficiently construct an attribute-based multikeyword search is significant both in theory and in practice.More importantly, a practical search system for IoT should support multiple data owners, because a huge number of data files may be shared among different data owners. According to whether a single entity owns each data file or many entities share each other, there are two types of the following multiowner, that is, unshared multiowner [24] and shared multiowner [19, 25]. Previous work in the literature mostly only concentrates on keyword search under unshared multiowner, losing sight of shared multiowner. The shared multiowner setting has many broader and practical applications compared with the unshared multiowner setting, such as cloud-based electronic health record systems. In this system, data records for some patient should be shared by different medical organizations and hospitals. Moreover, the unshared multiowner setting also brings significant computational and storage overheads as each data record is considered to be independent.Specifically, the authorization privilege of data owners may vary from users to users when considering some practical scenarios in an IoT environment. For example, in a company system, all employees of this company should have the right to search this system. On the one hand, employees in different departments have different search permissions. The attributes of employees can be set; only employees whose attributes meet the access structure specified by a department can query its related records. On the other hand, board members could control the important files of the company in common. The ordinary staff enables decrypting and obtaining the documents with the authorizations of them. The former can use the AND-gate access structure sufficiently to achieve search access control and the latter can use the linear secret-sharing schemes (LSSS) access structure.In this work, we first put forward an efficient attribute-based multikeyword search for shared multiowner (ABMKS-SM) scheme in Internet of things with fine-grained access control through AND-gate access structure and LSSS. Based on the AND-gate access structure, our proposed ABMKS-SM scheme achieves access control mechanism to enhance the user’s search experience, because the AND-gate access structure significantly improves the search algorithm. Based on LSSS technology, our scheme only allows data users to obtain valid authorizations from multiple data owners to decrypt the search results, which is suitable for multiowners sharing scenarios.In a nutshell, our main contributions can be concluded as follows:(1)
We first design an efficient and secure ABMKS-SM scheme for IoT environments, where multiple data owners enable controlling user’s search permissions and only legitimate users with authorizations could search for outsourced data. More importantly, it can be applied to shared multiowner settings.(2)
The most important security goal of designing schemes is adaptive indistinguishable security against chosen keyword attack (IND-CKA). We present a formal security analysis in an IND-CKA model while guaranteeing the privacy of keywords.(3)
In the respect of functional comparison, theoretical analysis, and experimental analysis, we evaluate our scheme’s performance and further demonstrate the efficiency and practicality of this scheme. At last, from theoretical analysis, it is shown that our ABMKS-SM scheme is superior to the previous CP-ABKS [15] and ABKS-SM scheme [19]. From experimental analysis, the obtained results further demonstrate computation costs to search which are free from attributes; meanwhile, the time costs to generate the trapdoor are not related to the number of attributes.The remainder of this paper can be organized as follows. We recall some related work in Section2. We describe some necessary cryptographic tools in Section 3. We give the system model, scheme definition, and security model in Section 4. We propose a new and concrete scheme in Section 5. We discuss a formal security analysis and performance analysis when compared with previous schemes in Section 6. We conclude this paper in Section 7.


## 2. Related Work

In 2000, Song et al. [5] suggested symmetric searchable encryption (SSE) scheme by using symmetric cryptography, which first introduces the concept of searchable encryption. Subsequently, Boneh et al. [26] seminally designed searchable public key encryption construction exploring identity-based encryption for e-mail systems in an asymmetric setting, where the data owner extracts keywords from messages and encrypts them before outsourcing to the server, then the data user can generate his interested keyword search token under his private key, and then he sends this token to the server. Upon receipt of the user’s token, the server can perform the keyword retrieval operations and returns the related search results. Since this seminal work, many researchers have made great efforts [27–35] and proposed a series of searchable encryption proposals to make them more efficient and enrich the search diversified, for example, fuzzy search [36–38], conjunctive search [39–41], and ranked search [42–44].To the best of our knowledge, ABE [7] implements attribute-based access control as an efficient solution. Furthermore, ABKS schemes can search keywords over encrypted documents with access control by utilizing ABE technology. In 2014, Zheng et al. [15] developed an attribute-based keyword search primitive and provided two concrete ABKS scheme constructions. In an ABKS scheme, data owners encrypt keywords and build searchable indexes embedded in an access structure, and only legitimate users can generate their search tokens for querying on outsourced datasets. Later on, Dong et al. [16] provided an efficient ABKS construction for resource-constrained mobile devices via an online/offline approach, where data owners and users are allowed to execute the related algorithm in this way. More specifically, an outsourcing key-issuing and decryption scheme was designed by Li et al. [17], where the cloud server can decrypt partial work without learning anything about the message. Recently, Qiu et al. [18] provided an enhanced scheme to achieve an access policy with hidden, where the data owner implements fine-grained authorizations for different users with a hidden structure in encrypted form. However, all the aforementioned schemes only consider searching a single keyword.Zhang et al. [21] introduced a searchable design with ranked multikeyword under multiple owners setting where the security of keywords and documents could be protected. Accordingly, by exploring proxy re-encryption as well as lazy re-encryption technology, an authorized keyword search construction was designed by Sun et al. [22] under multiple data owners and users. And it can achieve an efficient user revocation mechanism. Subsequently, Miao et al. [24] provided a new multikeyword search proposal on medical records that is encrypted via ciphertext-policy attribute-based encryption. In their construction, it not only offers multikeyword search but also can be applied to multiowner settings. On the other hand, Liu et al. [23] presented a new improved scheme with user tracing using the AND-gate on the multivalue attribute. Although these above schemes support multikeyword search, it cannot be applied to scenarios where multiple owners could be shared. More recently, Miao et al. [19] first presented an efficient ABKS scheme which is suitable for shared multiowner setting; however, it only considers a single keyword search. Moreover, Miao et al. [25] suggested a scheme to deal with conjunctive keyword search with verification on the basis of multisignatures in shared multiowner setting again. Although their scheme is applied to a shared multiowner setting, it also fails to support multikeyword search. There are no efficient attribute-based multikeyword search schemes for shared multiowner so far. Thus, in this work, we first design an efficient attribute-based multikeyword search for shared multiowner (ABMKS-SM) scheme in IoT, and it can support the multikeyword search on ciphertexts with fine-grained access control.


## 3. Preliminaries

We explain some necessary cryptographic tools related to our ABMKS-SM construction.


### 3.1. Bilinear Map

SupposeG and GT are two cyclic groups of same order p, and g is a generator of G. Let e^:G×G⟶GT represent a computable bilinear map that satisfies three conditions as below:(1)
Bilinearity: for anyg,h∈G and x,y∈ℤp∗, there exists e^gx,hy=e^g,hxy(2)
Nondegeneracy: forg∈G, e^g,g≠1(3)
Computability: giveng,h∈G, the pairing e^g,h could be computed efficiently


### 3.2. Access Structure

In our scheme, we define an AND-gate access structure [45, 46] based multivalue attribute. Suppose L=λ1,λ2,…,λn denotes an attribute list where n represents the number of attributes. Each attribute λi∈L,i=1,2,…,n has a possible value set Vi=vi,1,vi,2,…,vi,ni, where ni is the number of possible values of λi. The user’s attribute set SU is defined as SU=a1,a2,…,an, where ai∈Vi. The AND-gate access policy is denoted as ℙ=att1,att2,…,attn, where atti∈Vi. If ai=attii∈1,n, the attribute set for users SU satisfies the AND-gate access policy ℙ. Specifically, the user’s attribute list is the same structure as the access policy when the attribute in the user’s attribute list has only one value.


### 3.3. Linear Secret-Sharing Schemes (LSSS)

Linear secret-sharing schemes (LSSS) [47] can convert previously used structures such as formulas (equivalently tree structures) into an LSSS representation by using standard techniques [48] and enhance the access control to multiparty requirements. Suppose P=P1,P2,…,Pl is a collection of parties, a secret-sharing scheme Π is called linear (over ℤp) on the condition that the following properties are satisfied.(i)
A vector overℤp is formed by the shares for each party Pi (i∈1,l).(ii)
There exists a linear secret-sharing structureM,ρ, where Ml×n denotes a sharing-generating matrix and a monotone function ρi (i∈1,l) can label the i-th row in M, where ρ denotes an injective function from 1,2,…,l to a party. Given random elements r2,…,rn∈ℤp∗, we consider constructing a column vector v⟶=s,r2,…,rn and compute the shares of secret s as λi=Miv⟶, where the share λi belongs to Pi and Mi represents the i-th row in M.According to the above definition, every linear secret-sharing scheme satisfies linear reconstruction property. AssumeΠ is an LSSS for the access structure A and S represents an authorized set that satisfies A (namely, S∈A). We define I⊂1,2,…,l as I=i|ρi∈S. If λi are the valid shares of a secret s, then we can find a constant set ωii∈I such that ∑i∈IωiMi=1,…,0 via Gaussian elimination method. Consequently, the equation ∑i∈Iωiλi=s can be satisfied.


### 3.4. Decisional Bilinear Diffie–Hellman Assumption

Decisional Bilinear Diffie-Hellman (DBDH) Assumption has the following definition: given elementsgx,gy,gz∈G where x,y,z∈ℤp∗ and g is a generator of group G, the DBDH problem is to distinguish e^g,gxyz∈GT from a random group element e^g,gγ∈GT where γ∈ℤp∗. It is said that the DBDH assumption holds if there no exists a probabilistic polynomial-time (PPT) algorithm A who has a nonnegligible advantage solving DBDH hardness problem, where the advantage function of this algorithm A can be denoted as(1)AdvADBDHλ=PrAg,gx,gy,gz,e^g,gxyz=1−PrAg,gx,gy,gz,e^g,gγ=1.


## 3.1. Bilinear Map

SupposeG and GT are two cyclic groups of same order p, and g is a generator of G. Let e^:G×G⟶GT represent a computable bilinear map that satisfies three conditions as below:(1)
Bilinearity: for anyg,h∈G and x,y∈ℤp∗, there exists e^gx,hy=e^g,hxy(2)
Nondegeneracy: forg∈G, e^g,g≠1(3)
Computability: giveng,h∈G, the pairing e^g,h could be computed efficiently


## 3.2. Access Structure

In our scheme, we define an AND-gate access structure [45, 46] based multivalue attribute. Suppose L=λ1,λ2,…,λn denotes an attribute list where n represents the number of attributes. Each attribute λi∈L,i=1,2,…,n has a possible value set Vi=vi,1,vi,2,…,vi,ni, where ni is the number of possible values of λi. The user’s attribute set SU is defined as SU=a1,a2,…,an, where ai∈Vi. The AND-gate access policy is denoted as ℙ=att1,att2,…,attn, where atti∈Vi. If ai=attii∈1,n, the attribute set for users SU satisfies the AND-gate access policy ℙ. Specifically, the user’s attribute list is the same structure as the access policy when the attribute in the user’s attribute list has only one value.


## 3.3. Linear Secret-Sharing Schemes (LSSS)

Linear secret-sharing schemes (LSSS) [47] can convert previously used structures such as formulas (equivalently tree structures) into an LSSS representation by using standard techniques [48] and enhance the access control to multiparty requirements. Suppose P=P1,P2,…,Pl is a collection of parties, a secret-sharing scheme Π is called linear (over ℤp) on the condition that the following properties are satisfied.(i)
A vector overℤp is formed by the shares for each party Pi (i∈1,l).(ii)
There exists a linear secret-sharing structureM,ρ, where Ml×n denotes a sharing-generating matrix and a monotone function ρi (i∈1,l) can label the i-th row in M, where ρ denotes an injective function from 1,2,…,l to a party. Given random elements r2,…,rn∈ℤp∗, we consider constructing a column vector v⟶=s,r2,…,rn and compute the shares of secret s as λi=Miv⟶, where the share λi belongs to Pi and Mi represents the i-th row in M.According to the above definition, every linear secret-sharing scheme satisfies linear reconstruction property. AssumeΠ is an LSSS for the access structure A and S represents an authorized set that satisfies A (namely, S∈A). We define I⊂1,2,…,l as I=i|ρi∈S. If λi are the valid shares of a secret s, then we can find a constant set ωii∈I such that ∑i∈IωiMi=1,…,0 via Gaussian elimination method. Consequently, the equation ∑i∈Iωiλi=s can be satisfied.


## 3.4. Decisional Bilinear Diffie–Hellman Assumption

Decisional Bilinear Diffie-Hellman (DBDH) Assumption has the following definition: given elementsgx,gy,gz∈G where x,y,z∈ℤp∗ and g is a generator of group G, the DBDH problem is to distinguish e^g,gxyz∈GT from a random group element e^g,gγ∈GT where γ∈ℤp∗. It is said that the DBDH assumption holds if there no exists a probabilistic polynomial-time (PPT) algorithm A who has a nonnegligible advantage solving DBDH hardness problem, where the advantage function of this algorithm A can be denoted as(1)AdvADBDHλ=PrAg,gx,gy,gz,e^g,gxyz=1−PrAg,gx,gy,gz,e^g,gγ=1.


## 4. System and Security Model

We give a description of the system model, scheme definition and corresponding security model, respectively.


### 4.1. System Model

We discuss our ABMKS-SM system for shared multiowner settings in IoT, which consists of four participants, including cloud service provider (CSP), data users, trusted authority (TA) and multiple data owners. TA initializes the system and distributes keys for multiple data owners and users. First, multiple data owners encrypt files with symmetric keys and further encrypt symmetric keys with a random secret value. In particular, based on LSSS access structure, multiple data owners share the secret value with each other when considering shared multiowner settings. Then, multiple data owners build keyword indexes extracted keywords from each document under the AND-gate access policy before outsourcing to the CSP. Especially, the CSP provides computation, storage and search services for users. When a user wishes to request a keyword query on storage of encrypted records, he could produce a search keyword trapdoor and then submit it into the CSP. Having received a trapdoor from a data user, the CSP attempts to retrieve over encrypted data and returns relevant results to users. Finally, the user decrypts corresponding results only if he gets legitimate authorization credentials associated with multiple data owners. More specifically, our system model is presented in Figure1.Figure 1
ABMKS-SM model.


### 4.2. Algorithm Definition in ABMKS-SM System

In this section, we give the algorithm defined in the ABMKS-SM system comprised the following six algorithms.Setup1λ: TA runs the setup algorithm, which inputs the security parameter λ, and generates master key msk and public parameter pp.KeyGenpp,O,ID,SU,msk: TA runs this key generation algorithm, which inputs the public parameter pp, the multiple data owners set O, the user’s identityID, the data user’s attribute set SU and the master key msk, and generates public key PKOj and secret key SKOj of each data owner Oj and user’s private key SKU.EncryptionW,pp,F,K,ℙ,PKO,M,ρ: the multiple data owners run the encryption algorithm, which inputs the keyword set W, the public parameter pp, the file/symmetric key pair set F,K=f,k, the AND-gate access policy ℙ used to construct keyword indexes, the public key PKO of data owners and an access policy M,ρ to multiple data owners authorizations for accredited data users, and generates ciphertexts CT and the encrypted indexes IW.Trapdoorpp,SU,SKU,W′: the data user runs this trapdoor generation algorithm, which inputs the public parameter pp, the attribute set SU, the private key SKU and a set of the query keyword W′, and generates the search trapdoor TW′.Searchpp,TW′,SU,IW: the CSP runs the search query algorithm, which inputs the public parameter pp, the trapdoor TW′, the attribute set SU and the encrypted index IW. When SU satisfies AND-gate access policy ℙ contained IW, and further the search trapdoor and the encrypted index contain the same keyword set, this algorithm returns 1 and sends the relevant search results CT′ to user. Otherwise, it returns 0.Decryptionpp,SKU,ID,CT′: the data user runs this decryption algorithm, which inputs the public parameter pp, private key SKU, user’s identity ID and the corresponding search results CT′. If the user’s identity ID is authorized by multiple data owners, it decrypts relevant search results.


### 4.3. Security Model

SupposeA is an adversary and C is a challenger, we define our ABMKS-SM scheme’s security model as adaptive indistinguishable security against chosen keyword attack (IND-CKA) game, which is conducted between A and C as the following steps.Setup: C runs the Setup1λ algorithm to generate pp and msk. C runs the KeyGenpp,O,ID,SU,msk to output SKU, while A only owns public parameters pp.Phase 1: A is able to adaptively request the trapdoor from a tuple of keyword sets W′. C executes the Trapdoorpp,SU,SKU,W′ algorithm and generates the search trapdoor TW′, and then returns it to A.Challenge: A chooses keyword sets W0, W1 for challenging, and submits to C. It is required that the two keyword sets are not able to query in Phase 1. Upon receipt of two keyword sets, C selects a random bit b∈0,1 to output an encrypted index IWb, and sends it to the adversary A.Phase 2: A can request the queries for more trapdoors of keyword sets and the only restriction is that any keyword set of his choice except for the W0, W1.Guess: finally, A outputs a guess b′, if b=b′, A gains this game.We define thatA’s the advantage function against IND-CKA game can be denoted as(2)AdvAIND−CKAλ=Prb=b′−12.Definition 1.
A privacy-preserving ABMKS-SM scheme is IND-CKA secure under the circumstance that the advantage of breaking IND-CKA game is negligible for any PPT adversaryA.


## 4.1. System Model

We discuss our ABMKS-SM system for shared multiowner settings in IoT, which consists of four participants, including cloud service provider (CSP), data users, trusted authority (TA) and multiple data owners. TA initializes the system and distributes keys for multiple data owners and users. First, multiple data owners encrypt files with symmetric keys and further encrypt symmetric keys with a random secret value. In particular, based on LSSS access structure, multiple data owners share the secret value with each other when considering shared multiowner settings. Then, multiple data owners build keyword indexes extracted keywords from each document under the AND-gate access policy before outsourcing to the CSP. Especially, the CSP provides computation, storage and search services for users. When a user wishes to request a keyword query on storage of encrypted records, he could produce a search keyword trapdoor and then submit it into the CSP. Having received a trapdoor from a data user, the CSP attempts to retrieve over encrypted data and returns relevant results to users. Finally, the user decrypts corresponding results only if he gets legitimate authorization credentials associated with multiple data owners. More specifically, our system model is presented in Figure1.Figure 1
ABMKS-SM model.


## 4.2. Algorithm Definition in ABMKS-SM System

In this section, we give the algorithm defined in the ABMKS-SM system comprised the following six algorithms.Setup1λ: TA runs the setup algorithm, which inputs the security parameter λ, and generates master key msk and public parameter pp.KeyGenpp,O,ID,SU,msk: TA runs this key generation algorithm, which inputs the public parameter pp, the multiple data owners set O, the user’s identityID, the data user’s attribute set SU and the master key msk, and generates public key PKOj and secret key SKOj of each data owner Oj and user’s private key SKU.EncryptionW,pp,F,K,ℙ,PKO,M,ρ: the multiple data owners run the encryption algorithm, which inputs the keyword set W, the public parameter pp, the file/symmetric key pair set F,K=f,k, the AND-gate access policy ℙ used to construct keyword indexes, the public key PKO of data owners and an access policy M,ρ to multiple data owners authorizations for accredited data users, and generates ciphertexts CT and the encrypted indexes IW.Trapdoorpp,SU,SKU,W′: the data user runs this trapdoor generation algorithm, which inputs the public parameter pp, the attribute set SU, the private key SKU and a set of the query keyword W′, and generates the search trapdoor TW′.Searchpp,TW′,SU,IW: the CSP runs the search query algorithm, which inputs the public parameter pp, the trapdoor TW′, the attribute set SU and the encrypted index IW. When SU satisfies AND-gate access policy ℙ contained IW, and further the search trapdoor and the encrypted index contain the same keyword set, this algorithm returns 1 and sends the relevant search results CT′ to user. Otherwise, it returns 0.Decryptionpp,SKU,ID,CT′: the data user runs this decryption algorithm, which inputs the public parameter pp, private key SKU, user’s identity ID and the corresponding search results CT′. If the user’s identity ID is authorized by multiple data owners, it decrypts relevant search results.


## 4.3. Security Model

SupposeA is an adversary and C is a challenger, we define our ABMKS-SM scheme’s security model as adaptive indistinguishable security against chosen keyword attack (IND-CKA) game, which is conducted between A and C as the following steps.Setup: C runs the Setup1λ algorithm to generate pp and msk. C runs the KeyGenpp,O,ID,SU,msk to output SKU, while A only owns public parameters pp.Phase 1: A is able to adaptively request the trapdoor from a tuple of keyword sets W′. C executes the Trapdoorpp,SU,SKU,W′ algorithm and generates the search trapdoor TW′, and then returns it to A.Challenge: A chooses keyword sets W0, W1 for challenging, and submits to C. It is required that the two keyword sets are not able to query in Phase 1. Upon receipt of two keyword sets, C selects a random bit b∈0,1 to output an encrypted index IWb, and sends it to the adversary A.Phase 2: A can request the queries for more trapdoors of keyword sets and the only restriction is that any keyword set of his choice except for the W0, W1.Guess: finally, A outputs a guess b′, if b=b′, A gains this game.We define thatA’s the advantage function against IND-CKA game can be denoted as(2)AdvAIND−CKAλ=Prb=b′−12.Definition 1.
A privacy-preserving ABMKS-SM scheme is IND-CKA secure under the circumstance that the advantage of breaking IND-CKA game is negligible for any PPT adversaryA.


## 5. ABMKS-SM Construction

Based on the algorithm defined in the ABMKS-SM system, we present a specific construction of our proposed scheme that makes use of six algorithms. The running algorithms are described below.Setup1λ: given the security parameter λ, it generates pp and msk, which works as follows:TA first randomly selects two cyclic groups,G and GT, with same order p and sets a computable bilinear pairing e^:G×G⟶GT and g is the generator of G.Then, the TA selects two secure hash functions:H1:0,1∗⟶ℤp∗and H2:0,1∗⟶G.Finally, TA randomly selectsα,β∈ℤp∗, computes gβ,A=e^g,gα, and sets pp=G,GT,p,e^,g,A,gβ,H1,H2,msk=α,βKeyGenpp,O,ID,SU,msk: given the public parameter pp, the multiple data owners set O=O1,O2,…,Ol, the user’s identity ID, the attribute set SU, and the master key msk, it generates the public key PKOj and secret key SKOj of each data owner Oj,j∈1,l and the user’s private key SKU, which works as follows:TA randomly choosesxj∈ℤp∗ and sets each data owner’s public key and secret key as PKOj=gxj,SKOj=xj.The TA randomly choosesr∈ℤp∗, computes K1=gr,K2=gα, and sets K3=K2H2IDβ.For each attributea∈SU, compute Ka=K1gH1a.Set the data user’s private key asSKU=K1,K2,K3,Ka∀a∈SUEncryptionW,pp,F,K,ℙ,PKO,M,ρ: given the keyword set W=w1,w2,…,wm, the public parameter pp, the file/symmetric key pair set F,K=f,k, the AND-gate access policy ℙ used to establish encrypted keyword indexes, the data owner’s public key PKO, and an LSSS access policy M,ρ to multiple data owners authorizations for accredited data users, where Ml×n is an access matrix and ρ is a function mapping each row of M to a data owner, this encryption algorithm generates ciphertexts CT and the encrypted indexes IW.(i)
The ciphertextsCT are generated as follows:For each filef, one of multiple data owners (without loss of generality, assume the data owner is O1) encrypts f with symmetric key k∈GT as c, that is, f⟶kc.Then,O1 encrypts each symmetric key k and randomly chooses the secret value s and computes C′=kAs,C″=gs.After,O1 randomly selects values r2,…,rn∈ℤp∗ and considers to build a column vector v⟶=s,r2,…,rn and further computes the shares of the secret s as λj=Mjv⟶j∈1,l. O1 sends remaining λj to other data owners via a secure channel. Data owners compute Cj=gβλjPKOj−1=gβλjg−xj, j∈1,l.Set symmetric key ciphertexts as(5)C=C′,C″,Cj.The ciphertexts are(6)CT=c,C=c,C′,C″,Cj.(ii)
The encrypted indexesIW are generated as follows:Multiple data owners extract keyword setsW=w1,w2,…,wm from the file set F=f and select a random element θ∈ℤp∗. For any keyword wi∈W, multiple data owners compute Iwi=Aθe^gθ,H2wi.ComputeI1=gθ.For each attributeatt∈ℙ, compute Iatt=gθH1att.Set the encrypted indexes asIw=Iwi,I1,IattBesides, multiple data owners have authorized users’ identity list, and each data owner can generate the valid decryption authorizationAOj=H2IDxj with his/her private key SKOjfor the identity ID of a data user.Trapdoorpp,SU,SKU,W′: given the public parameter pp, the attribute set SU, the private key SKU, and the search keyword set W′=w1′,w2′,…,wt′, this trapdoor generation algorithm generates the search trapdoor TW′, which works as follows:The data user calculatesT=K1K2t∏i=1tH2wi′=grgαt∏i=1tH2wi′.For each attributea∈SU, compute Ta=Ka=grgH1a.Set the trapdoor asTW′=T,Ta∀a∈SuSearchpp,TW′,SU,IW: given the public parameter pp, the query trapdoor TW′, the attribute set SU, and the encrypted indexes IW, the search query algorithm returns 1 or 0, which works as follows.IfSU satisfies the AND-gate access policy ℙ embedded in IW, then the CSP checks that the following equation holds:(9)e^I1,Ta∏i=1tIwi=e^I1,Te^g,Iatt.If the above condition holds, this search algorithm returns 1 and sends the relevant search resultsCT′ to user; otherwise, it returns 0.Decryptionpp,SKU,ID,CT′: given the public parameter pp, the user’s private key SKU and identity ID, and the relevant query results CT′, the decryption algorithm returns related file encryption key set K=k, which works as follows.The data user first verifies whether the identityID is authorized from multiple data owners. Note that there is no intersection between data users and data owners. If it is not in the authorized users’ identity list, the algorithm returns 0.Otherwise, the identityID of the data user obtains the valid decrypted authorizations AOj=H2IDxj from multiple data owners.AssumeA is an LSSS matrix access policy (namely, A=M,ρ) and S is an authorized set of data owners (S∈A) with η=j|ρj∈S⊂1,2,…,l. When multiple data owners encrypted each shared file with same access structure, they get a constant set φjj∈ηby solving the equation ∑j∈ηφjMi=1,…,0.According to the decrypted authorizationsAOjOj∈S and the private key SKU, the data user computes the following equation:(10)e^C″,K3∏j∈ηe^Cj,H2IDe^AOj,gφj=e^g,gαs.Finally, the data user gains the file encryption keyk=C′/e^g,gαs and decrypts the related search results.


## 6. Security and Performance

We analyze our scheme’s correctness, security, and performance.


### 6.1. Correctness

IfSU satisfies the AND-gate access policy ℙ embedded in IW, while the search trapdoor and the encrypted index contain same keyword set, W′⊆W, we can verify the correctness of search algorithm indicated as (11)e^I1,Ta∏i=1tIwi=e^gθ,grgH1a∏i=1te^g,gαθe^gθ,H2wi=e^g,gαθt∏i=1te^gθ,H2wie^gθ,gre^gθ,gH1a=e^g,gαθte^gθ,∏i=1tH2wie^gθ,gre^gθ,gH1a=e^g,gαθte^gθ,∏i=1tH2wie^g,gθre^g,gθH1a,where the encryption algorithm generates Iwi and I1 and the trapdoor algorithm generates Ta.(12)e^I1,Te^g,Iatt=e^gθ,grgαt∏i=1tH2wi′e^g,gθH1att=e^gθ,gre^gθ,gαte^gθ,∏i=1tH2wi′e^g,gθH1att=e^g,gθre^g,gθαte^gθ,∏i=1tH2wi′e^g,gθH1att,where the encryption algorithm generates I1 and Iatt and the trapdoor algorithm generates T.If the identityID of the data user is authorized from multiple data owners, according to the decrypted authorizations AOjOj∈S and the private key SKU, then we can verify correctness for decryption indicated as(13)e^C″,K3∏j∈ηe^Cj,H2IDe^AOj,gφj=e^gs,gαH2IDβ∏j∈ηe^gβλjg−xj,H2IDe^H2IDxj,gφj=e^gs,gαe^gs,H2IDβe^H2IDxj,ge^g−xj,H2IDe^gβ,H2ID∑j∈ηφjλj=e^gs,gαe^gs,H2IDβe^gβ,H2IDs=e^g,gαs.


### 6.2. Security Proof

In the area of public key searchable encryption, IND-CKA secure is one of the most important security goals. By the described above security model defined inSection 4.3, we formally prove the security of ABMSK-SM construction.Theorem 1.
Our ABMKS-SM scheme is IND-CKA secure provided that the DBDH assumption holds.Proof 1.
In fact, our reduction is straightforward. Intuitively, assume that there exists an adversaryA that can break our proposed scheme. We could build a simulator ℬ who resolves DBDH problems of distinguishing the DBDH tuple gx,gy,gz,Z=e^g,gxyz and a random tuple gx,gy,gz,Z=e^g,gγ, where x,y,z,γ∈ℤp∗. Next, we formally show the following reduction.Init: at first, A chooses an AND-gate access policy ℙ∗ for challenging and returns to ℬ.Setup: ℬ selects random elements α,β∈ℤp∗ and calculates A=e^g,gα, gβ. ℬ selects one hash function H1:0,1∗⟶ℤp∗ and sets msk=α,β and pp=G,GT,p,e^,g,A,gβ.The hash queryH2wi is simulated as a random oracle model as below. If wi has not been requested previously, the simulator ℬ randomly chooses ρi∈ℤp∗ and next puts wi,ρi to the list OH2 and outputs gρi; otherwise, the simulator ℬ searches ρi from OH2 and returns gρi.Phase 1: A can query the trapdoor for keyword set W and request the queries of the following OKeyGen and OTrapdoor oracles.(1)
OKeyGen: the simulator ℬ randomly selects r∈ℤp∗ and computes K1=gr. For each attribute a∈SU, compute Ka=K1gH1a=grgH1a. ℬ returns SKU to A and stores a private key’s list LSKU.(2)
OTrapdoor: at the beginning, the simulator ℬ issues the OKeyGen oracle to gain the secret key SKU and then ℬ calculates T=grgα∏i=1tgρi and Ta=grgH1a for each attribute a∈SU. ℬ adds W to the list LW depending on SU which satisfies the access policy.Challenge: A submits ℬ two keyword sets W0,W1. Without loss of generality, W0 and W1 are not in LW. ℬ randomly chooses b∈0,1 and encrypts Wb to generate encrypted keyword index IWb. It is shown as follows: ℬ computes Iwi∗=Ze^gx,H2wi for any keyword wi∈Wb, I1∗=gx, and Iatt=gθH1att for each attribute att in the access policy ℙ∗. Finally, ℬ sends the encrypted keyword index IWb=Iwi∗,I1∗,Iatt to A.Phase 2: A can repeat the queries of more trapdoors for keyword sets; notice that any keyword set is of his choice except for the W0,W1.Guess: finally, A outputs b′. ℬ returns 1 if b=b′; otherwise, it randomly returns.It has the following two conditions:(i)
IfZ=e^g,gxyz, A is given a ciphertext IWb, and we suppose that A wins this game with an advantage ε. Iwi∗=Ze^gθ,H2wi=e^g,gxyze^gx,H2wi (wi∈Wb)I1∗=gx, whereas α,θ are random elements, x,y,z,∈ℤp∗, let x=θ,yz=α, Iwi∗=Aθe^gθ,H2wi, I1∗=gθ, which means IWb is a valid ciphertext.SinceA has an advantage ε with its correct guess, we make a conclusion that Prℬg,gx,gy,gz,Z=e^g,gxyz=1=1/2+ε.(ii)
Otherwise,IWb is a random ciphertext. A is not able to obtain any advantage in breaking IND-CKA game, so that we have Prℬg,gx,gy,gz,Z=e^g,gγ=1=1/2.
Therefore, in the IND-CKA security game, the overall advantages ofℬ solving DBDH problems can be denoted as(14)AdvℬIND−CKAλ=1212+ε+12⋅12−12=ε2.
In other words, the advantage of a simulatorℬ solving DBDH problems is negligible because the advantage of a PPT adversary A against the IND-CKA security game is negligible. It can be said that our ABMKS-SM scheme is IND-CKA secure provided that the DBDH assumption holds. This proves the security of our scheme.


### 6.3. Performance Analysis

From the aspect of functional comparison, theoretical analysis, and experimental analysis, we show our performance.


#### 6.3.1. Functional Comparison

In terms of functionalities, mainly including attribute-based keyword search, multikeyword search, and unshared multiowner as well as shared multiowner, we compared our proposed scheme with some previous schemes, as demonstrated in Table1. One observes that our ABMKS-SM scheme has much richer capabilities that can support all the above types of functionalities at the same time, which enables our scheme to be used in IoT.Table 1
Functional comparison.
SchemeAttribute-based keyword searchMultikeyword searchUnshared multiownerShared multiowner[15]√[18]√[19]√√√[20]√[21]√√[22]√√√[23]√√[24]√√√[25]√√√Ours√√√√


#### 6.3.2. Theoretical Analysis

We analyze computation and storage costs in terms of theoretical analysis. At first, we introduce several time-consuming operations, such as hash operationH mapping to the element in group G, pairing operation Pair, multiplication operation MT in group GT, and modular exponentiation operation E (or ET) in group G (or GT). For ease of comparison, we ignore multiplication operation in group G as well as hash operation which maps to an element in ℤp∗. As shown in Table 2, we give detailed notation definitions of the performance analysis.Table 2
Notation definitions for performance analysis.
NotationDescriptionEA modular exponentiation operation time inGETA modular exponentiation operation time inGTPairA pairing operation timeMTA multiplication operation time inGTHA hash operation timemThe number of encrypting keywordsnThe number of attributestThe number of querying keywordspThe order of groupsG and GTlThe number of data ownersTo better assess the efficiency of our proposed ABMKS-SM scheme, we make a comparison of state-of-the-art CP-ABKS [15], ABKS-SM [19], and our ABMKS-SM scheme. Table 3 shows the computation costs of compared schemes. We take into account the computation costs by evaluating KeyGen, Encryption, Trapdoor, and Search algorithm. From Table 3, it is worth noticing that our construction has much more efficiency than other schemes, especially for KeyGen, Trapdoor, and Search algorithm. In KeyGen algorithm, our scheme just needs n+l+3E+H time, but the CP-ABKS and ABKS-SM scheme take 2n+2E+nH and 2n+l+4E+ET+H time, respectively. So, our scheme outperforms ABKS-SM and CP-ABKS scheme regarding the time of key generation. In Trapdoor algorithm, the computation costs of the ABKS-SM and CP-ABKS scheme increase linearly along with the number of attributes, while our ABMKS-SM construction almost remains unchanged and only takes E+tH time. Our time costs are related to the number of search keywords, but hash operation H is less than exponentiation operation E. Therefore, our construction is more superior to CP-ABKS and ABKS-SM scheme regarding generating the trapdoor time. In Search algorithm, our scheme just needs 3Pair+t+2MT time, while the time of CP-ABKS and ABKS-SM scheme is subject to the number of system attributes, so our scheme offers a much better search experience. In Encryption and Search algorithm, the number of keywords also influences the time of our scheme, but it does not reduce the search experience for data users and can support more rich functionalities; therefore, our scheme is still desirable in the Internet of things environment.Table 3
Computation cost comparison.
AlgorithmCP-ABKS [15]ABKS-SM [19]ABMKS-SM (ours)KeyGen2n+2E+nH2n+l+4E+ET+Hn+l+3E+HEncryption2n+4E+nH2l+2n+2E+3ET2l+n+2E+m+1ET+mPair+mH+m+1MTTrapdoor2n+4E2n+1EE+tHSearch2n+3Pair+nET+n+2MT2N+1Pair+ET+2n+1MT3Pair+t+2MTAs shown in Table4, we compare storage costs by evaluating KeyGen algorithm, Encryption algorithm, and Trapdoor algorithm. From Table 4, one observed that the storage costs of Trapdoor algorithm of our ABMKS-SM scheme outperform the CP-ABKS [15] and ABKS-SM [19] scheme. Along with the number of attributes growth increased in KeyGen algorithm, the storage costs of the ABKS-SM scheme and our ABMKS-SM scheme show an upward trend as a result of supporting shared multiple data owners. More concretely, our ABMKS-SM scheme achieves higher efficiency than the ABKS-SM scheme. In Encryption algorithm, our scheme’s storage costs are on the rise with the number of keywords in the encryption phase because of supporting multikeyword search. As we all know, supporting more complex functionalities can sometimes sacrifice some efficiency, but it does not bring a great influence on user search experience. Accordingly, our ABMKS-SM scheme can be accepted for more practical applications.Table 4
Storage cost comparison.
AlgorithmCP-ABKS [15]ABKS-SM [19]ABMKS-SM (ours)KeyGen2nlogp2l+2nlogp2l+nlogpEncryption2nlogpl+2nlogpn+l+mlogpTrapdoor2nlogp2nlogpnlogp


#### 6.3.3. Experimental Analysis

To validate the theoretical analysis, we implement our scheme in software by using JPBC library [49] in JRE1.8 environment. Furthermore, we simulate our experiments on the Windows 10 system with a laptop with Intel(R) Core (TM) i7-8565U CPU, 8.00 GB RAM through using Java language. In order to achieve a practical function, we choose an elliptic curve group with Type A: y2=x3+x. For ease of description, we mainly take into account several phases, such as key generation, encryption, trapdoor generation, search, and decryption process. Further, we evaluate our performance by varying the number of keywords and attributes and set m=t.As illustrated in Figure2, when the number of keywords is 10, we can see the time costs of key generation, encryption, trapdoor generation, and search process change as the number of attributes grows larger. In this case, it is shown that the computation costs of trapdoor generation, decryption, and search process have obvious advantages, which are free from the number of data user’s attributes. Moreover, the computation overheads of key generation and encryption are on the increase as the number of attributes.Figure 2
Performance evaluation for 10 keywords.Figure3 enlarges the time cost of the search algorithm in Figure 2. As illustrated in Figure 3, the time cost of the search process has almost unchanged as the number of attributes increases when the number of keywords is 10.Figure 3
Search time for 10 keywords.As illustrated in Figure4, we can see that as the number of keywords grows larger, the time costs of key generation, encryption, trapdoor generation, search, and decryption process change when the number of the data user’s attributes is 10. In this case, it is shown that the computation costs to generate keys, search, and decryption are minimal, while the costs of the encryption and trapdoor generation are on increase as the number of keywords.Figure 4
Performance evaluation for 10 attributes.Figure5 enlarges the time cost of the search algorithm in Figure 4. As illustrated in Figure 5, when the number of attributes is 10, the time cost of the search process has almost unchanged as the number of keywords increases. This is because the number of keywords is not large enough and the multiplication operation MT in group GT is the lowest when compared to other operations.Figure 5
Search time for 10 attributes.In order to clearly compare the relationship between search time and keywords, we consider removing three pairings in search time due to the high cost of pairing. As illustrated in Figure6, when the number of keywords becomes greatly larger, the computation cost of the search algorithm is proportional to the number of keywords when the attribute list satisfies the AND-gate access structure.Figure 6
Search algorithm performance (except three pairing operations).Furthermore, we show the time cost of decryption algorithm change as the number of data owners. As illustrated in Figure7, when the number of data owners becomes larger, the computation overhead of the decryption algorithm is proportional to the number of data owners.Figure 7
Decryption algorithm performance.From the above figures, we can show that our search process is more efficient than other phases, and its computation costs are free from the number of attributes. Although the computation cost of the search algorithm is proportional to the number of keywords when the attribute list satisfies the AND-gate access structure, the time cost of multiplication operationMT in group GT is the lowest. At the same time, the time cost for trapdoor generation has no relation with the number of attributes. Our scheme can significantly enhance user’s search experience, which corroborates benefits for data users to take advantage of Internet of things.


## 6.1. Correctness

IfSU satisfies the AND-gate access policy ℙ embedded in IW, while the search trapdoor and the encrypted index contain same keyword set, W′⊆W, we can verify the correctness of search algorithm indicated as (11)e^I1,Ta∏i=1tIwi=e^gθ,grgH1a∏i=1te^g,gαθe^gθ,H2wi=e^g,gαθt∏i=1te^gθ,H2wie^gθ,gre^gθ,gH1a=e^g,gαθte^gθ,∏i=1tH2wie^gθ,gre^gθ,gH1a=e^g,gαθte^gθ,∏i=1tH2wie^g,gθre^g,gθH1a,where the encryption algorithm generates Iwi and I1 and the trapdoor algorithm generates Ta.(12)e^I1,Te^g,Iatt=e^gθ,grgαt∏i=1tH2wi′e^g,gθH1att=e^gθ,gre^gθ,gαte^gθ,∏i=1tH2wi′e^g,gθH1att=e^g,gθre^g,gθαte^gθ,∏i=1tH2wi′e^g,gθH1att,where the encryption algorithm generates I1 and Iatt and the trapdoor algorithm generates T.If the identityID of the data user is authorized from multiple data owners, according to the decrypted authorizations AOjOj∈S and the private key SKU, then we can verify correctness for decryption indicated as(13)e^C″,K3∏j∈ηe^Cj,H2IDe^AOj,gφj=e^gs,gαH2IDβ∏j∈ηe^gβλjg−xj,H2IDe^H2IDxj,gφj=e^gs,gαe^gs,H2IDβe^H2IDxj,ge^g−xj,H2IDe^gβ,H2ID∑j∈ηφjλj=e^gs,gαe^gs,H2IDβe^gβ,H2IDs=e^g,gαs.


## 6.2. Security Proof

In the area of public key searchable encryption, IND-CKA secure is one of the most important security goals. By the described above security model defined inSection 4.3, we formally prove the security of ABMSK-SM construction.Theorem 1.
Our ABMKS-SM scheme is IND-CKA secure provided that the DBDH assumption holds.Proof 1.
In fact, our reduction is straightforward. Intuitively, assume that there exists an adversaryA that can break our proposed scheme. We could build a simulator ℬ who resolves DBDH problems of distinguishing the DBDH tuple gx,gy,gz,Z=e^g,gxyz and a random tuple gx,gy,gz,Z=e^g,gγ, where x,y,z,γ∈ℤp∗. Next, we formally show the following reduction.Init: at first, A chooses an AND-gate access policy ℙ∗ for challenging and returns to ℬ.Setup: ℬ selects random elements α,β∈ℤp∗ and calculates A=e^g,gα, gβ. ℬ selects one hash function H1:0,1∗⟶ℤp∗ and sets msk=α,β and pp=G,GT,p,e^,g,A,gβ.The hash queryH2wi is simulated as a random oracle model as below. If wi has not been requested previously, the simulator ℬ randomly chooses ρi∈ℤp∗ and next puts wi,ρi to the list OH2 and outputs gρi; otherwise, the simulator ℬ searches ρi from OH2 and returns gρi.Phase 1: A can query the trapdoor for keyword set W and request the queries of the following OKeyGen and OTrapdoor oracles.(1)
OKeyGen: the simulator ℬ randomly selects r∈ℤp∗ and computes K1=gr. For each attribute a∈SU, compute Ka=K1gH1a=grgH1a. ℬ returns SKU to A and stores a private key’s list LSKU.(2)
OTrapdoor: at the beginning, the simulator ℬ issues the OKeyGen oracle to gain the secret key SKU and then ℬ calculates T=grgα∏i=1tgρi and Ta=grgH1a for each attribute a∈SU. ℬ adds W to the list LW depending on SU which satisfies the access policy.Challenge: A submits ℬ two keyword sets W0,W1. Without loss of generality, W0 and W1 are not in LW. ℬ randomly chooses b∈0,1 and encrypts Wb to generate encrypted keyword index IWb. It is shown as follows: ℬ computes Iwi∗=Ze^gx,H2wi for any keyword wi∈Wb, I1∗=gx, and Iatt=gθH1att for each attribute att in the access policy ℙ∗. Finally, ℬ sends the encrypted keyword index IWb=Iwi∗,I1∗,Iatt to A.Phase 2: A can repeat the queries of more trapdoors for keyword sets; notice that any keyword set is of his choice except for the W0,W1.Guess: finally, A outputs b′. ℬ returns 1 if b=b′; otherwise, it randomly returns.It has the following two conditions:(i)
IfZ=e^g,gxyz, A is given a ciphertext IWb, and we suppose that A wins this game with an advantage ε. Iwi∗=Ze^gθ,H2wi=e^g,gxyze^gx,H2wi (wi∈Wb)I1∗=gx, whereas α,θ are random elements, x,y,z,∈ℤp∗, let x=θ,yz=α, Iwi∗=Aθe^gθ,H2wi, I1∗=gθ, which means IWb is a valid ciphertext.SinceA has an advantage ε with its correct guess, we make a conclusion that Prℬg,gx,gy,gz,Z=e^g,gxyz=1=1/2+ε.(ii)
Otherwise,IWb is a random ciphertext. A is not able to obtain any advantage in breaking IND-CKA game, so that we have Prℬg,gx,gy,gz,Z=e^g,gγ=1=1/2.
Therefore, in the IND-CKA security game, the overall advantages ofℬ solving DBDH problems can be denoted as(14)AdvℬIND−CKAλ=1212+ε+12⋅12−12=ε2.
In other words, the advantage of a simulatorℬ solving DBDH problems is negligible because the advantage of a PPT adversary A against the IND-CKA security game is negligible. It can be said that our ABMKS-SM scheme is IND-CKA secure provided that the DBDH assumption holds. This proves the security of our scheme.


## 6.3. Performance Analysis

From the aspect of functional comparison, theoretical analysis, and experimental analysis, we show our performance.


### 6.3.1. Functional Comparison

In terms of functionalities, mainly including attribute-based keyword search, multikeyword search, and unshared multiowner as well as shared multiowner, we compared our proposed scheme with some previous schemes, as demonstrated in Table1. One observes that our ABMKS-SM scheme has much richer capabilities that can support all the above types of functionalities at the same time, which enables our scheme to be used in IoT.Table 1
Functional comparison.
SchemeAttribute-based keyword searchMultikeyword searchUnshared multiownerShared multiowner[15]√[18]√[19]√√√[20]√[21]√√[22]√√√[23]√√[24]√√√[25]√√√Ours√√√√


### 6.3.2. Theoretical Analysis

We analyze computation and storage costs in terms of theoretical analysis. At first, we introduce several time-consuming operations, such as hash operationH mapping to the element in group G, pairing operation Pair, multiplication operation MT in group GT, and modular exponentiation operation E (or ET) in group G (or GT). For ease of comparison, we ignore multiplication operation in group G as well as hash operation which maps to an element in ℤp∗. As shown in Table 2, we give detailed notation definitions of the performance analysis.Table 2
Notation definitions for performance analysis.
NotationDescriptionEA modular exponentiation operation time inGETA modular exponentiation operation time inGTPairA pairing operation timeMTA multiplication operation time inGTHA hash operation timemThe number of encrypting keywordsnThe number of attributestThe number of querying keywordspThe order of groupsG and GTlThe number of data ownersTo better assess the efficiency of our proposed ABMKS-SM scheme, we make a comparison of state-of-the-art CP-ABKS [15], ABKS-SM [19], and our ABMKS-SM scheme. Table 3 shows the computation costs of compared schemes. We take into account the computation costs by evaluating KeyGen, Encryption, Trapdoor, and Search algorithm. From Table 3, it is worth noticing that our construction has much more efficiency than other schemes, especially for KeyGen, Trapdoor, and Search algorithm. In KeyGen algorithm, our scheme just needs n+l+3E+H time, but the CP-ABKS and ABKS-SM scheme take 2n+2E+nH and 2n+l+4E+ET+H time, respectively. So, our scheme outperforms ABKS-SM and CP-ABKS scheme regarding the time of key generation. In Trapdoor algorithm, the computation costs of the ABKS-SM and CP-ABKS scheme increase linearly along with the number of attributes, while our ABMKS-SM construction almost remains unchanged and only takes E+tH time. Our time costs are related to the number of search keywords, but hash operation H is less than exponentiation operation E. Therefore, our construction is more superior to CP-ABKS and ABKS-SM scheme regarding generating the trapdoor time. In Search algorithm, our scheme just needs 3Pair+t+2MT time, while the time of CP-ABKS and ABKS-SM scheme is subject to the number of system attributes, so our scheme offers a much better search experience. In Encryption and Search algorithm, the number of keywords also influences the time of our scheme, but it does not reduce the search experience for data users and can support more rich functionalities; therefore, our scheme is still desirable in the Internet of things environment.Table 3
Computation cost comparison.
AlgorithmCP-ABKS [15]ABKS-SM [19]ABMKS-SM (ours)KeyGen2n+2E+nH2n+l+4E+ET+Hn+l+3E+HEncryption2n+4E+nH2l+2n+2E+3ET2l+n+2E+m+1ET+mPair+mH+m+1MTTrapdoor2n+4E2n+1EE+tHSearch2n+3Pair+nET+n+2MT2N+1Pair+ET+2n+1MT3Pair+t+2MTAs shown in Table4, we compare storage costs by evaluating KeyGen algorithm, Encryption algorithm, and Trapdoor algorithm. From Table 4, one observed that the storage costs of Trapdoor algorithm of our ABMKS-SM scheme outperform the CP-ABKS [15] and ABKS-SM [19] scheme. Along with the number of attributes growth increased in KeyGen algorithm, the storage costs of the ABKS-SM scheme and our ABMKS-SM scheme show an upward trend as a result of supporting shared multiple data owners. More concretely, our ABMKS-SM scheme achieves higher efficiency than the ABKS-SM scheme. In Encryption algorithm, our scheme’s storage costs are on the rise with the number of keywords in the encryption phase because of supporting multikeyword search. As we all know, supporting more complex functionalities can sometimes sacrifice some efficiency, but it does not bring a great influence on user search experience. Accordingly, our ABMKS-SM scheme can be accepted for more practical applications.Table 4
Storage cost comparison.
AlgorithmCP-ABKS [15]ABKS-SM [19]ABMKS-SM (ours)KeyGen2nlogp2l+2nlogp2l+nlogpEncryption2nlogpl+2nlogpn+l+mlogpTrapdoor2nlogp2nlogpnlogp


### 6.3.3. Experimental Analysis

To validate the theoretical analysis, we implement our scheme in software by using JPBC library [49] in JRE1.8 environment. Furthermore, we simulate our experiments on the Windows 10 system with a laptop with Intel(R) Core (TM) i7-8565U CPU, 8.00 GB RAM through using Java language. In order to achieve a practical function, we choose an elliptic curve group with Type A: y2=x3+x. For ease of description, we mainly take into account several phases, such as key generation, encryption, trapdoor generation, search, and decryption process. Further, we evaluate our performance by varying the number of keywords and attributes and set m=t.As illustrated in Figure2, when the number of keywords is 10, we can see the time costs of key generation, encryption, trapdoor generation, and search process change as the number of attributes grows larger. In this case, it is shown that the computation costs of trapdoor generation, decryption, and search process have obvious advantages, which are free from the number of data user’s attributes. Moreover, the computation overheads of key generation and encryption are on the increase as the number of attributes.Figure 2
Performance evaluation for 10 keywords.Figure3 enlarges the time cost of the search algorithm in Figure 2. As illustrated in Figure 3, the time cost of the search process has almost unchanged as the number of attributes increases when the number of keywords is 10.Figure 3
Search time for 10 keywords.As illustrated in Figure4, we can see that as the number of keywords grows larger, the time costs of key generation, encryption, trapdoor generation, search, and decryption process change when the number of the data user’s attributes is 10. In this case, it is shown that the computation costs to generate keys, search, and decryption are minimal, while the costs of the encryption and trapdoor generation are on increase as the number of keywords.Figure 4
Performance evaluation for 10 attributes.Figure5 enlarges the time cost of the search algorithm in Figure 4. As illustrated in Figure 5, when the number of attributes is 10, the time cost of the search process has almost unchanged as the number of keywords increases. This is because the number of keywords is not large enough and the multiplication operation MT in group GT is the lowest when compared to other operations.Figure 5
Search time for 10 attributes.In order to clearly compare the relationship between search time and keywords, we consider removing three pairings in search time due to the high cost of pairing. As illustrated in Figure6, when the number of keywords becomes greatly larger, the computation cost of the search algorithm is proportional to the number of keywords when the attribute list satisfies the AND-gate access structure.Figure 6
Search algorithm performance (except three pairing operations).Furthermore, we show the time cost of decryption algorithm change as the number of data owners. As illustrated in Figure7, when the number of data owners becomes larger, the computation overhead of the decryption algorithm is proportional to the number of data owners.Figure 7
Decryption algorithm performance.From the above figures, we can show that our search process is more efficient than other phases, and its computation costs are free from the number of attributes. Although the computation cost of the search algorithm is proportional to the number of keywords when the attribute list satisfies the AND-gate access structure, the time cost of multiplication operationMT in group GT is the lowest. At the same time, the time cost for trapdoor generation has no relation with the number of attributes. Our scheme can significantly enhance user’s search experience, which corroborates benefits for data users to take advantage of Internet of things.


## 6.3.1. Functional Comparison

In terms of functionalities, mainly including attribute-based keyword search, multikeyword search, and unshared multiowner as well as shared multiowner, we compared our proposed scheme with some previous schemes, as demonstrated in Table1. One observes that our ABMKS-SM scheme has much richer capabilities that can support all the above types of functionalities at the same time, which enables our scheme to be used in IoT.Table 1
Functional comparison.
SchemeAttribute-based keyword searchMultikeyword searchUnshared multiownerShared multiowner[15]√[18]√[19]√√√[20]√[21]√√[22]√√√[23]√√[24]√√√[25]√√√Ours√√√√


## 6.3.2. Theoretical Analysis

We analyze computation and storage costs in terms of theoretical analysis. At first, we introduce several time-consuming operations, such as hash operationH mapping to the element in group G, pairing operation Pair, multiplication operation MT in group GT, and modular exponentiation operation E (or ET) in group G (or GT). For ease of comparison, we ignore multiplication operation in group G as well as hash operation which maps to an element in ℤp∗. As shown in Table 2, we give detailed notation definitions of the performance analysis.Table 2
Notation definitions for performance analysis.
NotationDescriptionEA modular exponentiation operation time inGETA modular exponentiation operation time inGTPairA pairing operation timeMTA multiplication operation time inGTHA hash operation timemThe number of encrypting keywordsnThe number of attributestThe number of querying keywordspThe order of groupsG and GTlThe number of data ownersTo better assess the efficiency of our proposed ABMKS-SM scheme, we make a comparison of state-of-the-art CP-ABKS [15], ABKS-SM [19], and our ABMKS-SM scheme. Table 3 shows the computation costs of compared schemes. We take into account the computation costs by evaluating KeyGen, Encryption, Trapdoor, and Search algorithm. From Table 3, it is worth noticing that our construction has much more efficiency than other schemes, especially for KeyGen, Trapdoor, and Search algorithm. In KeyGen algorithm, our scheme just needs n+l+3E+H time, but the CP-ABKS and ABKS-SM scheme take 2n+2E+nH and 2n+l+4E+ET+H time, respectively. So, our scheme outperforms ABKS-SM and CP-ABKS scheme regarding the time of key generation. In Trapdoor algorithm, the computation costs of the ABKS-SM and CP-ABKS scheme increase linearly along with the number of attributes, while our ABMKS-SM construction almost remains unchanged and only takes E+tH time. Our time costs are related to the number of search keywords, but hash operation H is less than exponentiation operation E. Therefore, our construction is more superior to CP-ABKS and ABKS-SM scheme regarding generating the trapdoor time. In Search algorithm, our scheme just needs 3Pair+t+2MT time, while the time of CP-ABKS and ABKS-SM scheme is subject to the number of system attributes, so our scheme offers a much better search experience. In Encryption and Search algorithm, the number of keywords also influences the time of our scheme, but it does not reduce the search experience for data users and can support more rich functionalities; therefore, our scheme is still desirable in the Internet of things environment.Table 3
Computation cost comparison.
AlgorithmCP-ABKS [15]ABKS-SM [19]ABMKS-SM (ours)KeyGen2n+2E+nH2n+l+4E+ET+Hn+l+3E+HEncryption2n+4E+nH2l+2n+2E+3ET2l+n+2E+m+1ET+mPair+mH+m+1MTTrapdoor2n+4E2n+1EE+tHSearch2n+3Pair+nET+n+2MT2N+1Pair+ET+2n+1MT3Pair+t+2MTAs shown in Table4, we compare storage costs by evaluating KeyGen algorithm, Encryption algorithm, and Trapdoor algorithm. From Table 4, one observed that the storage costs of Trapdoor algorithm of our ABMKS-SM scheme outperform the CP-ABKS [15] and ABKS-SM [19] scheme. Along with the number of attributes growth increased in KeyGen algorithm, the storage costs of the ABKS-SM scheme and our ABMKS-SM scheme show an upward trend as a result of supporting shared multiple data owners. More concretely, our ABMKS-SM scheme achieves higher efficiency than the ABKS-SM scheme. In Encryption algorithm, our scheme’s storage costs are on the rise with the number of keywords in the encryption phase because of supporting multikeyword search. As we all know, supporting more complex functionalities can sometimes sacrifice some efficiency, but it does not bring a great influence on user search experience. Accordingly, our ABMKS-SM scheme can be accepted for more practical applications.Table 4
Storage cost comparison.
AlgorithmCP-ABKS [15]ABKS-SM [19]ABMKS-SM (ours)KeyGen2nlogp2l+2nlogp2l+nlogpEncryption2nlogpl+2nlogpn+l+mlogpTrapdoor2nlogp2nlogpnlogp


## 6.3.3. Experimental Analysis

To validate the theoretical analysis, we implement our scheme in software by using JPBC library [49] in JRE1.8 environment. Furthermore, we simulate our experiments on the Windows 10 system with a laptop with Intel(R) Core (TM) i7-8565U CPU, 8.00 GB RAM through using Java language. In order to achieve a practical function, we choose an elliptic curve group with Type A: y2=x3+x. For ease of description, we mainly take into account several phases, such as key generation, encryption, trapdoor generation, search, and decryption process. Further, we evaluate our performance by varying the number of keywords and attributes and set m=t.As illustrated in Figure2, when the number of keywords is 10, we can see the time costs of key generation, encryption, trapdoor generation, and search process change as the number of attributes grows larger. In this case, it is shown that the computation costs of trapdoor generation, decryption, and search process have obvious advantages, which are free from the number of data user’s attributes. Moreover, the computation overheads of key generation and encryption are on the increase as the number of attributes.Figure 2
Performance evaluation for 10 keywords.Figure3 enlarges the time cost of the search algorithm in Figure 2. As illustrated in Figure 3, the time cost of the search process has almost unchanged as the number of attributes increases when the number of keywords is 10.Figure 3
Search time for 10 keywords.As illustrated in Figure4, we can see that as the number of keywords grows larger, the time costs of key generation, encryption, trapdoor generation, search, and decryption process change when the number of the data user’s attributes is 10. In this case, it is shown that the computation costs to generate keys, search, and decryption are minimal, while the costs of the encryption and trapdoor generation are on increase as the number of keywords.Figure 4
Performance evaluation for 10 attributes.Figure5 enlarges the time cost of the search algorithm in Figure 4. As illustrated in Figure 5, when the number of attributes is 10, the time cost of the search process has almost unchanged as the number of keywords increases. This is because the number of keywords is not large enough and the multiplication operation MT in group GT is the lowest when compared to other operations.Figure 5
Search time for 10 attributes.In order to clearly compare the relationship between search time and keywords, we consider removing three pairings in search time due to the high cost of pairing. As illustrated in Figure6, when the number of keywords becomes greatly larger, the computation cost of the search algorithm is proportional to the number of keywords when the attribute list satisfies the AND-gate access structure.Figure 6
Search algorithm performance (except three pairing operations).Furthermore, we show the time cost of decryption algorithm change as the number of data owners. As illustrated in Figure7, when the number of data owners becomes larger, the computation overhead of the decryption algorithm is proportional to the number of data owners.Figure 7
Decryption algorithm performance.From the above figures, we can show that our search process is more efficient than other phases, and its computation costs are free from the number of attributes. Although the computation cost of the search algorithm is proportional to the number of keywords when the attribute list satisfies the AND-gate access structure, the time cost of multiplication operationMT in group GT is the lowest. At the same time, the time cost for trapdoor generation has no relation with the number of attributes. Our scheme can significantly enhance user’s search experience, which corroborates benefits for data users to take advantage of Internet of things.


## 7. Conclusion

In this paper, we design a novel attribute-based multikeyword search for shared multiowner (ABMKS-SM) scheme in Internet of things and it can support to search multikeyword on ciphertexts with enhancing fine-grained access control. The most important security goal of public key searchable encryption is IND-CKA secure. We give this formal model definition and achieve IND-CKA security. Finally, we evaluate our performance with respect to functional, theoretical, and experimental analysis and further show our efficiency and practicality. Results demonstrate that time costs to search are free from the number of attributes; meanwhile, the costs for trapdoor generation are not related to the number of attributes. Last but not least, our proposed scheme makes full use of the benefits brought by cloud computing and Internet of things and is acceptable in practice.



---

*Source: 6649119-2021-05-24.xml*