# Multiauthority Attribute-Based Keyword Search over Cloud-Edge-End Collaboration in IoV

Authors: Yan Zhen; Yilan Chui; Puning Zhang; Huan Liu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

The development of cloud computing and edge computing makes it possible to store and share Internet of Vehicles (IoV) data on a large scale, which greatly contributes to traffic intelligence, but outsourced data confidentiality and user privacy cannot be guaranteed. The Ciphertext Policy Attribute-Based Encryption (CP-ABE) scheme can achieve both fine-grained access control and secure data sharing. However, existing CP-ABE schemes owns high computational complexity, and the adopted single attribute authority mode is burdensome to resource-limited IoV. Thus, this paper proposes a Multiauthority Attribute-Based Keyword Search over Cloud-Edge-End Collaboration (CEABKS-MA) system, leveraging the benefits of edge and cloud resources and effectively combining with the multiauthority structure to minimize the computation and storage pressure on resource-limited parties in the system. In addition, fine-grained keyword search with support for attribute update and lightweight encryption/decryption is extended. Finally, this paper demonstrates the security and efficiency of the CEABKS-MA system through rigorous security analysis and simulation experiments.


---

## Body

## 1. Introduction

IoV collects and transmits vehicle data to the network through in-vehicle sensing devices, which largely facilitates intelligent transportation system [1–3]. Currently, with the development of IoV technology and the increase in the number of vehicles, users’ demands for intelligent access to vehicle information are increasing. Since IoV data usually includes users’ private information (e.g., vehicle location), privacy protection becomes a key factor affecting IoV user search experience. However, in-vehicle networks exposed to unprotected environments are more vulnerable to security threats in data storage, transmission, and sharing [4, 5] and have limited computation and storage capacity to effectively support secure sharing of IoV data.Outsourcing massive amounts of data to the cloud and edge can effectively alleviate the resource-limited issue of IoV devices and facilitate data sharing, but the cloud and edge are usually perceived as “honest and curious” [6, 7], meaning they will honor agreements honestly but may have unauthorized access to some sensitive data. Hence, the searchable encryption (SE) [8] is proposed to support outsourced data encryption and enable keyword search in the ciphertext domain, where special encryption algorithms are used by data owners and search users for encryption of plaintext data, indexes, and queries to perform accurate or near-accurate keyword matching operations on the ciphertext.Facing the massive amount of IoV data, fine-grained access control to the data in secure retrieval is of great importance to users. The CP-ABE scheme [9, 10] embeds the access policy into the ciphertext; the user can decrypt the ciphertext only when the user attributes satisfy the policy; thus, the data owner can control the access to the data, which is ideal for dynamic IoV environments. However, most existing CP-ABE schemes are mainly based on cloud computing architecture [11, 12] and are designed for single attribute authority scenarios [13–15] and have high computational complexity. Among them, centralized cloud computing imposes a heavy computation and storage burden on cloud servers, and remote cloud-oriented data transmissions cause high communication cost and large latency [16–18]. As user registration and key generation of single attribute authority are resource-intensive and time-consuming, which may lead to the failure of single-point attribute authority and serious consequences such as key and user privacy leakage, ultimately affecting the availability of search system. Besides, multiple types of sensing devices are deployed on vehicles to collect corresponding vehicle attribute data, while users may only need vehicle data for a certain attribute; traditional keyword search will return ciphertext for all attributes of the vehicle, which will bring additional computation consumption and communication overhead for users.Compared with centralized cloud computing, cloud-edge-end collaborative architecture can effectively reduce search latency and the computational load on the cloud by fusing the advantages of the edge being closer to users and the cloud having abundant resources [19–21]. Figure 1 illustrates the IoV cloud-edge-end collaborative architecture. Therefore, this paper designs a multiauthority attribute keyword search (CEABKS-MA) system based on cloud-edge-end collaboration, which can effectively reduce the computation and storage burden of resource-constrained parties in the system and achieve efficient and secure fine-grained keyword retrieval for IoV data. The main contributions of this paper are as follows:
(i)
Fine-grained keyword search with support for attribute update and lightweight encryption is extended in access control. Vehicles carrying multiple sensors are abstracted into one or more attributes to enable retrieval of specified vehicle attributes. The attribute update function effectively prevents malicious users from stealing who revoke attributes, and the online/offline encryption method further reduces the computation burden on users(ii)
A cloud-edge-end collaborative search method is proposed, where users can achieve real-time and historical search by sending a trapdoor to the nearest edge. Besides, the edge provides a ciphertext predecryption service, and the search user can obtain plaintext data by performing a simple calculation(iii)
A multiauthority structure is designed to implement distributed key management, which decentralizes the expensive and time-consuming key generation and distribution tasks of the central authority to each attribute authority, which can better adapt to the spatial characteristics of vehicles and distributed IoV topologyFigure 1
IoV cloud-edge-end collaborative architecture.The main content of this paper is as follows. Section2 discusses related work. Section 3 introduces preparatory knowledge. Section 4 presents the system model, formal definition, and security model. Section 5 describes in detail the construction of the CEABKS-MA system. Section 6 analyzes the security and performance of the CEABKS-MA system. Section 7 concludes this paper.


## 2. Related Work

This section includes three parts: (1) searchable encryption, (2) privacy-preserving in IoV, and (3) secure data sharing in IoV.


### 2.1. Searchable Encryption

With a large number of data owners outsourcing critical private data to access rich computational and storage resources at a lower cost, the SE scheme that enables encrypted data retrieval is widely studied and applied [22–24]. Song et al. [8] first introduced a symmetric search encryption (SSE) scheme in 2000 to enable a single keyword search over ciphertext. Boneh et al. [25] proposed the first Public-Key Encrypted Keyword Search (PEKS) scheme, which has a broader application scenario than the SSE scheme and can support secure data sharing among multiple data owners. Sahai and Waters [26] introduced an Attribute-Based Encryption (ABE) scheme in 2005, which supports one-to-many encryption, greatly reduces the number of keys generated, and is an effective way to achieve fine-grained access control, and since then, researchers have studied the ABE scheme extensively.The ABE scheme mainly consists of Key-Policy ABE (KP-ABE) [27] and Ciphertext-Policy ABE (CP-ABE) [28]. Bethencourt et al. [28] first proposed the CP-ABE scheme in 2007, by using attributes to express the user’s authentication credentials and tokenizing the key; the user could decrypt the ciphertext if the set of attributes hidden in the user’s key matched the access policy embedded in the ciphertext by the data owner, which was more suitable for dynamic scenarios than the KP-ABE scheme that embeds the access policy in the key. Keyword search is an effective way to help users rapidly filter the data they need, based on which researchers have conducted extensive research on Ciphertext Policy Attribute-Based Keyword Search (CP-ABKS) [29–31]. Qiu et al. [29] devised an attribute keyword search scheme that could resist keyword guessing attacks to maintain the indistinguishability of keywords and access structures. Miao et al. [30] presented an attribute-based encrypted keyword search scheme for verifiable attributes and consider the access rights of the same data based on the priority tree of the attributes. Zhang et al. [31] designed a lightweight searchable encryption protocol for industrial IoT that can provide users with connected keyword search while extending the scheme to multiauthority scenarios to efficiently generate and manage keys, but the system did not have the attribute update function and was less dynamic.


### 2.2. Privacy-Preserving in IoV

With the large amount of sensitive data in IoV being collected by sensors carried by vehicles, the issue of user privacy protection involved in the collection, transmission, and storage of vehicle data has received a lot of attention from researchers. Wu et al. [32] focused on vehicle anonymity and driving privacy in IoV by designing a privacy-preserving system equipped with a priori and a posteriori countermeasures for message verification thereby improving the reliability of vehicle-to-vehicle (V2V) communication. Kumar et al. [33] proposed a privacy-preserving IoV framework based on blockchain technology and built a deep learning module to detect data in the blockchain to guarantee data security. Zhou et al. [34] considered the location privacy problem of the designed EVN architecture and introduced edge computing to propose a differentiated privacy-preserving service framework. Kang et al. [35] used fog computing to achieve effective user location privacy protection and avoided high latency and cost problems. Wu et al. [36] focused on privacy leakage when computing tasks were offloaded in IoV scenarios, quantifying the potential threats when vehicle users offloaded computing tasks based on physical layer security theory.The above schemes have effectively investigated data privacy protection in IoV, but they mainly focus on vehicle location privacy or data storage privacy and do not expand much on secure retrieval and sharing of IoV data.


### 2.3. Secure Data Sharing in IoV

Data sharing can further increase the value of IoV data utilization; as users are increasingly concerned about privacy protection when performing information retrieval, researchers have conducted preliminary studies on IoV data secure retrieval using existing technologies. Chen et al. [37] designed an IoV data sharing incentive mechanism based on the tamper-proof performance of blockchain to ensure the integrity of data on the chain. Cui et al. [38] designed a traceable and anonymous V2V data sharing using federated blockchain technology to track the origin of data and prevent data from being shared twice by malicious users, but the above two schemes are difficult to support the user’s flexible data retrieval needs.Several studies have improved the ABE scheme in secure retrieval of IoV data and fine-grained access control. Wang et al. [39] extended ground-based IoV scenarios to Space-Air-Ground Integrated Vehicular Networks (SAGIN); a valid keyword conversion algorithm based on a single lattice algorithm and particle encryption is proposed to achieve fuzzy retrieval, and keyword weights are calculated using dependency grammar and phrase structure tree to improve retrieval precision. Zhang et al. [40] proposed a secure retrieval scheme for IoV data based on cloud-fog collaboration, focusing on the problem of accessing sensitive data by malicious users whose attributes are revoked, proposing the concept of auditable user revocation, and giving a verifiable online/offline calculation method. Considering the problems of high computational consumption and low efficiency of serial outsourcing decryption of the ABE scheme, Feng et al. [41] introduced the edge computing to support parallel outsourcing decryption, and the designed scheme can be extended to existing ABE schemes built based on tree structure and linear secret sharing.However, the above studies utilize the single attribute authority for complex key generation and management tasks when building a secure retrieval scheme for IoV data in combination with an ABE scheme, which is prone to the single-point performance bottleneck. In addition, for IoV scenarios, the computational complexity of the scheme should be minimized without sacrificing efficiency and security.


## 2.1. Searchable Encryption

With a large number of data owners outsourcing critical private data to access rich computational and storage resources at a lower cost, the SE scheme that enables encrypted data retrieval is widely studied and applied [22–24]. Song et al. [8] first introduced a symmetric search encryption (SSE) scheme in 2000 to enable a single keyword search over ciphertext. Boneh et al. [25] proposed the first Public-Key Encrypted Keyword Search (PEKS) scheme, which has a broader application scenario than the SSE scheme and can support secure data sharing among multiple data owners. Sahai and Waters [26] introduced an Attribute-Based Encryption (ABE) scheme in 2005, which supports one-to-many encryption, greatly reduces the number of keys generated, and is an effective way to achieve fine-grained access control, and since then, researchers have studied the ABE scheme extensively.The ABE scheme mainly consists of Key-Policy ABE (KP-ABE) [27] and Ciphertext-Policy ABE (CP-ABE) [28]. Bethencourt et al. [28] first proposed the CP-ABE scheme in 2007, by using attributes to express the user’s authentication credentials and tokenizing the key; the user could decrypt the ciphertext if the set of attributes hidden in the user’s key matched the access policy embedded in the ciphertext by the data owner, which was more suitable for dynamic scenarios than the KP-ABE scheme that embeds the access policy in the key. Keyword search is an effective way to help users rapidly filter the data they need, based on which researchers have conducted extensive research on Ciphertext Policy Attribute-Based Keyword Search (CP-ABKS) [29–31]. Qiu et al. [29] devised an attribute keyword search scheme that could resist keyword guessing attacks to maintain the indistinguishability of keywords and access structures. Miao et al. [30] presented an attribute-based encrypted keyword search scheme for verifiable attributes and consider the access rights of the same data based on the priority tree of the attributes. Zhang et al. [31] designed a lightweight searchable encryption protocol for industrial IoT that can provide users with connected keyword search while extending the scheme to multiauthority scenarios to efficiently generate and manage keys, but the system did not have the attribute update function and was less dynamic.


## 2.2. Privacy-Preserving in IoV

With the large amount of sensitive data in IoV being collected by sensors carried by vehicles, the issue of user privacy protection involved in the collection, transmission, and storage of vehicle data has received a lot of attention from researchers. Wu et al. [32] focused on vehicle anonymity and driving privacy in IoV by designing a privacy-preserving system equipped with a priori and a posteriori countermeasures for message verification thereby improving the reliability of vehicle-to-vehicle (V2V) communication. Kumar et al. [33] proposed a privacy-preserving IoV framework based on blockchain technology and built a deep learning module to detect data in the blockchain to guarantee data security. Zhou et al. [34] considered the location privacy problem of the designed EVN architecture and introduced edge computing to propose a differentiated privacy-preserving service framework. Kang et al. [35] used fog computing to achieve effective user location privacy protection and avoided high latency and cost problems. Wu et al. [36] focused on privacy leakage when computing tasks were offloaded in IoV scenarios, quantifying the potential threats when vehicle users offloaded computing tasks based on physical layer security theory.The above schemes have effectively investigated data privacy protection in IoV, but they mainly focus on vehicle location privacy or data storage privacy and do not expand much on secure retrieval and sharing of IoV data.


## 2.3. Secure Data Sharing in IoV

Data sharing can further increase the value of IoV data utilization; as users are increasingly concerned about privacy protection when performing information retrieval, researchers have conducted preliminary studies on IoV data secure retrieval using existing technologies. Chen et al. [37] designed an IoV data sharing incentive mechanism based on the tamper-proof performance of blockchain to ensure the integrity of data on the chain. Cui et al. [38] designed a traceable and anonymous V2V data sharing using federated blockchain technology to track the origin of data and prevent data from being shared twice by malicious users, but the above two schemes are difficult to support the user’s flexible data retrieval needs.Several studies have improved the ABE scheme in secure retrieval of IoV data and fine-grained access control. Wang et al. [39] extended ground-based IoV scenarios to Space-Air-Ground Integrated Vehicular Networks (SAGIN); a valid keyword conversion algorithm based on a single lattice algorithm and particle encryption is proposed to achieve fuzzy retrieval, and keyword weights are calculated using dependency grammar and phrase structure tree to improve retrieval precision. Zhang et al. [40] proposed a secure retrieval scheme for IoV data based on cloud-fog collaboration, focusing on the problem of accessing sensitive data by malicious users whose attributes are revoked, proposing the concept of auditable user revocation, and giving a verifiable online/offline calculation method. Considering the problems of high computational consumption and low efficiency of serial outsourcing decryption of the ABE scheme, Feng et al. [41] introduced the edge computing to support parallel outsourcing decryption, and the designed scheme can be extended to existing ABE schemes built based on tree structure and linear secret sharing.However, the above studies utilize the single attribute authority for complex key generation and management tasks when building a secure retrieval scheme for IoV data in combination with an ABE scheme, which is prone to the single-point performance bottleneck. In addition, for IoV scenarios, the computational complexity of the scheme should be minimized without sacrificing efficiency and security.


## 3. Preliminaries

### 3.1. Bilinear Groups

Assume thatG,GT are two multiplicative cyclic groups of order p, where p is a prime, g is a generator of G, and the bilinear mapping e:G×G⟶GT has the following properties:
(1)
Bilinear. ega,gb=eg,gab, ∀a,b∈Zp(2)
Nondegeneracy. eg,g≠1(3)
Computability. ∀x,y∈G, there exists a valid polynomial-time algorithm to compute the value of ex,y


### 3.2. Access Structure

LetP=P1,P2,⋯,Pn be a set of attributes, and the access structure Λ⊆2P is monotonic. The access structure Λ is a nonempty subset of the set 2P, the sets in Λ are authorized sets, and the sets not in Λ are unauthorized sets.


### 3.3. Linear Secret Sharing Scheme (LSSS)

If the following conditions both hold, an LSSS overP is linear.
(1)
The sharing of each attribute forms a vector onZP(2)
LetM (l×n) be the shared matrix of LSSS to describe the access structure Λ, the ith row is defined as Mii∈1,l, and the mapping function ρ. maps each row Mi to a certain attribute ρi. Given a randomly chosen vector x=s,y1,y2,⋯,yn∈ZPn, where s is the shared secret value, then MxT represents the l shares of s in LSSS, where the shared Mix belongs to a attribute ρi, denoted as λi=MixThe LSSS defined in the above way is reconfigurable: assume thatM,ρ denotes the access structure Λ of the LSSS, the set of authorized users S∈Λ, and define I=i,ρi∈S⊆1,2,⋯,l. There exists ω=ωi∈ZPi∈I such that ∑i∈IωiMi=1,0,⋯,0, and thus, ∑i∈IωiMix=∑i∈Iωiλi=s.


## 3.1. Bilinear Groups

Assume thatG,GT are two multiplicative cyclic groups of order p, where p is a prime, g is a generator of G, and the bilinear mapping e:G×G⟶GT has the following properties:
(1)
Bilinear. ega,gb=eg,gab, ∀a,b∈Zp(2)
Nondegeneracy. eg,g≠1(3)
Computability. ∀x,y∈G, there exists a valid polynomial-time algorithm to compute the value of ex,y


## 3.2. Access Structure

LetP=P1,P2,⋯,Pn be a set of attributes, and the access structure Λ⊆2P is monotonic. The access structure Λ is a nonempty subset of the set 2P, the sets in Λ are authorized sets, and the sets not in Λ are unauthorized sets.


## 3.3. Linear Secret Sharing Scheme (LSSS)

If the following conditions both hold, an LSSS overP is linear.
(1)
The sharing of each attribute forms a vector onZP(2)
LetM (l×n) be the shared matrix of LSSS to describe the access structure Λ, the ith row is defined as Mii∈1,l, and the mapping function ρ. maps each row Mi to a certain attribute ρi. Given a randomly chosen vector x=s,y1,y2,⋯,yn∈ZPn, where s is the shared secret value, then MxT represents the l shares of s in LSSS, where the shared Mix belongs to a attribute ρi, denoted as λi=MixThe LSSS defined in the above way is reconfigurable: assume thatM,ρ denotes the access structure Λ of the LSSS, the set of authorized users S∈Λ, and define I=i,ρi∈S⊆1,2,⋯,l. There exists ω=ωi∈ZPi∈I such that ∑i∈IωiMi=1,0,⋯,0, and thus, ∑i∈IωiMix=∑i∈Iωiλi=s.


## 4. System Model and Definition

### 4.1. System Model

As shown in Figure2, the system model involves six main participants, namely, central authority (CA), multiple attribute authorities (AAs), vehicle node (VN), multiple edge servers (ESs), cloud server (CS), and search user (SU).
(i)
Central Authority. The CA is responsible for initializing the system and registrating multiple SUs and AAs(ii)
Attribute Authority. Each AA is independent of the other, and there is no intersection between the attributes managed. The AA is responsible for the generation and distribution of user keys within the domain and supports attribute updates for authorized users(iii)
Vehicle Node. Different kinds of sensors carried by vehicles observe the vehicle status in real-time, and the VN obtains an attribute-based access structure from AA to encrypt and upload the collected vehicle datasets to the nearest ES(iv)
Edge Server. The ES is mainly responsible for the following three tasks. First, it stores vehicle instant ciphertext and forwards vehicle historical ciphertext to CS. Second, it provides instant search service to SU and forwards trapdoor from SU to CS to realize historical search. Third, it provides ciphertext predecryption service to SU whose attributes satisfy the access structure(v)
Cloud Server. The CS provides outsourced storage and search service for the vehicle historical ciphertext. In addition, the CS sends the matching ciphertext to ES for predecryption after an accurate keyword search(vi)
Search User. The SU obtains the secret key from AA and wishes to freely access ciphertext resources in ES or CS without compromising privacy while reducing the computational burden of decrypting the ciphertextFigure 2
Cloud-edge-end collaborative multiauthority attribute encrypted search model in IoV.In the CEABKS-MA system, the CA and multiple AAs, as fully trusted third parties, are real-time online and have sufficient computing and storage resources to perform tasks such as system initialization and key distribution. The CS and multiple ESs are “honest and curious”; they perform ciphertext storage and search services honestly but may try to obtain more private data without authorization.


### 4.2. Formal Definition

LetSA=AA1,AA2⋯,AAN denote the set of multiple AAs, the AAjj∈1,N has a set of attributes Lj=att1,j,att2,j,⋯,attU,j, and the number of attributes managed by AAj is denoted as Uj. The proposed CEABKS-MA system includes the following polynomial-time algorithms.
(1)
CAsetupκ⟶PP,MSK. Given the security parameter κ, the CA generates the public parameters PP and the master key MSK, while generates a unique identifier uid for each authorized SU(2)
AAsetupPP⟶ASKj,APKj. Given the public parameters PP, the AAj generates an attribute public key APKj and an attribute private key ASKj for each set of attributes it manages(3)
KeygenPP,MSK,Sj,uid,ASKj⟶USKj,uid. Sj,uid denotes the set of attributes received by SUuid from AAj, where Sj,uid⊆Lj; then, the AAj generates the key USKj,uid associated with the set of attributes for SUuid and sends it to SUuid(4)
PreKeygenz,USKj,uid⟶PSKj,uid. The SUuid randomly selects the blind value z to send it to AAj; then, the AAj executes this algorithm to generate the predecryption key PSKj,uid according to USKj,uid and sends it to ES(5)
EncryptPP,APKj,E,kw,M,ρ⟶CT. Given the vehicle plaintext dataset E, the vehicle attribute keywords kw, and the access structure M,ρ, the VN outputs the ciphertext CT, which includes the encrypted index set IE and the encrypted dataset CE(6)
TrapdoorPP,USKj,uid,kw′⟶Tkw′. Given the query keyword set kw′, the SUuid generates the trapdoor Tkw′ according to the secret key USKj,uid and sends it to ES(7)
SearchCT,Tkw′⟶0,1. Given the trapdoor Tkw′ and the ciphertext CT, the ES or CS conducts the search algorithm, if the query is successful, outputs “1” and performs the ciphertext predecryption operation, otherwise, outputs “0”(8)
EdgeDecCT,PSKj,uid⟶CTout. Given the ciphertext CT and the predecryption key PSKj,uid, the ES outputs the partially decrypted ciphertext CTout and sends it to SUuid(9)
DecCTout,z⟶skEa. Take the partially decrypted ciphertext CTout as input, and the SUuid performs this algorithm to decrypt the ciphertext lightly using the blind value z(10)
UpdateCT,ASK′i,j,APK′i,j,v′i⟶v^′i. Given the ciphertext CT and the attribute update public key APK′i,j for key and ciphertext update


### 4.3. Secure Model

To protect the confidentiality of vehicle data, unauthorized CS, ESs, and SUs cannot access any plaintext information. The CEABKS-MA system proposed in this paper enables the Indistinguishability of Chosen Plaintext Attack (IND-CPA) [42], as well as the Indistinguishability of Chosen Keyword Attack (IND-CKA) [43]. In this subsection, we define the following interactive game between challenger B and adversary A.
(1)
IND-CPA securityInitialization. Adversary A announces a challenging access structure Λ∗ and sends it to challenger B.Setup. B first runs the Setup algorithm, outputs the public key PK, and sends it to A.Phase 1. A can adaptively send any attribute set S to B, but the restriction is that all submitted attribute sets cannot satisfy Λ∗. For each attribute set S, A executes the Keygen algorithm to output the key and sends it to B. Moreover, A can make any queries for updated key related to the canceled attribute v′i.Challenge. A selects two messages m0,m1 of equal length and sends them to B; then, B randomly selects κ∈0,1 and uses Λ∗ to encrypt mκ. Finally, B returns the challenging ciphertext Cκ to A.Phase 2. A repeats Phase 1 for other sets of attributes, but none of them satisfy Λ∗.Guess. A outputs κ′∈0,1, if κ′=κ, then wins the security game; otherwise, it fails.
(2)
IND-CKA securityDefinition 1.
If the advantage of winning the above game in any polynomial-time adversary is negligible, then the CEABKS-MA system is IND-CPA security.Setup. B outputs the public key PK and sends it to A.Phase 1. A can query OKeygen and OTrap for keys and trapdoors in polynomial time.
(i)
OKeygen. B invokes Keygen to generate the corresponding key SK and sends it to A(ii)
OTrap. A submits a keyword kw′ of interest, and B executes the Trap algorithm to generate the trapdoor Tkw′ and sends it to AChallenge. A selects two keywords kw0,kw1 with the same length, and then, B randomly selects κ∈0,1, generates index Ikwκ, and returns it to A.Phase 2. The process of Phase 2 is similar to that of Phase 1.Guess. A outputs κ′∈0,1, if κ′=κ, then wins the security game; otherwise, it fails.Definition 2.
If the advantage of winning the above game in any polynomial-time adversary is negligible, then the CEABKS-MA system is IND-CKA security.


## 4.1. System Model

As shown in Figure2, the system model involves six main participants, namely, central authority (CA), multiple attribute authorities (AAs), vehicle node (VN), multiple edge servers (ESs), cloud server (CS), and search user (SU).
(i)
Central Authority. The CA is responsible for initializing the system and registrating multiple SUs and AAs(ii)
Attribute Authority. Each AA is independent of the other, and there is no intersection between the attributes managed. The AA is responsible for the generation and distribution of user keys within the domain and supports attribute updates for authorized users(iii)
Vehicle Node. Different kinds of sensors carried by vehicles observe the vehicle status in real-time, and the VN obtains an attribute-based access structure from AA to encrypt and upload the collected vehicle datasets to the nearest ES(iv)
Edge Server. The ES is mainly responsible for the following three tasks. First, it stores vehicle instant ciphertext and forwards vehicle historical ciphertext to CS. Second, it provides instant search service to SU and forwards trapdoor from SU to CS to realize historical search. Third, it provides ciphertext predecryption service to SU whose attributes satisfy the access structure(v)
Cloud Server. The CS provides outsourced storage and search service for the vehicle historical ciphertext. In addition, the CS sends the matching ciphertext to ES for predecryption after an accurate keyword search(vi)
Search User. The SU obtains the secret key from AA and wishes to freely access ciphertext resources in ES or CS without compromising privacy while reducing the computational burden of decrypting the ciphertextFigure 2
Cloud-edge-end collaborative multiauthority attribute encrypted search model in IoV.In the CEABKS-MA system, the CA and multiple AAs, as fully trusted third parties, are real-time online and have sufficient computing and storage resources to perform tasks such as system initialization and key distribution. The CS and multiple ESs are “honest and curious”; they perform ciphertext storage and search services honestly but may try to obtain more private data without authorization.


## 4.2. Formal Definition

LetSA=AA1,AA2⋯,AAN denote the set of multiple AAs, the AAjj∈1,N has a set of attributes Lj=att1,j,att2,j,⋯,attU,j, and the number of attributes managed by AAj is denoted as Uj. The proposed CEABKS-MA system includes the following polynomial-time algorithms.
(1)
CAsetupκ⟶PP,MSK. Given the security parameter κ, the CA generates the public parameters PP and the master key MSK, while generates a unique identifier uid for each authorized SU(2)
AAsetupPP⟶ASKj,APKj. Given the public parameters PP, the AAj generates an attribute public key APKj and an attribute private key ASKj for each set of attributes it manages(3)
KeygenPP,MSK,Sj,uid,ASKj⟶USKj,uid. Sj,uid denotes the set of attributes received by SUuid from AAj, where Sj,uid⊆Lj; then, the AAj generates the key USKj,uid associated with the set of attributes for SUuid and sends it to SUuid(4)
PreKeygenz,USKj,uid⟶PSKj,uid. The SUuid randomly selects the blind value z to send it to AAj; then, the AAj executes this algorithm to generate the predecryption key PSKj,uid according to USKj,uid and sends it to ES(5)
EncryptPP,APKj,E,kw,M,ρ⟶CT. Given the vehicle plaintext dataset E, the vehicle attribute keywords kw, and the access structure M,ρ, the VN outputs the ciphertext CT, which includes the encrypted index set IE and the encrypted dataset CE(6)
TrapdoorPP,USKj,uid,kw′⟶Tkw′. Given the query keyword set kw′, the SUuid generates the trapdoor Tkw′ according to the secret key USKj,uid and sends it to ES(7)
SearchCT,Tkw′⟶0,1. Given the trapdoor Tkw′ and the ciphertext CT, the ES or CS conducts the search algorithm, if the query is successful, outputs “1” and performs the ciphertext predecryption operation, otherwise, outputs “0”(8)
EdgeDecCT,PSKj,uid⟶CTout. Given the ciphertext CT and the predecryption key PSKj,uid, the ES outputs the partially decrypted ciphertext CTout and sends it to SUuid(9)
DecCTout,z⟶skEa. Take the partially decrypted ciphertext CTout as input, and the SUuid performs this algorithm to decrypt the ciphertext lightly using the blind value z(10)
UpdateCT,ASK′i,j,APK′i,j,v′i⟶v^′i. Given the ciphertext CT and the attribute update public key APK′i,j for key and ciphertext update


## 4.3. Secure Model

To protect the confidentiality of vehicle data, unauthorized CS, ESs, and SUs cannot access any plaintext information. The CEABKS-MA system proposed in this paper enables the Indistinguishability of Chosen Plaintext Attack (IND-CPA) [42], as well as the Indistinguishability of Chosen Keyword Attack (IND-CKA) [43]. In this subsection, we define the following interactive game between challenger B and adversary A.
(1)
IND-CPA securityInitialization. Adversary A announces a challenging access structure Λ∗ and sends it to challenger B.Setup. B first runs the Setup algorithm, outputs the public key PK, and sends it to A.Phase 1. A can adaptively send any attribute set S to B, but the restriction is that all submitted attribute sets cannot satisfy Λ∗. For each attribute set S, A executes the Keygen algorithm to output the key and sends it to B. Moreover, A can make any queries for updated key related to the canceled attribute v′i.Challenge. A selects two messages m0,m1 of equal length and sends them to B; then, B randomly selects κ∈0,1 and uses Λ∗ to encrypt mκ. Finally, B returns the challenging ciphertext Cκ to A.Phase 2. A repeats Phase 1 for other sets of attributes, but none of them satisfy Λ∗.Guess. A outputs κ′∈0,1, if κ′=κ, then wins the security game; otherwise, it fails.
(2)
IND-CKA securityDefinition 1.
If the advantage of winning the above game in any polynomial-time adversary is negligible, then the CEABKS-MA system is IND-CPA security.Setup. B outputs the public key PK and sends it to A.Phase 1. A can query OKeygen and OTrap for keys and trapdoors in polynomial time.
(i)
OKeygen. B invokes Keygen to generate the corresponding key SK and sends it to A(ii)
OTrap. A submits a keyword kw′ of interest, and B executes the Trap algorithm to generate the trapdoor Tkw′ and sends it to AChallenge. A selects two keywords kw0,kw1 with the same length, and then, B randomly selects κ∈0,1, generates index Ikwκ, and returns it to A.Phase 2. The process of Phase 2 is similar to that of Phase 1.Guess. A outputs κ′∈0,1, if κ′=κ, then wins the security game; otherwise, it fails.Definition 2.
If the advantage of winning the above game in any polynomial-time adversary is negligible, then the CEABKS-MA system is IND-CKA security.


## 5. The Proposed CEABKS-MA System

### 5.1. Construction of CEABKS-MA System

#### 5.1.1. System Initialization

Assume thatH:0,1∗⟶Zp is a one-way hash function, and e:G×G⟶GT is chosen as a bilinear mapping, where G and GT are p-order cyclic groups whose generators are g and gT, respectively. The initialization process is divided into two stages, which are described in detail as follows.
(i)
CAsetupκ. The CA executes the algorithm using the security parameter κ, obtaining the global bilinear parameter GP=e,g,GT,G, and then randomly selects a0,a1∈Zp∗ to compute Y=eg,ga0, finally obtains the public parameter PP=GP,ga0,ga1,Y and the master key MSK=a0,a1(ii)
AAsetupPP. For each attribute Atti,j∈Lji∈1,Uj, the AAj picks a random element αi∈Zp and computes hi=gαi, then randomly chooses vi∈Zp to get the attribute version key APKi,j=gvi, ASKi,j=vi. Finally, the AAj gets the attribute private key ASKj=αi,vii∈1,Uj,j∈1,N and the attribute public key APKj=hi,APKi,ji∈1,Uj,j∈1,N


#### 5.1.2. Key Generation

(i)
Keygen. The AAj computes K′=ga0a1, and for each attribute τ∈Sj,uid, picks a random value t∈Zp and computes K1=ga0ga1t, K2=gt, finally constructs a private key USKj,uid=K′,K1,K2 and sends it to SUuid(ii)
PreKeygen. The SUuid selects a random value z∈Zp and sends it to the AAj, the AAj computes K′1=K1z, K′2=K2z, and K′τ=hτtz/vτ, then constructs a predecryption key PSKj,uid=K′1,K′2,K′ττ∈Sj,uid,j∈SA and sends it to ES


#### 5.1.3. Ciphertext and Encrypted Index Generation

In the actual IoV scenario, different types of sensors carried by vehicles collect the corresponding vehicle attribute data separately. For the different attribute states of vehicles monitored by different sensors deployed on the same vehicle, the CEABKS-MA system can achieve a fine-grained keyword search for the specified vehicle attributes. Given the vehicle attribute datasetE=Ea and a keyword dictionary KW=kw, the VN uses the key skEa to encrypt the data of each attribute of the vehicle Ea∈E and defines the encrypted vehicle attribute dataset as CE=EncskEaEa; the symmetric key skEa is protected by a specified access structure M,ρ, where M is the matrix of n×l; ρ is a function that associates rows of M to attributes. The specific encryption process is divided into vehicle attribute data encryption and vehicle attribute index encryption, as follows.
(i)
EncryptCTE. The VN chooses two random vectors x=s,y1,y2,⋯,yn∈Zp and r=r1,⋯,rl∈Zp, where s is the secret sharing value, and computes λi=Mix, where i∈1,l. Then, for ∀i∈1,l, the VN computes Ci,1=ga1λihρi−ri, Ci,2=grivρi, C′=gs, and CEa=skEa·eg,ga0s and outputs the vehicle attribute ciphertext CTEa=C′,CEa,Ci,1,Ci,2i∈1,l, so as to get the vehicle ciphertext set CTE=CTEa(ii)
EncryptIE. The VN extracts keywords kw∈KW from different attribute dataset Ea∈E and constructs an attribute encrypted index IEa based on the keywords in each Ea. Then, the VN selects a random element π∈Zp, for ∀i∈1,l, computes I0=ga1π and I1,i=ga0s+πhρiπHkw and outputs the vehicle attribute encrypted index IEa=I0,I1,ii∈1,l, so as to get the vehicle encrypted index set IE=IEa(iii)
The VN uploads the vehicle ciphertext to ES periodically, and after the ciphertext expires (i.e., the VN uploads a new round of ciphertext), the ES uploads this vehicle historical ciphertext to CS


#### 5.1.4. Trapdoor Generation

If theSUuid uses his key and keyword set to generate a trapdoor Tkw′ to search an attribute status of the vehicle that contains the query keyword kw′, as follows.
(i)
Trapdoor. The SUuid randomly selects μ∈Zp∗ and computes T1=ga1μ and T2=K′μ. Then, according to the query keyword kw′, for each attribute τ∈Sj,uid, the SU computes T0=ga0μ∏τ∈Sj,uidhτμHkw′, finally gets the search trapdoor Tkw′=T0,T1,T2 and sends it to ES


#### 5.1.5. Search and Predecryption

After receiving the trapdoor and the attribute setSj,uid from SUuid, it is mainly divided into two processes: Search and EdgeDec.(i)
Search. The CS or ES first verifies whether the attribute set of SUuid embedded in the trapdoor Tkw′ can satisfy the access structure M,ρ of the ciphertext CT and stops the search operation if it does not match; otherwise, the keyword search algorithm is executed to match the trapdoor Tkw′ and the index set IE, as shown as follows:(1)eI0,T0eC′,T2=e∏ρi∈Sj,uidI1,i,T1,Correctness verification is as follows:(2)ξ1=eI0,∏τ∈Sj,uidT0eC′,T2=ega1π,ga0μ∏τ∈Sj,uidhτμHkw′egs,ga0a1μ=eg,ga0a1μπeg,∏τ∈Sj,uidhτa1μπHkw′eg,ga0a1μs,(3)ξ2=e∏ρi∈Sj,uidI1,i,T1=ega0s+π∏ρi∈Sj,uidhρiπHkw,ga1μ=eg,ga0a1μseg,ga0a1μπeg,∏ρi=τ∈Sj,uidhρia1μπHkw.Obviously, whenkw′=kw, there is ξ1=ξ2; that is, the keyword search algorithm is successful and outputs “1,” otherwise, outputs “0.”
(ii)
EdgeDec. After the keyword search is successful, the ES will perform the ciphertext predecryption operation for SUuid. Define I⊂1,2,⋯,l, expressed as I=i,ρi∈Sj,uid; there must be a set of constants wi∈Zpi∈I makes ∑i∈Iwiλi=s, and calculates the following:(4)ζ=eK′1,C′∏i∈IeCi,1,K2′·eCi,2,Kρi′wi=ega0zga1tz,gs∑i∈Iga1λi·hρi−ri,gtzegrivρi,hρitz/viwi=eg,ga0zseg,ga1tzs∑i∈Ieg,ga1tzλiwi=eg,ga0zs.The ES constructs partially decrypted ciphertextCTout=Ckw′,ζ and returns it to SUuid.


#### 5.1.6. User Decryption

(i)
After receiving the partially decrypted ciphertext, the SU uses the blind valuez to compute Ckw′/ζ to obtain the symmetric key skEa and then uses skEa to obtain the plaintext vehicle data Ea


### 5.2. Attribute Revocation and Update

The access right change of SU requires the update of their attributes to avoid malicious users from using expired keys to access unauthorized information. Each AA in the CEABKS-MA system manages a disjoint set of attribute collections and performs attribute update operations only for users in the domain, effectively spreading the computational and storage burden of the CA and obtaining higher efficiency.When there are some attributes to be updated, theAAj first updates the attribute version key ASKi,j,APKi,j and then generates the transformation key to update SU’s key and the vehicle ciphertext stored in ES or CS. Moreover, the CEABKS-MA system only updates a small portion of the attribute-related key and ciphertext; the attribute update algorithm is as follows.
(i)
If the attributeatt′i of SU managed by AAj is revoked, the AAj inputs ASKi,j,APKi,j, and the revoked attribute att′i randomly chooses a new value v^′i∈Zpv^′i≠v′i and computes the updated attribute version key as ASK′i,j=v^′i/v′i, APK′i,j=gv′iASK′i,j=gv∧′i. Finally, the AAj sends ASK′i,j to ES or CS(ii)
Key Update. The AAj informs SU that has the attribute att′i and has not been revoked to upload the relevant part of the key component with the revoked attribute to AAj for updating. After receiving the data uploaded by SU, the AAj computes K⌢′i=K′iASK′i,j−1=hizt/v′iv′i/v⌢′i=hizt/v⌢′i and returns it to SU whose attributes have not been revoked(iii)
Ciphertext Update. When the attribute att′i of SU is revoked, the AAj needs to update the ciphertext synchronously. Due to the limited computing resources of VN, updating the attribute ciphertext C⌢i,2=Ci,2ASK′i,j=griv′iv⌢′i/v′i=griv⌢′i associated with attribute att′i on ES or CS


### 5.3. Online/Offline Encryption

#### 5.3.1. Ciphertext Online/Offline Generation

To avoid the heavy burden of encrypting computation as well as to improve the efficiency of encryption, the CEABKS-MA system is extended to support ciphertext online/offline generation, as follows.(i)
Offline Encryption. Let the maximum number of lines in the access structure M,ρ embedded in the vehicle ciphertext be Θ. The VN chooses random elements s,π,λ′i,ri∈Zp and computes C′i,1=ga1λ′i, C′′i,1=hρi−ri, Ci,2=grivρi, C′Ea=eg,ga0s, C′=gs, I0=ga1π, I′1=ga0s+π, and I′′1,i=hρiπ. Finally, the VN generates the offline vehicle attribute ciphertext CT′Ea=C′,C′Ea,C′i,1,C′′i,1,Ci,2i∈1,Θ and the offline vehicle attribute encrypted index I′Ea=I0,I′1,I′′1,ii∈1,Φ(ii)
Online Encryption. The VN selects a random vector x=s,y1,y2,⋯,yn∈Zp, s as the secret shared value of the access structure M,ρ and computes λi=Mix, i∈1,l. Then, the VN computes C′i=λi−λ′i and CEa=skEa·C′Ea and gets the complete vehicle attribute ciphertext CTEa=CEa,C′,C′i,C′i,1,C′′i,1,Ci,2i∈1,l. Finally, for ∀i∈1,l, the VN computes I1,i=I′1·I′′1,iHkw and gets the complete vehicle attribute encrypted index IEa=I0,I1,ii∈1,l


#### 5.3.2. Trapdoor Online/Offline Generation

Similarly, the trapdoor generation part is divided into the online/offline phase to improve the computation efficiency of SU.(i)
Offline Generation. The SU randomly selects μ∈Zp∗ and computes T0′=ga0μ, T1=ga1μ, and T2=K′μ, then gets the offline part of the trapdoor Toff=T′0,T1,T2. The SU saves it to avoid duplicate operations during the search(ii)
Online Generation. Based on the vehicle attribute keyword kw′, for each attribute τ∈Sj,uid, the SU computes T0=T′0∏τ∈Sj,uidhτμHkw′ and gets the online trapdoor Ton=T0, then gets the final trapdoor Tkw′=Toff,Ton(iii)
Predecryption Phase. In the predecryption phase, the CS or ES first computes C′′i=ga1C′i=ga1λi−λ′i and Ci,1=C′i,1C′′iC′′i,1=ga1λihρi−ri, which can be predecrypted by using the predecryption formula (4)


### 5.4. Cloud-Edge-End Collaborative Search Method

This paper designs a cloud-edge-end collaborative search method to provide a more efficient and flexible search while reducing user burden. The specific search process is shown in Figure3.Figure 3
Cloud-edge-end collaborative search method.The object task in the proposed search method has changed compared to the cloud-based search method. In the ciphertext upload phase, the vehicle carries sensors to monitor the vehicle state in real-time, and the VN encrypts the vehicle data and uploads the ciphertext to the nearby ES periodically for reducing communication cost and latency caused by long-distance communication toward CS. And after the VN forwards a new round of the ciphertext, the ES uploads the historical ciphertext to CS to reduce the computation and storage burden. In the search phase, the SU only needs to send the trapdoor to ES for instant and historical search; at the same time, the corresponding ciphertext after a successful query is finally returned to SU after predecryption by ES, and the SU only needs to perform marginal decryption operation to decrypt it.


## 5.1. Construction of CEABKS-MA System

### 5.1.1. System Initialization

Assume thatH:0,1∗⟶Zp is a one-way hash function, and e:G×G⟶GT is chosen as a bilinear mapping, where G and GT are p-order cyclic groups whose generators are g and gT, respectively. The initialization process is divided into two stages, which are described in detail as follows.
(i)
CAsetupκ. The CA executes the algorithm using the security parameter κ, obtaining the global bilinear parameter GP=e,g,GT,G, and then randomly selects a0,a1∈Zp∗ to compute Y=eg,ga0, finally obtains the public parameter PP=GP,ga0,ga1,Y and the master key MSK=a0,a1(ii)
AAsetupPP. For each attribute Atti,j∈Lji∈1,Uj, the AAj picks a random element αi∈Zp and computes hi=gαi, then randomly chooses vi∈Zp to get the attribute version key APKi,j=gvi, ASKi,j=vi. Finally, the AAj gets the attribute private key ASKj=αi,vii∈1,Uj,j∈1,N and the attribute public key APKj=hi,APKi,ji∈1,Uj,j∈1,N


### 5.1.2. Key Generation

(i)
Keygen. The AAj computes K′=ga0a1, and for each attribute τ∈Sj,uid, picks a random value t∈Zp and computes K1=ga0ga1t, K2=gt, finally constructs a private key USKj,uid=K′,K1,K2 and sends it to SUuid(ii)
PreKeygen. The SUuid selects a random value z∈Zp and sends it to the AAj, the AAj computes K′1=K1z, K′2=K2z, and K′τ=hτtz/vτ, then constructs a predecryption key PSKj,uid=K′1,K′2,K′ττ∈Sj,uid,j∈SA and sends it to ES


### 5.1.3. Ciphertext and Encrypted Index Generation

In the actual IoV scenario, different types of sensors carried by vehicles collect the corresponding vehicle attribute data separately. For the different attribute states of vehicles monitored by different sensors deployed on the same vehicle, the CEABKS-MA system can achieve a fine-grained keyword search for the specified vehicle attributes. Given the vehicle attribute datasetE=Ea and a keyword dictionary KW=kw, the VN uses the key skEa to encrypt the data of each attribute of the vehicle Ea∈E and defines the encrypted vehicle attribute dataset as CE=EncskEaEa; the symmetric key skEa is protected by a specified access structure M,ρ, where M is the matrix of n×l; ρ is a function that associates rows of M to attributes. The specific encryption process is divided into vehicle attribute data encryption and vehicle attribute index encryption, as follows.
(i)
EncryptCTE. The VN chooses two random vectors x=s,y1,y2,⋯,yn∈Zp and r=r1,⋯,rl∈Zp, where s is the secret sharing value, and computes λi=Mix, where i∈1,l. Then, for ∀i∈1,l, the VN computes Ci,1=ga1λihρi−ri, Ci,2=grivρi, C′=gs, and CEa=skEa·eg,ga0s and outputs the vehicle attribute ciphertext CTEa=C′,CEa,Ci,1,Ci,2i∈1,l, so as to get the vehicle ciphertext set CTE=CTEa(ii)
EncryptIE. The VN extracts keywords kw∈KW from different attribute dataset Ea∈E and constructs an attribute encrypted index IEa based on the keywords in each Ea. Then, the VN selects a random element π∈Zp, for ∀i∈1,l, computes I0=ga1π and I1,i=ga0s+πhρiπHkw and outputs the vehicle attribute encrypted index IEa=I0,I1,ii∈1,l, so as to get the vehicle encrypted index set IE=IEa(iii)
The VN uploads the vehicle ciphertext to ES periodically, and after the ciphertext expires (i.e., the VN uploads a new round of ciphertext), the ES uploads this vehicle historical ciphertext to CS


### 5.1.4. Trapdoor Generation

If theSUuid uses his key and keyword set to generate a trapdoor Tkw′ to search an attribute status of the vehicle that contains the query keyword kw′, as follows.
(i)
Trapdoor. The SUuid randomly selects μ∈Zp∗ and computes T1=ga1μ and T2=K′μ. Then, according to the query keyword kw′, for each attribute τ∈Sj,uid, the SU computes T0=ga0μ∏τ∈Sj,uidhτμHkw′, finally gets the search trapdoor Tkw′=T0,T1,T2 and sends it to ES


### 5.1.5. Search and Predecryption

After receiving the trapdoor and the attribute setSj,uid from SUuid, it is mainly divided into two processes: Search and EdgeDec.(i)
Search. The CS or ES first verifies whether the attribute set of SUuid embedded in the trapdoor Tkw′ can satisfy the access structure M,ρ of the ciphertext CT and stops the search operation if it does not match; otherwise, the keyword search algorithm is executed to match the trapdoor Tkw′ and the index set IE, as shown as follows:(1)eI0,T0eC′,T2=e∏ρi∈Sj,uidI1,i,T1,Correctness verification is as follows:(2)ξ1=eI0,∏τ∈Sj,uidT0eC′,T2=ega1π,ga0μ∏τ∈Sj,uidhτμHkw′egs,ga0a1μ=eg,ga0a1μπeg,∏τ∈Sj,uidhτa1μπHkw′eg,ga0a1μs,(3)ξ2=e∏ρi∈Sj,uidI1,i,T1=ega0s+π∏ρi∈Sj,uidhρiπHkw,ga1μ=eg,ga0a1μseg,ga0a1μπeg,∏ρi=τ∈Sj,uidhρia1μπHkw.Obviously, whenkw′=kw, there is ξ1=ξ2; that is, the keyword search algorithm is successful and outputs “1,” otherwise, outputs “0.”
(ii)
EdgeDec. After the keyword search is successful, the ES will perform the ciphertext predecryption operation for SUuid. Define I⊂1,2,⋯,l, expressed as I=i,ρi∈Sj,uid; there must be a set of constants wi∈Zpi∈I makes ∑i∈Iwiλi=s, and calculates the following:(4)ζ=eK′1,C′∏i∈IeCi,1,K2′·eCi,2,Kρi′wi=ega0zga1tz,gs∑i∈Iga1λi·hρi−ri,gtzegrivρi,hρitz/viwi=eg,ga0zseg,ga1tzs∑i∈Ieg,ga1tzλiwi=eg,ga0zs.The ES constructs partially decrypted ciphertextCTout=Ckw′,ζ and returns it to SUuid.


### 5.1.6. User Decryption

(i)
After receiving the partially decrypted ciphertext, the SU uses the blind valuez to compute Ckw′/ζ to obtain the symmetric key skEa and then uses skEa to obtain the plaintext vehicle data Ea


## 5.1.1. System Initialization

Assume thatH:0,1∗⟶Zp is a one-way hash function, and e:G×G⟶GT is chosen as a bilinear mapping, where G and GT are p-order cyclic groups whose generators are g and gT, respectively. The initialization process is divided into two stages, which are described in detail as follows.
(i)
CAsetupκ. The CA executes the algorithm using the security parameter κ, obtaining the global bilinear parameter GP=e,g,GT,G, and then randomly selects a0,a1∈Zp∗ to compute Y=eg,ga0, finally obtains the public parameter PP=GP,ga0,ga1,Y and the master key MSK=a0,a1(ii)
AAsetupPP. For each attribute Atti,j∈Lji∈1,Uj, the AAj picks a random element αi∈Zp and computes hi=gαi, then randomly chooses vi∈Zp to get the attribute version key APKi,j=gvi, ASKi,j=vi. Finally, the AAj gets the attribute private key ASKj=αi,vii∈1,Uj,j∈1,N and the attribute public key APKj=hi,APKi,ji∈1,Uj,j∈1,N


## 5.1.2. Key Generation

(i)
Keygen. The AAj computes K′=ga0a1, and for each attribute τ∈Sj,uid, picks a random value t∈Zp and computes K1=ga0ga1t, K2=gt, finally constructs a private key USKj,uid=K′,K1,K2 and sends it to SUuid(ii)
PreKeygen. The SUuid selects a random value z∈Zp and sends it to the AAj, the AAj computes K′1=K1z, K′2=K2z, and K′τ=hτtz/vτ, then constructs a predecryption key PSKj,uid=K′1,K′2,K′ττ∈Sj,uid,j∈SA and sends it to ES


## 5.1.3. Ciphertext and Encrypted Index Generation

In the actual IoV scenario, different types of sensors carried by vehicles collect the corresponding vehicle attribute data separately. For the different attribute states of vehicles monitored by different sensors deployed on the same vehicle, the CEABKS-MA system can achieve a fine-grained keyword search for the specified vehicle attributes. Given the vehicle attribute datasetE=Ea and a keyword dictionary KW=kw, the VN uses the key skEa to encrypt the data of each attribute of the vehicle Ea∈E and defines the encrypted vehicle attribute dataset as CE=EncskEaEa; the symmetric key skEa is protected by a specified access structure M,ρ, where M is the matrix of n×l; ρ is a function that associates rows of M to attributes. The specific encryption process is divided into vehicle attribute data encryption and vehicle attribute index encryption, as follows.
(i)
EncryptCTE. The VN chooses two random vectors x=s,y1,y2,⋯,yn∈Zp and r=r1,⋯,rl∈Zp, where s is the secret sharing value, and computes λi=Mix, where i∈1,l. Then, for ∀i∈1,l, the VN computes Ci,1=ga1λihρi−ri, Ci,2=grivρi, C′=gs, and CEa=skEa·eg,ga0s and outputs the vehicle attribute ciphertext CTEa=C′,CEa,Ci,1,Ci,2i∈1,l, so as to get the vehicle ciphertext set CTE=CTEa(ii)
EncryptIE. The VN extracts keywords kw∈KW from different attribute dataset Ea∈E and constructs an attribute encrypted index IEa based on the keywords in each Ea. Then, the VN selects a random element π∈Zp, for ∀i∈1,l, computes I0=ga1π and I1,i=ga0s+πhρiπHkw and outputs the vehicle attribute encrypted index IEa=I0,I1,ii∈1,l, so as to get the vehicle encrypted index set IE=IEa(iii)
The VN uploads the vehicle ciphertext to ES periodically, and after the ciphertext expires (i.e., the VN uploads a new round of ciphertext), the ES uploads this vehicle historical ciphertext to CS


## 5.1.4. Trapdoor Generation

If theSUuid uses his key and keyword set to generate a trapdoor Tkw′ to search an attribute status of the vehicle that contains the query keyword kw′, as follows.
(i)
Trapdoor. The SUuid randomly selects μ∈Zp∗ and computes T1=ga1μ and T2=K′μ. Then, according to the query keyword kw′, for each attribute τ∈Sj,uid, the SU computes T0=ga0μ∏τ∈Sj,uidhτμHkw′, finally gets the search trapdoor Tkw′=T0,T1,T2 and sends it to ES


## 5.1.5. Search and Predecryption

After receiving the trapdoor and the attribute setSj,uid from SUuid, it is mainly divided into two processes: Search and EdgeDec.(i)
Search. The CS or ES first verifies whether the attribute set of SUuid embedded in the trapdoor Tkw′ can satisfy the access structure M,ρ of the ciphertext CT and stops the search operation if it does not match; otherwise, the keyword search algorithm is executed to match the trapdoor Tkw′ and the index set IE, as shown as follows:(1)eI0,T0eC′,T2=e∏ρi∈Sj,uidI1,i,T1,Correctness verification is as follows:(2)ξ1=eI0,∏τ∈Sj,uidT0eC′,T2=ega1π,ga0μ∏τ∈Sj,uidhτμHkw′egs,ga0a1μ=eg,ga0a1μπeg,∏τ∈Sj,uidhτa1μπHkw′eg,ga0a1μs,(3)ξ2=e∏ρi∈Sj,uidI1,i,T1=ega0s+π∏ρi∈Sj,uidhρiπHkw,ga1μ=eg,ga0a1μseg,ga0a1μπeg,∏ρi=τ∈Sj,uidhρia1μπHkw.Obviously, whenkw′=kw, there is ξ1=ξ2; that is, the keyword search algorithm is successful and outputs “1,” otherwise, outputs “0.”
(ii)
EdgeDec. After the keyword search is successful, the ES will perform the ciphertext predecryption operation for SUuid. Define I⊂1,2,⋯,l, expressed as I=i,ρi∈Sj,uid; there must be a set of constants wi∈Zpi∈I makes ∑i∈Iwiλi=s, and calculates the following:(4)ζ=eK′1,C′∏i∈IeCi,1,K2′·eCi,2,Kρi′wi=ega0zga1tz,gs∑i∈Iga1λi·hρi−ri,gtzegrivρi,hρitz/viwi=eg,ga0zseg,ga1tzs∑i∈Ieg,ga1tzλiwi=eg,ga0zs.The ES constructs partially decrypted ciphertextCTout=Ckw′,ζ and returns it to SUuid.


## 5.1.6. User Decryption

(i)
After receiving the partially decrypted ciphertext, the SU uses the blind valuez to compute Ckw′/ζ to obtain the symmetric key skEa and then uses skEa to obtain the plaintext vehicle data Ea


## 5.2. Attribute Revocation and Update

The access right change of SU requires the update of their attributes to avoid malicious users from using expired keys to access unauthorized information. Each AA in the CEABKS-MA system manages a disjoint set of attribute collections and performs attribute update operations only for users in the domain, effectively spreading the computational and storage burden of the CA and obtaining higher efficiency.When there are some attributes to be updated, theAAj first updates the attribute version key ASKi,j,APKi,j and then generates the transformation key to update SU’s key and the vehicle ciphertext stored in ES or CS. Moreover, the CEABKS-MA system only updates a small portion of the attribute-related key and ciphertext; the attribute update algorithm is as follows.
(i)
If the attributeatt′i of SU managed by AAj is revoked, the AAj inputs ASKi,j,APKi,j, and the revoked attribute att′i randomly chooses a new value v^′i∈Zpv^′i≠v′i and computes the updated attribute version key as ASK′i,j=v^′i/v′i, APK′i,j=gv′iASK′i,j=gv∧′i. Finally, the AAj sends ASK′i,j to ES or CS(ii)
Key Update. The AAj informs SU that has the attribute att′i and has not been revoked to upload the relevant part of the key component with the revoked attribute to AAj for updating. After receiving the data uploaded by SU, the AAj computes K⌢′i=K′iASK′i,j−1=hizt/v′iv′i/v⌢′i=hizt/v⌢′i and returns it to SU whose attributes have not been revoked(iii)
Ciphertext Update. When the attribute att′i of SU is revoked, the AAj needs to update the ciphertext synchronously. Due to the limited computing resources of VN, updating the attribute ciphertext C⌢i,2=Ci,2ASK′i,j=griv′iv⌢′i/v′i=griv⌢′i associated with attribute att′i on ES or CS


## 5.3. Online/Offline Encryption

### 5.3.1. Ciphertext Online/Offline Generation

To avoid the heavy burden of encrypting computation as well as to improve the efficiency of encryption, the CEABKS-MA system is extended to support ciphertext online/offline generation, as follows.(i)
Offline Encryption. Let the maximum number of lines in the access structure M,ρ embedded in the vehicle ciphertext be Θ. The VN chooses random elements s,π,λ′i,ri∈Zp and computes C′i,1=ga1λ′i, C′′i,1=hρi−ri, Ci,2=grivρi, C′Ea=eg,ga0s, C′=gs, I0=ga1π, I′1=ga0s+π, and I′′1,i=hρiπ. Finally, the VN generates the offline vehicle attribute ciphertext CT′Ea=C′,C′Ea,C′i,1,C′′i,1,Ci,2i∈1,Θ and the offline vehicle attribute encrypted index I′Ea=I0,I′1,I′′1,ii∈1,Φ(ii)
Online Encryption. The VN selects a random vector x=s,y1,y2,⋯,yn∈Zp, s as the secret shared value of the access structure M,ρ and computes λi=Mix, i∈1,l. Then, the VN computes C′i=λi−λ′i and CEa=skEa·C′Ea and gets the complete vehicle attribute ciphertext CTEa=CEa,C′,C′i,C′i,1,C′′i,1,Ci,2i∈1,l. Finally, for ∀i∈1,l, the VN computes I1,i=I′1·I′′1,iHkw and gets the complete vehicle attribute encrypted index IEa=I0,I1,ii∈1,l


### 5.3.2. Trapdoor Online/Offline Generation

Similarly, the trapdoor generation part is divided into the online/offline phase to improve the computation efficiency of SU.(i)
Offline Generation. The SU randomly selects μ∈Zp∗ and computes T0′=ga0μ, T1=ga1μ, and T2=K′μ, then gets the offline part of the trapdoor Toff=T′0,T1,T2. The SU saves it to avoid duplicate operations during the search(ii)
Online Generation. Based on the vehicle attribute keyword kw′, for each attribute τ∈Sj,uid, the SU computes T0=T′0∏τ∈Sj,uidhτμHkw′ and gets the online trapdoor Ton=T0, then gets the final trapdoor Tkw′=Toff,Ton(iii)
Predecryption Phase. In the predecryption phase, the CS or ES first computes C′′i=ga1C′i=ga1λi−λ′i and Ci,1=C′i,1C′′iC′′i,1=ga1λihρi−ri, which can be predecrypted by using the predecryption formula (4)


## 5.3.1. Ciphertext Online/Offline Generation

To avoid the heavy burden of encrypting computation as well as to improve the efficiency of encryption, the CEABKS-MA system is extended to support ciphertext online/offline generation, as follows.(i)
Offline Encryption. Let the maximum number of lines in the access structure M,ρ embedded in the vehicle ciphertext be Θ. The VN chooses random elements s,π,λ′i,ri∈Zp and computes C′i,1=ga1λ′i, C′′i,1=hρi−ri, Ci,2=grivρi, C′Ea=eg,ga0s, C′=gs, I0=ga1π, I′1=ga0s+π, and I′′1,i=hρiπ. Finally, the VN generates the offline vehicle attribute ciphertext CT′Ea=C′,C′Ea,C′i,1,C′′i,1,Ci,2i∈1,Θ and the offline vehicle attribute encrypted index I′Ea=I0,I′1,I′′1,ii∈1,Φ(ii)
Online Encryption. The VN selects a random vector x=s,y1,y2,⋯,yn∈Zp, s as the secret shared value of the access structure M,ρ and computes λi=Mix, i∈1,l. Then, the VN computes C′i=λi−λ′i and CEa=skEa·C′Ea and gets the complete vehicle attribute ciphertext CTEa=CEa,C′,C′i,C′i,1,C′′i,1,Ci,2i∈1,l. Finally, for ∀i∈1,l, the VN computes I1,i=I′1·I′′1,iHkw and gets the complete vehicle attribute encrypted index IEa=I0,I1,ii∈1,l


## 5.3.2. Trapdoor Online/Offline Generation

Similarly, the trapdoor generation part is divided into the online/offline phase to improve the computation efficiency of SU.(i)
Offline Generation. The SU randomly selects μ∈Zp∗ and computes T0′=ga0μ, T1=ga1μ, and T2=K′μ, then gets the offline part of the trapdoor Toff=T′0,T1,T2. The SU saves it to avoid duplicate operations during the search(ii)
Online Generation. Based on the vehicle attribute keyword kw′, for each attribute τ∈Sj,uid, the SU computes T0=T′0∏τ∈Sj,uidhτμHkw′ and gets the online trapdoor Ton=T0, then gets the final trapdoor Tkw′=Toff,Ton(iii)
Predecryption Phase. In the predecryption phase, the CS or ES first computes C′′i=ga1C′i=ga1λi−λ′i and Ci,1=C′i,1C′′iC′′i,1=ga1λihρi−ri, which can be predecrypted by using the predecryption formula (4)


## 5.4. Cloud-Edge-End Collaborative Search Method

This paper designs a cloud-edge-end collaborative search method to provide a more efficient and flexible search while reducing user burden. The specific search process is shown in Figure3.Figure 3
Cloud-edge-end collaborative search method.The object task in the proposed search method has changed compared to the cloud-based search method. In the ciphertext upload phase, the vehicle carries sensors to monitor the vehicle state in real-time, and the VN encrypts the vehicle data and uploads the ciphertext to the nearby ES periodically for reducing communication cost and latency caused by long-distance communication toward CS. And after the VN forwards a new round of the ciphertext, the ES uploads the historical ciphertext to CS to reduce the computation and storage burden. In the search phase, the SU only needs to send the trapdoor to ES for instant and historical search; at the same time, the corresponding ciphertext after a successful query is finally returned to SU after predecryption by ES, and the SU only needs to perform marginal decryption operation to decrypt it.


## 6. Safety and Performance Simulation Validation

### 6.1. Security Analysis

The CEABKS-MA system proposed in this paper can achieve IND-CPA security and IND-CKA security presented in Section 4.3 and is analyzed in detail as follows.Theorem 3.
Under the assumption that the Decisional q-parallel Bilinear Diffie-Hellman Exponent (BDHE) assumption [44] holds, that the advantage of all polynomial-time opponents who can win the IND-CPA game can be ignored.Proof.
Assume that adversary A can break the CEABKS-MA system by a nonnegligible advantageδ. A chooses a challenging matrix M∗, and then, B handles the q-DBDHE problem as follows.
Setup. Given a q-DBDHE challenge instance ϕ,R, B first chooses a0∈Zp and sets a0=a′+a1q+1; then, B defines the public key component Y=eg,ga0=ega1,ga1qeg,ga′. B chooses a random value vi∈Zp for each i∈Uj and sets APKi,j=gvi. To simulate the group elements hi, B picks a random element βi∈Zp for each i∈Uj. Let ρ∗ι=i, then B sets hi as follows:
(5)hi=gβi∏ι∈Φga1Mι,1∗/bιga12Mι,2∗/bι⋯ga1n∗Mι,n∗∗/bι,where Φ denotes the set of indices ι. If Φ=∅, B sets hi=gβi, and the values of hi are randomly distributed due to gβi.
Phase 1. In this phase, B needs to answer A’s key queries. Assume that A provides an attribute set S that do not satisfy M∗, and B chooses a vector x∗=x1∗,⋯,xn∗∗ such that x1∗=−1 for all ιρ∗ι∈S have x∗·Mι∗=0. Then, B randomly chooses an element ϑ∈Zp and defines t as follows:
(6)t=ϑ+x1∗a1q+x2∗a1q−1+⋯+xn∗∗a1q−n∗+1.
Then, B computesK′2:
(7)K′2=gϑz∏ι=1n∗gxι∗za1q+1−ι=gtz.
Based on the definition oft above, it can be inferred that ga1t contains ga1q+1 which can be cancelled by ga0. Thus, B computes K′1 as follows:
(8)K′1=ga′zga1ϑz∏ι∈2,n∗gvιa1q+2−ι=ga0zga1tz.
For each attributeτ∈S, B defines K′τ if ρ∗ι≠τ sets K′τ=K′2gβτ/vτ. Under this condition, B cannot simulate K′τ for the attribute τ∈S in M∗, since K′τ contains the term ga1q+1/bι. If there exists a set Φ=ι such that ρ∗ι=τ and B computes K′τ as follows:
(9)K′τ=K′2βτ/vτ∏ι∈Φ∏k∈1,n∗ga1kϑ/bιMi,k∗/vτ·∏ι∈Φ∏k∈1,n∗∏k′∈1,n∗ga1q+1+k−k′/bιMi,j∗/vτ.
A sends a revoked attributeatt′i to perform an updated attribute version key query. B randomly selects a new value v^′i∈Zpv^′i≠v′i and computes the updated attribute version key as ASK′i,j=v^′i/v′i and returns it as A.
Challenge. A submits two challenging messages m0,m1 to B with corresponding encryption keys sk0,sk1, and then, B randomly selects κ∈0,1 and computes CEκ=skEκ·eg,ga0s,C′=gs. However, since the ciphertext component Ci,1 contains some terms that should be removed, it is difficult to simulate Ci,1, where i∈1,l∗. To solve this problem, B randomly chooses y2∗,⋯,yn∗∗∈Zp and shares the secret s as follows:
(10)x=s,sa1+y2∗,sa12+y3∗,⋯,sa1n∗−1+yn∗∗.
Furthermore, B chooses random elementsr2∗,⋯,rn∗∗∈Zp. Let Qi be the set of all ρi=ρk′ satisfying i∈1,l∗. Finally, B outputs Ci,1,Ci,2 as follows:
(11)Ci,1=hρ∗iri∗∏k∈2,n∗ga1Mi,k∗yk∗∗gbis−βρ∗i·∏k′∈Ωi∏k∈1,n∗ga1ksbi/bk′Mk′,k∗,Ci,2=g−ri∗−sbivρ∗i.
Phase 2. Phase 2 has the same process as Phase 1.
Guess. A returns a guess bit κ′∈0,1, if κ′=κ; B returns “0” indicating that R=eg,ga1q+1s; otherwise, B returns “1” indicating that R is a randomly chosen element of the group GT. When R is a tuple, B returns a perfect simulation, which then yields PrBϕ,R=eg,ga1q+1s=0=1/2+δ. When R is a random element in the group GT and the encryption key skκ is completely hidden from A, then one obtains PrBϕ,R=0=1/2. Thus, B simulates the above security game with a nonnegligible advantage. This completes the proof of Theorem 3.Theorem 4.
Based on a given one-way hash functionH, the CEABKS-MA system prevents chosen keyword attacks.
Selecting a random valued∈Zp, the advantage of adversary A in distinguishing between gd and ga0s+πhρiπHkw0 is the same as the advantage of distinguishing between gd and ga0s+πhρiπHkw1 with the same advantage. Assume that A can distinguish between gd and ga0s+π, and the defined secure interactive game is as follows.Proof.
Setup. B randomly selects a0,a1∈Zp and returns the public key PK=g,ga0,ga1 to A.
Phase 1. A can query OKeygen and OTrap for keys and trapdoors in polynomial time.
(i)
OKeygen. B computes K′=ga0a1 and sends K′ to A(ii)
OTrap. B randomly selects μ∈Zp and computes T0=ga0μhτμHkw′, T1=ga1μ, and T2=ga0a1μ according to query keyword kw′, which gives the trapdoor Tkw′=T0,T1,T2
Challenge. A inputs two keywords of the same length kw0,kw1. B selects s,π∈Zp and picks κ∈0,1. If κ=0, B sets I0=ga1π, I1=gd, and C′=gs, otherwise, sets I0=ga1π, I1=ga0s+π, and C′=gs.
Phase 2. A performs a query similar to Phase 1 but restricts kw≠kw0,kw1.
Assume thatυ∈Zp and if A can construct eg,gυa0s+π using the term gυ returned by the query, then A can distinguish between gd and ga0s+π. Thus, it needs to be shown that A can only use the term gυ to construct eg,gυa0s+π by a negligible advantage.
LetG1=ϕ1ηη∈Zp,GT=ϕ2ηη∈Zp, where ϕ1 and ϕ2 are two introjection functions mapped from Zp to a set with p3 elements. In the mapping between ϕ1 and ϕ2, the advantage of adversary A in distinguishing elements is negligible, so it is only necessary to consider the probability of adversary A in constructing eg,gυa0s+π using gυ.
If A want to geteg,gυa0s+π from gυ, since only a1π contains π, υ must contain a1 to get eg,gυa0s+π. A will try to construct eg,gυ′a0s+π based on υ′=υa1. However, A also needs to get υ′a0a1s containing the term a0a1 and the secret value s. Since only B has the primary key a1, A cannot obtain eg,gυ′a0s+π.
Thus, it can be concluded that adversary A cannot distinguishga0s+πhρiπHkw0 and ga0s+πhρiπHkw1. That is, the CEABKS-MA system is secure in the chosen keyword attack game, which completes the proof of Theorem 4.In addition, the CEABKS-MA system can resist collusion attacks by users and achieve the security of user key. (1) The CEABKS-MA system prevents user collusion attacks by assigning a global identifieruid to each DU. In Keygen, the key component is associated with a random value t, so it is difficult for a malicious user to isolate the t value from a given key to perform collusion queries in the absence of a random value t. (2) The search user uses a random value μ to blind the key when performing queries to ensure the security and confidentiality of the user’s key.


### 6.2. Performance Analysis

The CEABKS-MA system implements fine-grained keyword search, multiauthority structure, and attribute update and has high efficiency in both key and trapdoor generation as well as search and decryption phases. Table1 shows a functional comparison between the CEABKS-MA system and other existing systems [29–31].Table 1
Functional comparison of different system.
SystemHP-CPABKS [29]VKSE [30]LSABE-MA [31]CEABKS-MAKeyword search√√√√Attribute revocation×××√Multi-authority××√√High efficiency×××√Access structureLSSSTreeLSSSLSSSThe theoretical computation and storage costs of the CEABKS-MA system and the existing scheme [29] are analyzed, as shown in Tables 2 and 3, respectively. For the computation costs in Table 2, we mainly consider several more time-consuming operations, namely, bilinear pairing operation P and exponential operation E or ET in group G or GT. The number of system attributes is denoted as Uj and U for the CEABKS-MA system and HP-CPABKS system, respectively, and the number of user attributes is denoted as S. Since the CEABKS-MA system uses a distributed key distribution structure, S≪Uj≪U in practice, the CEABKS-MA system consumes less time than the HP-CPABKS system in Keygen and Trapdoor. The computation cost of the CEABKS-MA system in Encrypt will be higher than that of the HP-CPABKS system when setting Uj=U, but the online/offline encryption method is extended to the proposed system, and the ciphertext generation is a one-time operation. In Search, the computation cost of the CEABKS-MA system is constant, and the search efficiency is much higher than that of the HP-CPABKS system.Table 2
Theoretical computation cost comparison.
SystemCEABKS-MAHP-CPABKS [29]KeygenS+5E2U+1E+ETTrapdoorS+2E2U+1EEncrypt3Uj+3E+ET2U+1E+ETSearch3P2U+1P+ETTable 3
Theoretical storage cost comparison.
SystemCEABKS-MAHP-CPABKS [29]Setup2Uj+1Zp+2Uj+2G+GTU+2Zp+U+1G+GTKeygenS+5G2U+1G+U+2ZpTrapdoor3G2U+1G+2ZpEncrypt3Uj+3G+GT2U+1G+U+1ZpFor the storage costs in Table3, element lengths in G,GT,Zp are defined as G,GT,Zp, respectively. When Uj=U, the storage cost of the CEABKS-MA system in Setup is higher due to the added attribute update function. Similar to the computation cost analysis, the storage cost of the CEABKS-MA system is much lower than that of the HP-CPABKS system in Keygen and Trapdoor, and the storage cost in Trapdoor is constant, which is more suitable for resource-constrained devices.To verify the above theoretical analysis, we present an experimental analysis of the computation efficiency and storage consumption of the CEABKS-MA system and the HP-CPABKS system. The experimental simulation is Windows 10, Intel(R) Core(TM) i3-8100 CPU@3.60 GHz. The programming language is C and parsing-based cryptography (PBC) libraries. The parameters related to computation and storage costs are set asG=GT=1024 bits, Zp=160 bits, S∈1,50, and Uj=U∈1,100.Figure4 shows the actual computation time comparison of different systems in each phase; in Figure 4(a), the computation cost of both systems in Setup increases with the expanding number of system attributes, and the CEABKS-MA system costs slightly more time than the HP-CPABKS system, which is consistent with the theoretical analysis, but note that Uj<U in practice. The number of system attributes in Figures 4(b) and 4(c) is fixed at U=50; it can be seen that the time consumption of the CEABKS-MA system in Keygen and Trapdoor increases linearly with the number of user attributes but is still much lower than that of the HP-CPABKS system, and S≪U, so the CEABKS-MA system has higher efficiency and application value for search users with limited computational resources. Figure 4(d) shows the comparative analysis of search time, which is constant and much lower than that of the HP-CPABKS system.Figure 4
Computation cost comparison.
(a)
Setup(b)
Keygen(c)
Trapdoor(d)
SearchFigure5 shows the actual storage cost comparison of different systems in each phase, where Figures 5(a)–5(c) are consistent with the reasons analyzed in Figures 4(a)–4(c); in Figure 5(d), the storage cost of the CEABKS-MA system in Encrypt is slightly higher than that of the HP-CPABKS system; due to Uj<U, the ciphertext storage cost of the CEABKS-MA system is still limited.Figure 5
Storage cost comparison.
(a)
Setup(b)
Keygen(c)
Trapdoor(d)
Encrypt


## 6.1. Security Analysis

The CEABKS-MA system proposed in this paper can achieve IND-CPA security and IND-CKA security presented in Section 4.3 and is analyzed in detail as follows.Theorem 3.
Under the assumption that the Decisional q-parallel Bilinear Diffie-Hellman Exponent (BDHE) assumption [44] holds, that the advantage of all polynomial-time opponents who can win the IND-CPA game can be ignored.Proof.
Assume that adversary A can break the CEABKS-MA system by a nonnegligible advantageδ. A chooses a challenging matrix M∗, and then, B handles the q-DBDHE problem as follows.
Setup. Given a q-DBDHE challenge instance ϕ,R, B first chooses a0∈Zp and sets a0=a′+a1q+1; then, B defines the public key component Y=eg,ga0=ega1,ga1qeg,ga′. B chooses a random value vi∈Zp for each i∈Uj and sets APKi,j=gvi. To simulate the group elements hi, B picks a random element βi∈Zp for each i∈Uj. Let ρ∗ι=i, then B sets hi as follows:
(5)hi=gβi∏ι∈Φga1Mι,1∗/bιga12Mι,2∗/bι⋯ga1n∗Mι,n∗∗/bι,where Φ denotes the set of indices ι. If Φ=∅, B sets hi=gβi, and the values of hi are randomly distributed due to gβi.
Phase 1. In this phase, B needs to answer A’s key queries. Assume that A provides an attribute set S that do not satisfy M∗, and B chooses a vector x∗=x1∗,⋯,xn∗∗ such that x1∗=−1 for all ιρ∗ι∈S have x∗·Mι∗=0. Then, B randomly chooses an element ϑ∈Zp and defines t as follows:
(6)t=ϑ+x1∗a1q+x2∗a1q−1+⋯+xn∗∗a1q−n∗+1.
Then, B computesK′2:
(7)K′2=gϑz∏ι=1n∗gxι∗za1q+1−ι=gtz.
Based on the definition oft above, it can be inferred that ga1t contains ga1q+1 which can be cancelled by ga0. Thus, B computes K′1 as follows:
(8)K′1=ga′zga1ϑz∏ι∈2,n∗gvιa1q+2−ι=ga0zga1tz.
For each attributeτ∈S, B defines K′τ if ρ∗ι≠τ sets K′τ=K′2gβτ/vτ. Under this condition, B cannot simulate K′τ for the attribute τ∈S in M∗, since K′τ contains the term ga1q+1/bι. If there exists a set Φ=ι such that ρ∗ι=τ and B computes K′τ as follows:
(9)K′τ=K′2βτ/vτ∏ι∈Φ∏k∈1,n∗ga1kϑ/bιMi,k∗/vτ·∏ι∈Φ∏k∈1,n∗∏k′∈1,n∗ga1q+1+k−k′/bιMi,j∗/vτ.
A sends a revoked attributeatt′i to perform an updated attribute version key query. B randomly selects a new value v^′i∈Zpv^′i≠v′i and computes the updated attribute version key as ASK′i,j=v^′i/v′i and returns it as A.
Challenge. A submits two challenging messages m0,m1 to B with corresponding encryption keys sk0,sk1, and then, B randomly selects κ∈0,1 and computes CEκ=skEκ·eg,ga0s,C′=gs. However, since the ciphertext component Ci,1 contains some terms that should be removed, it is difficult to simulate Ci,1, where i∈1,l∗. To solve this problem, B randomly chooses y2∗,⋯,yn∗∗∈Zp and shares the secret s as follows:
(10)x=s,sa1+y2∗,sa12+y3∗,⋯,sa1n∗−1+yn∗∗.
Furthermore, B chooses random elementsr2∗,⋯,rn∗∗∈Zp. Let Qi be the set of all ρi=ρk′ satisfying i∈1,l∗. Finally, B outputs Ci,1,Ci,2 as follows:
(11)Ci,1=hρ∗iri∗∏k∈2,n∗ga1Mi,k∗yk∗∗gbis−βρ∗i·∏k′∈Ωi∏k∈1,n∗ga1ksbi/bk′Mk′,k∗,Ci,2=g−ri∗−sbivρ∗i.
Phase 2. Phase 2 has the same process as Phase 1.
Guess. A returns a guess bit κ′∈0,1, if κ′=κ; B returns “0” indicating that R=eg,ga1q+1s; otherwise, B returns “1” indicating that R is a randomly chosen element of the group GT. When R is a tuple, B returns a perfect simulation, which then yields PrBϕ,R=eg,ga1q+1s=0=1/2+δ. When R is a random element in the group GT and the encryption key skκ is completely hidden from A, then one obtains PrBϕ,R=0=1/2. Thus, B simulates the above security game with a nonnegligible advantage. This completes the proof of Theorem 3.Theorem 4.
Based on a given one-way hash functionH, the CEABKS-MA system prevents chosen keyword attacks.
Selecting a random valued∈Zp, the advantage of adversary A in distinguishing between gd and ga0s+πhρiπHkw0 is the same as the advantage of distinguishing between gd and ga0s+πhρiπHkw1 with the same advantage. Assume that A can distinguish between gd and ga0s+π, and the defined secure interactive game is as follows.Proof.
Setup. B randomly selects a0,a1∈Zp and returns the public key PK=g,ga0,ga1 to A.
Phase 1. A can query OKeygen and OTrap for keys and trapdoors in polynomial time.
(i)
OKeygen. B computes K′=ga0a1 and sends K′ to A(ii)
OTrap. B randomly selects μ∈Zp and computes T0=ga0μhτμHkw′, T1=ga1μ, and T2=ga0a1μ according to query keyword kw′, which gives the trapdoor Tkw′=T0,T1,T2
Challenge. A inputs two keywords of the same length kw0,kw1. B selects s,π∈Zp and picks κ∈0,1. If κ=0, B sets I0=ga1π, I1=gd, and C′=gs, otherwise, sets I0=ga1π, I1=ga0s+π, and C′=gs.
Phase 2. A performs a query similar to Phase 1 but restricts kw≠kw0,kw1.
Assume thatυ∈Zp and if A can construct eg,gυa0s+π using the term gυ returned by the query, then A can distinguish between gd and ga0s+π. Thus, it needs to be shown that A can only use the term gυ to construct eg,gυa0s+π by a negligible advantage.
LetG1=ϕ1ηη∈Zp,GT=ϕ2ηη∈Zp, where ϕ1 and ϕ2 are two introjection functions mapped from Zp to a set with p3 elements. In the mapping between ϕ1 and ϕ2, the advantage of adversary A in distinguishing elements is negligible, so it is only necessary to consider the probability of adversary A in constructing eg,gυa0s+π using gυ.
If A want to geteg,gυa0s+π from gυ, since only a1π contains π, υ must contain a1 to get eg,gυa0s+π. A will try to construct eg,gυ′a0s+π based on υ′=υa1. However, A also needs to get υ′a0a1s containing the term a0a1 and the secret value s. Since only B has the primary key a1, A cannot obtain eg,gυ′a0s+π.
Thus, it can be concluded that adversary A cannot distinguishga0s+πhρiπHkw0 and ga0s+πhρiπHkw1. That is, the CEABKS-MA system is secure in the chosen keyword attack game, which completes the proof of Theorem 4.In addition, the CEABKS-MA system can resist collusion attacks by users and achieve the security of user key. (1) The CEABKS-MA system prevents user collusion attacks by assigning a global identifieruid to each DU. In Keygen, the key component is associated with a random value t, so it is difficult for a malicious user to isolate the t value from a given key to perform collusion queries in the absence of a random value t. (2) The search user uses a random value μ to blind the key when performing queries to ensure the security and confidentiality of the user’s key.


## 6.2. Performance Analysis

The CEABKS-MA system implements fine-grained keyword search, multiauthority structure, and attribute update and has high efficiency in both key and trapdoor generation as well as search and decryption phases. Table1 shows a functional comparison between the CEABKS-MA system and other existing systems [29–31].Table 1
Functional comparison of different system.
SystemHP-CPABKS [29]VKSE [30]LSABE-MA [31]CEABKS-MAKeyword search√√√√Attribute revocation×××√Multi-authority××√√High efficiency×××√Access structureLSSSTreeLSSSLSSSThe theoretical computation and storage costs of the CEABKS-MA system and the existing scheme [29] are analyzed, as shown in Tables 2 and 3, respectively. For the computation costs in Table 2, we mainly consider several more time-consuming operations, namely, bilinear pairing operation P and exponential operation E or ET in group G or GT. The number of system attributes is denoted as Uj and U for the CEABKS-MA system and HP-CPABKS system, respectively, and the number of user attributes is denoted as S. Since the CEABKS-MA system uses a distributed key distribution structure, S≪Uj≪U in practice, the CEABKS-MA system consumes less time than the HP-CPABKS system in Keygen and Trapdoor. The computation cost of the CEABKS-MA system in Encrypt will be higher than that of the HP-CPABKS system when setting Uj=U, but the online/offline encryption method is extended to the proposed system, and the ciphertext generation is a one-time operation. In Search, the computation cost of the CEABKS-MA system is constant, and the search efficiency is much higher than that of the HP-CPABKS system.Table 2
Theoretical computation cost comparison.
SystemCEABKS-MAHP-CPABKS [29]KeygenS+5E2U+1E+ETTrapdoorS+2E2U+1EEncrypt3Uj+3E+ET2U+1E+ETSearch3P2U+1P+ETTable 3
Theoretical storage cost comparison.
SystemCEABKS-MAHP-CPABKS [29]Setup2Uj+1Zp+2Uj+2G+GTU+2Zp+U+1G+GTKeygenS+5G2U+1G+U+2ZpTrapdoor3G2U+1G+2ZpEncrypt3Uj+3G+GT2U+1G+U+1ZpFor the storage costs in Table3, element lengths in G,GT,Zp are defined as G,GT,Zp, respectively. When Uj=U, the storage cost of the CEABKS-MA system in Setup is higher due to the added attribute update function. Similar to the computation cost analysis, the storage cost of the CEABKS-MA system is much lower than that of the HP-CPABKS system in Keygen and Trapdoor, and the storage cost in Trapdoor is constant, which is more suitable for resource-constrained devices.To verify the above theoretical analysis, we present an experimental analysis of the computation efficiency and storage consumption of the CEABKS-MA system and the HP-CPABKS system. The experimental simulation is Windows 10, Intel(R) Core(TM) i3-8100 CPU@3.60 GHz. The programming language is C and parsing-based cryptography (PBC) libraries. The parameters related to computation and storage costs are set asG=GT=1024 bits, Zp=160 bits, S∈1,50, and Uj=U∈1,100.Figure4 shows the actual computation time comparison of different systems in each phase; in Figure 4(a), the computation cost of both systems in Setup increases with the expanding number of system attributes, and the CEABKS-MA system costs slightly more time than the HP-CPABKS system, which is consistent with the theoretical analysis, but note that Uj<U in practice. The number of system attributes in Figures 4(b) and 4(c) is fixed at U=50; it can be seen that the time consumption of the CEABKS-MA system in Keygen and Trapdoor increases linearly with the number of user attributes but is still much lower than that of the HP-CPABKS system, and S≪U, so the CEABKS-MA system has higher efficiency and application value for search users with limited computational resources. Figure 4(d) shows the comparative analysis of search time, which is constant and much lower than that of the HP-CPABKS system.Figure 4
Computation cost comparison.
(a)
Setup(b)
Keygen(c)
Trapdoor(d)
SearchFigure5 shows the actual storage cost comparison of different systems in each phase, where Figures 5(a)–5(c) are consistent with the reasons analyzed in Figures 4(a)–4(c); in Figure 5(d), the storage cost of the CEABKS-MA system in Encrypt is slightly higher than that of the HP-CPABKS system; due to Uj<U, the ciphertext storage cost of the CEABKS-MA system is still limited.Figure 5
Storage cost comparison.
(a)
Setup(b)
Keygen(c)
Trapdoor(d)
Encrypt


## 7. Conclusion

In this paper, we propose a secure and efficient CEABKS-MA system to support IoV data sharing. The cloud-edge-end collaborative search architecture is designed to meet the real-time search requirements of users and alleviate the severe computation and storage overload problem in the cloud. The multiauthority structure is designed to effectively avoid single-point performance bottlenecks. In addition, the proposed system implements fine-grained keyword search for specified vehicle attributes and extends lightweight encryption and decryption to support attribute updates. Then, this paper demonstrates that the CEABKS-MA system can achieve IND-CPA and IND-CKA security. Experimental simulations prove that the proposed system can effectively reduce computation and storage costs. Since the search query of users is diverse and personalized, on the basis of protecting user privacy, we will dig deeper into users’ search intentions and provide users with more intelligent search results.



---

*Source: 3513063-2022-05-31.xml*