# Privacy-Preserving Attribute-Based Keyword Search with Traceability and Revocation for Cloud-Assisted IoT

Authors: Kai Zhang; Yanping Li; Laifeng Lu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

With the rapid development of cloud computing and Internet of Things (IoT) technology, it is becoming increasingly popular for source-limited devices to outsource the massive IoT data to the cloud. How to protect data security and user privacy is an important challenge in the cloud-assisted IoT environment. Attribute-based keyword search (ABKS) has been regarded as a promising solution to ensure data confidentiality and fine-grained search control for cloud-assisted IoT. However, due to the fact that multiple users may have the same retrieval permission in ABKS, malicious users may sell their private keys on the Internet without fear of being caught. In addition, most of existing ABKS schemes do not protect the access policy which may contain privacy information. Towards this end, we present a privacy-preserving ABKS that simultaneously supports policy hiding, malicious user traceability, and revocation. Formal security analysis shows that our scheme can not only guarantee the confidentiality of keywords and access policies but also realize the traceability of malicious users. Furthermore, we provide another more efficient construction for public tracing.


---

## Body

## 1. Introduction

As a prevalent Internet technology, Internet of Things (IoT) [1] has been widely used in various industries, such as smart healthcare, transportation, and city [2–5]. Due to the limited computing and storage capacity of many IoT devices, users often need to store IoT data in the cloud. The cloud-assisted IoT [6] technology can be used to collect and store massive medical data, so it is expected to greatly improve the efficiency of medical institutions and promote the development of smart healthcare. Apart from the efficiency concern, security issue is an important concern hindering the widespread application of IoT technology [7–10]. Especially for the smart healthcare system based on cloud-assisted IoT, the data security issue has become a key challenge, due to the fact that the sensitive personal health record (PHR) outsourced in the cloud is vulnerable to hacker attacks.Although the traditional encryption technology [11] can protect the data security, it makes the ciphertext data unable to retrieve, thus greatly reducing the availability of IoT data. An inefficient solution is that data users download ciphertext data from the cloud, decrypt it, and then search on plaintext data. However, ordinary users do not have enough storage and computing power to retrieve the huge amount of cloud data locally. Public key encryption with keyword search (PEKS) [12, 13] is a more efficient solution, which can realize the retrieval of ciphertext by a cloud server without decryption. In a PEKS scheme, a data user can delegate the cloud server to retrieve all cloud ciphertexts by sending a search token to it. However, in order to avoid the abuse of retrieval ability, data owners usually want to control the retrieval permission.As an efficient and flexible solution to meet the above requirements, attribute-based keyword search (ABKS) [14, 15] can realize data confidentiality, ciphertext retrieval, and fine-grained access control simultaneously. In a ciphertext-policy ABKS (CP-ABKS) system, a data owner encrypts the file keyword by an access policy and only users whose attributes satisfy the access policy can retrieve the ciphertext file. However, the public access policy in CP-ABKS may disclose privacy information in the smart medical cloud system. For example, a medical institution wants to share PHR with users whose attributes meet the policy “(Institution: hospital A AND Patient ID: 202007953) OR (Institution: hospital B AND Position: oncologist)”; then it encrypts the PHR keyword by this policy and generates the corresponding ciphertext. Note that the access policy is exposed together with the ciphertext in the traditional CP-ABKS, so anyone can infer that the patient with the identity “202007953” is likely to have a tumor. Moreover, multiple users with the same attributes have the same retrieval ability and the user identity cannot be determined by the user private key in CP-ABKS, so malicious users may sell their private keys without worrying about being caught. As in the above example, if one of the multiple oncologists in hospital B sells his private key online, it is difficult to accurately identify and revoke the malicious user who sells his private key.


### 1.1. Our Contributions

Up till now, there is no secure ABKS scheme that simultaneously supports hidden policy, traceability, and revocation. To address these issues, we propose a traceable and revocable hidden ABKS (TR-HABKS) scheme and an enhanced TR-HABKS (eTR-HABKS) scheme, which support the above three properties at once. Moreover, the eTR-HABKS scheme achieves two other remarkable properties: (1) no identity table for tracing: the scheme only needs to maintain an identity table for revocation but does not require any identity table for tracing; (2) public traceability: besides the trusted authority, anyone without additional secret information can also run the tracing algorithm to capture malicious users. Specifically, our TR-HABKS and eTR-HABKS schemes provide the following properties:(i)
Fine-Grained Search Control. In our schemes, a data user’s search token is corresponding to his attributes and can be used to retrieve ciphertext only when the attributes satisfy the ciphertext policy. To control the user search permission, our schemes allow the data owner to encrypt the keyword by a specified access policy, which can be expressed as an AND-gates on multivalued attributes.(ii)
Hidden Policy. Our schemes not only guarantee the confidentiality of the keyword but also protect the privacy of the policy. Different from those ABKS schemes which only prove the keyword security, we also prove that access policies are also indistinguishable in the selective security model. Moreover, our schemes require the data owner to encrypt the keyword by his private key, so that the adversary cannot launch the keyword guessing attacks (KGA) by generating the ciphertext himself.(iii)
Traceability. Both the TR-HABKS and eTR-HABKS schemes achieve the user traceability in ABKS. When a malicious user leaks his private key in our TR-HABKS scheme, then the trusted authority can determine the identity of the malicious user by a tracing identity table. In our eTR-HABKS scheme, everyone can trace the malicious user’s identity without the help of any identity table.(iv)
Revocation. When the malicious user’s identity is determined, our schemes can effectively revoke the user by managing a registration table. In our schemes, the trusted authority adds each legitimate user to a registered identity table in the key generation stage and can easily revoke the malicious user by deleting his identity from the identity table.The properties comparison between our schemes with other related works can be seen in Table1. The symbol “—” means not applicable.Table 1
Properties comparison.
Scheme[12][16][14][15][17][18]TR-HABKSeTR-HABKSSearch✓✓✓✓✓✓✓✓Fine-grained search control✕✕✓✓✓✓✓✓Hidden policy——✕✕✕✓✓✓Resist KGA✕✓✕✕✕✓✓✓Traceability✕✕✕✕✕✕Private traceabilityPublic traceabilityRevocation✕✕✕✓✓✕✓✓


### 1.2. Related Work

#### 1.2.1. Attributed-Based Encryption

Attribute-based encryption (ABE) [19] is a practical method for fine-grained access control and can be divided into key-policy ABE (KP-ABE) [20] and ciphertext-policy ABE (CP-ABE) [21, 22]. Based on KP-ABE and CP-ABE, dual-policy ABE (DP-ABE) [23, 24] was also introduced for achieving content-based and role-based access control simultaneously. However, in traditional CP-ABE and DP-ABE, the access policy corresponding to the ciphertext may disclose the user’s privacy. To address this problem, Nishide et al. [25] proposed the first CP-ABE in which access policies can be hidden by the encryptor. Later, Lai et al. [26] presented a high expressive CP-ABE with partially hidden access structure that can be expressed as a linear secret-sharing scheme (LSSS) [27]. Yang et al. [28] proposed a privacy-preserving CP-ABE to hide both the attribute names and the attribute values in the access policy. Based on an optimized vector transformation approach, Sun et al. [29] proposed a lightweight hiding CP-ABE scheme for IoT-oriented smart health. Their scheme can not only support policy hiding but also support offline encryption and outsourcing decryption. In order to prevent key abuse, Hinek et al. [30] first considered the trace problem in ABE and constructed a traceable ABE scheme. Liu et al. [31] proposed a high expressive white-box traceable ABE that supports traceability of the malicious user who sold his decryption key on the Internet. For a decryption black-box in ABE, Liu et al. [32] later proposed a black-box traceable CP-ABE that can trace the malicious user whose private key was used to construct the decryption device. To support more flexible attributes, Ning et al. [33] presented a traceable CP-ABE that simultaneously supports white-box traceability and large universe. Ying et al. [34] presented a black-box traceable CP-ABE with hidden policy in e-healthcare cloud. Recently, several novel ABE schemes [35–37] were proposed for stronger security and user revocation in cloud storage system. Unfortunately, the above ABE schemes cannot search the ciphertext data in the cloud.


#### 1.2.2. Attribute-Based Keyword Search

Boneh et al. [12] first introduced the concept of PEKS and constructed the first concrete PEKS scheme. In the scheme, the user authorizes a third party to search the ciphertext by giving him a search token that is associated with a keyword; the third party returns the search results to the user but without learning the keyword information. However, Byun et al. [38] pointed out that the PEKS scheme [12] cannot resist KGA. Specifically, anyone can generate a ciphertext by encrypting a keyword in PEKS scheme, so the third party can use the search token to continuously retrieve the ciphertexts corresponding to different keywords to guess the keyword corresponding to the search token. To resist the above attack in PEKS, Huang and Li [16] presented a public key authenticated encryption with keyword search, in which the keyword needs to be authenticated by the data owner during the encryption phase. Miao et al. [39] proposed a verifiable searchable encryption, which can achieve verifiable searchability and resist KGA. In order to support fine-grained search authorization, Zheng et al. [14] proposed a CP-ABKS scheme based on PEKS and CP-ABE [21]. In the CP-ABKS scheme, a data owner encrypts a keyword by an access policy and only users whose attributes meet the access policy can retrieve the ciphertext. With the help of proxy reencryption and lazy reencryption techniques, Sun et al. [15] presented a revocable ABKS scheme that can delegate the search and update workload to the cloud server. Liu et al. [17] proposed a searchable ABE with efficient revocation and outsourced decryption for cloud IoT. Based on online/offline encryption and outsourced decryption techniques, Miao et al. [40] presented an efficient ABKS scheme in the cloud-assisted healthcare IoT system. To protect access policies, Qiu et al. [18] presented a hidden policy CP-ABKS against KGA. Later, Miao et al. [41] presented a privacy-preserving CP-ABKS in multiowner setting. However, Sun et al. [42] pointed out that four types of KGA exist in this scheme. To achieve hidden policy and traceability simultaneously, Liu et al. [43] presented a privacy-preserving ABKS with user tracing. However, the security proof cannot ensure the policy hiding property due to its flawed security model. Unlike with the formal security model in hidden policy CP-ABKS [18, 41], the security model in [43] only shows the indistinguishability of keywords and does not consider the indistinguishability of access policies.


### 1.3. Organization

The rest of this paper is organized as follows.Section 2 introduces the necessary background information of the paper. Section 3 defines the algorithm and model for TR-HABKS. Section 4 presents the TR-HABKS construction and proves its correctness and security. Section 5 presents the eTR-HABKS construction and compares the efficiencies of the TR-HABKS and eTR-HABKS schemes. Section 6 concludes the paper.


## 1.1. Our Contributions

Up till now, there is no secure ABKS scheme that simultaneously supports hidden policy, traceability, and revocation. To address these issues, we propose a traceable and revocable hidden ABKS (TR-HABKS) scheme and an enhanced TR-HABKS (eTR-HABKS) scheme, which support the above three properties at once. Moreover, the eTR-HABKS scheme achieves two other remarkable properties: (1) no identity table for tracing: the scheme only needs to maintain an identity table for revocation but does not require any identity table for tracing; (2) public traceability: besides the trusted authority, anyone without additional secret information can also run the tracing algorithm to capture malicious users. Specifically, our TR-HABKS and eTR-HABKS schemes provide the following properties:(i)
Fine-Grained Search Control. In our schemes, a data user’s search token is corresponding to his attributes and can be used to retrieve ciphertext only when the attributes satisfy the ciphertext policy. To control the user search permission, our schemes allow the data owner to encrypt the keyword by a specified access policy, which can be expressed as an AND-gates on multivalued attributes.(ii)
Hidden Policy. Our schemes not only guarantee the confidentiality of the keyword but also protect the privacy of the policy. Different from those ABKS schemes which only prove the keyword security, we also prove that access policies are also indistinguishable in the selective security model. Moreover, our schemes require the data owner to encrypt the keyword by his private key, so that the adversary cannot launch the keyword guessing attacks (KGA) by generating the ciphertext himself.(iii)
Traceability. Both the TR-HABKS and eTR-HABKS schemes achieve the user traceability in ABKS. When a malicious user leaks his private key in our TR-HABKS scheme, then the trusted authority can determine the identity of the malicious user by a tracing identity table. In our eTR-HABKS scheme, everyone can trace the malicious user’s identity without the help of any identity table.(iv)
Revocation. When the malicious user’s identity is determined, our schemes can effectively revoke the user by managing a registration table. In our schemes, the trusted authority adds each legitimate user to a registered identity table in the key generation stage and can easily revoke the malicious user by deleting his identity from the identity table.The properties comparison between our schemes with other related works can be seen in Table1. The symbol “—” means not applicable.Table 1
Properties comparison.
Scheme[12][16][14][15][17][18]TR-HABKSeTR-HABKSSearch✓✓✓✓✓✓✓✓Fine-grained search control✕✕✓✓✓✓✓✓Hidden policy——✕✕✕✓✓✓Resist KGA✕✓✕✕✕✓✓✓Traceability✕✕✕✕✕✕Private traceabilityPublic traceabilityRevocation✕✕✕✓✓✕✓✓


## 1.2. Related Work

### 1.2.1. Attributed-Based Encryption

Attribute-based encryption (ABE) [19] is a practical method for fine-grained access control and can be divided into key-policy ABE (KP-ABE) [20] and ciphertext-policy ABE (CP-ABE) [21, 22]. Based on KP-ABE and CP-ABE, dual-policy ABE (DP-ABE) [23, 24] was also introduced for achieving content-based and role-based access control simultaneously. However, in traditional CP-ABE and DP-ABE, the access policy corresponding to the ciphertext may disclose the user’s privacy. To address this problem, Nishide et al. [25] proposed the first CP-ABE in which access policies can be hidden by the encryptor. Later, Lai et al. [26] presented a high expressive CP-ABE with partially hidden access structure that can be expressed as a linear secret-sharing scheme (LSSS) [27]. Yang et al. [28] proposed a privacy-preserving CP-ABE to hide both the attribute names and the attribute values in the access policy. Based on an optimized vector transformation approach, Sun et al. [29] proposed a lightweight hiding CP-ABE scheme for IoT-oriented smart health. Their scheme can not only support policy hiding but also support offline encryption and outsourcing decryption. In order to prevent key abuse, Hinek et al. [30] first considered the trace problem in ABE and constructed a traceable ABE scheme. Liu et al. [31] proposed a high expressive white-box traceable ABE that supports traceability of the malicious user who sold his decryption key on the Internet. For a decryption black-box in ABE, Liu et al. [32] later proposed a black-box traceable CP-ABE that can trace the malicious user whose private key was used to construct the decryption device. To support more flexible attributes, Ning et al. [33] presented a traceable CP-ABE that simultaneously supports white-box traceability and large universe. Ying et al. [34] presented a black-box traceable CP-ABE with hidden policy in e-healthcare cloud. Recently, several novel ABE schemes [35–37] were proposed for stronger security and user revocation in cloud storage system. Unfortunately, the above ABE schemes cannot search the ciphertext data in the cloud.


### 1.2.2. Attribute-Based Keyword Search

Boneh et al. [12] first introduced the concept of PEKS and constructed the first concrete PEKS scheme. In the scheme, the user authorizes a third party to search the ciphertext by giving him a search token that is associated with a keyword; the third party returns the search results to the user but without learning the keyword information. However, Byun et al. [38] pointed out that the PEKS scheme [12] cannot resist KGA. Specifically, anyone can generate a ciphertext by encrypting a keyword in PEKS scheme, so the third party can use the search token to continuously retrieve the ciphertexts corresponding to different keywords to guess the keyword corresponding to the search token. To resist the above attack in PEKS, Huang and Li [16] presented a public key authenticated encryption with keyword search, in which the keyword needs to be authenticated by the data owner during the encryption phase. Miao et al. [39] proposed a verifiable searchable encryption, which can achieve verifiable searchability and resist KGA. In order to support fine-grained search authorization, Zheng et al. [14] proposed a CP-ABKS scheme based on PEKS and CP-ABE [21]. In the CP-ABKS scheme, a data owner encrypts a keyword by an access policy and only users whose attributes meet the access policy can retrieve the ciphertext. With the help of proxy reencryption and lazy reencryption techniques, Sun et al. [15] presented a revocable ABKS scheme that can delegate the search and update workload to the cloud server. Liu et al. [17] proposed a searchable ABE with efficient revocation and outsourced decryption for cloud IoT. Based on online/offline encryption and outsourced decryption techniques, Miao et al. [40] presented an efficient ABKS scheme in the cloud-assisted healthcare IoT system. To protect access policies, Qiu et al. [18] presented a hidden policy CP-ABKS against KGA. Later, Miao et al. [41] presented a privacy-preserving CP-ABKS in multiowner setting. However, Sun et al. [42] pointed out that four types of KGA exist in this scheme. To achieve hidden policy and traceability simultaneously, Liu et al. [43] presented a privacy-preserving ABKS with user tracing. However, the security proof cannot ensure the policy hiding property due to its flawed security model. Unlike with the formal security model in hidden policy CP-ABKS [18, 41], the security model in [43] only shows the indistinguishability of keywords and does not consider the indistinguishability of access policies.


## 1.2.1. Attributed-Based Encryption

Attribute-based encryption (ABE) [19] is a practical method for fine-grained access control and can be divided into key-policy ABE (KP-ABE) [20] and ciphertext-policy ABE (CP-ABE) [21, 22]. Based on KP-ABE and CP-ABE, dual-policy ABE (DP-ABE) [23, 24] was also introduced for achieving content-based and role-based access control simultaneously. However, in traditional CP-ABE and DP-ABE, the access policy corresponding to the ciphertext may disclose the user’s privacy. To address this problem, Nishide et al. [25] proposed the first CP-ABE in which access policies can be hidden by the encryptor. Later, Lai et al. [26] presented a high expressive CP-ABE with partially hidden access structure that can be expressed as a linear secret-sharing scheme (LSSS) [27]. Yang et al. [28] proposed a privacy-preserving CP-ABE to hide both the attribute names and the attribute values in the access policy. Based on an optimized vector transformation approach, Sun et al. [29] proposed a lightweight hiding CP-ABE scheme for IoT-oriented smart health. Their scheme can not only support policy hiding but also support offline encryption and outsourcing decryption. In order to prevent key abuse, Hinek et al. [30] first considered the trace problem in ABE and constructed a traceable ABE scheme. Liu et al. [31] proposed a high expressive white-box traceable ABE that supports traceability of the malicious user who sold his decryption key on the Internet. For a decryption black-box in ABE, Liu et al. [32] later proposed a black-box traceable CP-ABE that can trace the malicious user whose private key was used to construct the decryption device. To support more flexible attributes, Ning et al. [33] presented a traceable CP-ABE that simultaneously supports white-box traceability and large universe. Ying et al. [34] presented a black-box traceable CP-ABE with hidden policy in e-healthcare cloud. Recently, several novel ABE schemes [35–37] were proposed for stronger security and user revocation in cloud storage system. Unfortunately, the above ABE schemes cannot search the ciphertext data in the cloud.


## 1.2.2. Attribute-Based Keyword Search

Boneh et al. [12] first introduced the concept of PEKS and constructed the first concrete PEKS scheme. In the scheme, the user authorizes a third party to search the ciphertext by giving him a search token that is associated with a keyword; the third party returns the search results to the user but without learning the keyword information. However, Byun et al. [38] pointed out that the PEKS scheme [12] cannot resist KGA. Specifically, anyone can generate a ciphertext by encrypting a keyword in PEKS scheme, so the third party can use the search token to continuously retrieve the ciphertexts corresponding to different keywords to guess the keyword corresponding to the search token. To resist the above attack in PEKS, Huang and Li [16] presented a public key authenticated encryption with keyword search, in which the keyword needs to be authenticated by the data owner during the encryption phase. Miao et al. [39] proposed a verifiable searchable encryption, which can achieve verifiable searchability and resist KGA. In order to support fine-grained search authorization, Zheng et al. [14] proposed a CP-ABKS scheme based on PEKS and CP-ABE [21]. In the CP-ABKS scheme, a data owner encrypts a keyword by an access policy and only users whose attributes meet the access policy can retrieve the ciphertext. With the help of proxy reencryption and lazy reencryption techniques, Sun et al. [15] presented a revocable ABKS scheme that can delegate the search and update workload to the cloud server. Liu et al. [17] proposed a searchable ABE with efficient revocation and outsourced decryption for cloud IoT. Based on online/offline encryption and outsourced decryption techniques, Miao et al. [40] presented an efficient ABKS scheme in the cloud-assisted healthcare IoT system. To protect access policies, Qiu et al. [18] presented a hidden policy CP-ABKS against KGA. Later, Miao et al. [41] presented a privacy-preserving CP-ABKS in multiowner setting. However, Sun et al. [42] pointed out that four types of KGA exist in this scheme. To achieve hidden policy and traceability simultaneously, Liu et al. [43] presented a privacy-preserving ABKS with user tracing. However, the security proof cannot ensure the policy hiding property due to its flawed security model. Unlike with the formal security model in hidden policy CP-ABKS [18, 41], the security model in [43] only shows the indistinguishability of keywords and does not consider the indistinguishability of access policies.


## 1.3. Organization

The rest of this paper is organized as follows.Section 2 introduces the necessary background information of the paper. Section 3 defines the algorithm and model for TR-HABKS. Section 4 presents the TR-HABKS construction and proves its correctness and security. Section 5 presents the eTR-HABKS construction and compares the efficiencies of the TR-HABKS and eTR-HABKS schemes. Section 6 concludes the paper.


## 2. Background

For a setS, let s⟵RS denote that an element s is chosen uniformly at random from S. Let ℤp denote the set 0,1,2,…,p−1, where p is a prime, let n denote the set 1,2,…,n, where n is a natural number, and let PPT denote probabilistic polynomial time.


### 2.1. Access Policy

In our system, the total number of attributes isn, and the access policy is represented by an AND-gates on multivalued attributes [25]. For each i∈n, let Ai be the attribute index, and let Si=vi,tt∈ni be the possible values of Ai, where ni is the number of possible values for Ai. Let L=Li be a user attributes set, where Li∈Si, and let P=Pii∈n be an access policy, where Pi⊆Si. If Li∈Pi for i∈n, we say that the attributes set L satisfies the access policy P, written as L⊨P; otherwise, we say that the attributes set L does not satisfy the access policy P, written as L⊭P. For ease of description, we use i instead of Ai to represent attribute index in our schemes.


### 2.2. Bilinear Map

An asymmetric bilinear group generatorG takes as input a security parameter λ and outputs a tuple G=p,G1,G2,GT,g1,g2,e, where p is a prime, G1,G2, and GT are multiplicative cyclic groups of order p, g1 (resp., g2) is a generator of G1 (resp., G2), and e:G1×G2⟶GT is an efficiently computable bilinear map with the following properties:(1)
Bilinear:∀g∈G1,h∈G2,a,b∈ℤp,ega,hb=eg,hab(2)
Nondegenerate:eg1,g2≠1


### 2.3. Signature

A signature scheme consists of the following algorithms:PK,SK⟵ KeyGen λ: The key generation algorithm gets the security parameter λ as input. It outputs a random key pair PK,SK.σ⟵ Sign SK,M: The signing algorithm gets a private key SK and a message M as input. It outputs a signature σ.0/1⟵ Verify PK,M,σ: The verifying algorithm gets a public key PK, a message M, and a signature σ as input. It outputs 1 if the signature is valid, and outputs 0 otherwise.The existential unforgeability under a weak chosen message attack [44] is defined by the following game:Query: the adversary sends messagesMjj∈qs to the challenger, where qs is the maximum number of signatures that the adversary can query.Response: the challenger runs the key generation algorithm and generates the signaturesσjj∈qs on the messages Mjj∈qs. Then, the challenger gives the public key PK and the signatures σjj∈qs to the adversary.Output: the adversary outputs a pairM,σ.The adversary wins this game if verifyPK,M,σ=1 and M,σ∉Mj,σjj∈qs. The adversary’s advantage is defined as the probability that he wins this game.Definition 1.
A signature scheme is said to be existentially unforgeable under a weak chosen message attack if all PPT adversaries have only a negligible advantage in this game.


## 2.1. Access Policy

In our system, the total number of attributes isn, and the access policy is represented by an AND-gates on multivalued attributes [25]. For each i∈n, let Ai be the attribute index, and let Si=vi,tt∈ni be the possible values of Ai, where ni is the number of possible values for Ai. Let L=Li be a user attributes set, where Li∈Si, and let P=Pii∈n be an access policy, where Pi⊆Si. If Li∈Pi for i∈n, we say that the attributes set L satisfies the access policy P, written as L⊨P; otherwise, we say that the attributes set L does not satisfy the access policy P, written as L⊭P. For ease of description, we use i instead of Ai to represent attribute index in our schemes.


## 2.2. Bilinear Map

An asymmetric bilinear group generatorG takes as input a security parameter λ and outputs a tuple G=p,G1,G2,GT,g1,g2,e, where p is a prime, G1,G2, and GT are multiplicative cyclic groups of order p, g1 (resp., g2) is a generator of G1 (resp., G2), and e:G1×G2⟶GT is an efficiently computable bilinear map with the following properties:(1)
Bilinear:∀g∈G1,h∈G2,a,b∈ℤp,ega,hb=eg,hab(2)
Nondegenerate:eg1,g2≠1


## 2.3. Signature

A signature scheme consists of the following algorithms:PK,SK⟵ KeyGen λ: The key generation algorithm gets the security parameter λ as input. It outputs a random key pair PK,SK.σ⟵ Sign SK,M: The signing algorithm gets a private key SK and a message M as input. It outputs a signature σ.0/1⟵ Verify PK,M,σ: The verifying algorithm gets a public key PK, a message M, and a signature σ as input. It outputs 1 if the signature is valid, and outputs 0 otherwise.The existential unforgeability under a weak chosen message attack [44] is defined by the following game:Query: the adversary sends messagesMjj∈qs to the challenger, where qs is the maximum number of signatures that the adversary can query.Response: the challenger runs the key generation algorithm and generates the signaturesσjj∈qs on the messages Mjj∈qs. Then, the challenger gives the public key PK and the signatures σjj∈qs to the adversary.Output: the adversary outputs a pairM,σ.The adversary wins this game if verifyPK,M,σ=1 and M,σ∉Mj,σjj∈qs. The adversary’s advantage is defined as the probability that he wins this game.Definition 1.
A signature scheme is said to be existentially unforgeable under a weak chosen message attack if all PPT adversaries have only a negligible advantage in this game.


## 3. Problem Formulation

In this section, we describe the algorithm definition, system model, and security model of TR-HABKS.


### 3.1. Algorithm Definition

A TR-HABKS scheme is formally defined as follows:MK,PK⟵ Setup λ: the setup algorithm gets the security parameter as input. It outputs the master key MK and the public parameter PK. In addition, it also generates two empty identity tables T1 and T2.SKid,L,SKo⟵ KeyGen MK,PK,id,L: the key generation algorithm gets an attributes set L, an identity id, the master key MK, and the public parameter PK as input. It outputs a private key SKid,L for a data user and a private key SKo for the data owner. In addition, it adds id to T1 and T2.CT⟵ Enc ω,P,SKo,PK: the encryption algorithm gets a keyword ω, an access policy P, the data owner’s private key SKo, and the public parameter PK as input. It outputs a ciphertext CT.TKid,L⟵ TokenGen SKid,L,PK,ω′: the token generation algorithm gets a data user’s private key SKid,L, the public parameter PK, and a keyword ω′ as input. It outputs a search token TKid,L.0/1⟵ Search TKid,L,CT,T1: the searching algorithm gets a ciphertext CT, a search token TKid,L, and an identity table T1 as input. It outputs 1 if 1L⊨P, 2id∈T1, and 3ω=ω′ and outputs 0 otherwise.id/⊤⟵ Trace SKid,L,PK,T2: the tracing algorithm gets a secret key SKid,L, the public parameter PK, and an identity table T2 as input. It outputs a user identity id if SKid,L passes the key sanity check and outputs symbol ⊤ otherwise. Key sanity check is a deterministic algorithm to test whether SKid,L needs to be traced.T1⟵ Revoke id,T1: the revocation algorithm gets a revocation user identity id and an identity table T1 as input. It outputs an updated table T1.


#### 3.1.1. Correctness

A TR-HABKS scheme is correct if the following condition holds: GivenMK,PK⟵ Setup λ,SKid,L,SKo⟵ KeyGenMK,PK,id,L,CT⟵ Enc ω,P,SKo,PK, TKid,L⟵ TokenGen SKid,L,PK,ω′, where L⊨P and id∈T1; then Search TKid,L,CT,T1 outputs 1 when ω=ω′.


### 3.2. System Model

As depicted in Figure1, our TR-HABKS system includes four entities: a trusted authority (TA), a data owner (DO), a cloud sever (CS), and multiple data users (DUs). Specifically, the role of each entity in our system model is described below.TA: TA first runs the setup algorithm, keeps the master keyMK secretly, and publishes the public parameter PK. Then, he uses his master key to generate private keys for DO and DUs. In addition, he creates an identity table T1 for user revocation and another identity table T2 for the malicious user tracing. When a malicious user sells his private key on the Internet, TA runs the tracing algorithm and then obtains the malicious user identity id from T2. Finally, TA deletes id from table T1 and sends T1 to CS to revoke the malicious user’s search ability.DO: when DO wants to encrypt a keywordω under an access policy P, he runs the encryption algorithm with his private key SKo and then generates a ciphertext CT corresponding to P,ω. Finally, he outsources the corresponding ciphertext CT to the cloud.DU: when DU wants to search the data files with the keywordω′, he runs the token generation algorithm with his private key SKid,L and then generates a search token TKid,L corresponding to id,L,ω′. Finally, he sends TKid,L to CS to query documents containing the keyword ω′.CS: when CS receives the search tokenTKid,L from DU, he first searches id in the table T1. If id∉T1, CS returns 0 and aborts; otherwise, CS runs the searching algorithm and returns the search result to DU.Figure 1
System model of TR-HABKS.In our threat model, TA and DO are assumed to be fully trusted; that is, they execute the above algorithm honestly and will not attack the system. CS is assumed to be an honest-but-curious adversary who honestly executes the searching algorithm but tries to infer the privacy of keywords. Note that the generation of ciphertext needs to use the private key of DO, so CS cannot generate ciphertext by itself and carry out keyword guessing attack. DUs in our system may be malicious adversaries who not only try to retrieve the ciphertext beyond their retrieval permission but also leak their private keys to others.


### 3.3. Security Model

In order to realize the confidentiality of keywords and access policies simultaneously, the security model of our TR-HABKS scheme requires that the adversary cannot distinguish between the encryption of a keywordω0 under an access policy P0 and the encryption of a keyword ω1 under an access policy P1. In the selective security model, the adversary needs to submit two challenge access policies P0 and P1 before the Setup phase. The selective security game includes the following phases:Inti: the adversary declares two challenge access policiesP0 and P1 that he tries to attack and gives them to the challenger.Setup: the challenger calls the setup algorithmMK,PK⟵ Setup λ and gives the public parameter PK to the adversary.Query Phase1: the adversary can repeatedly ask for private keys and search tokens as follows:(1)
Private Key QueryOKeyGenid,L: the adversary submits an identity id and an attributes set L to the challenger. If L⊨P0∧L⊭P1 or L⊭P0∧L⊨P1, then abort; otherwise, the challenger returns the corresponding private key SKid,L.(2)
Search Token QueryOTokenGenid,L,w: the adversary submits an identity id, an attributes set L, and a keyword ω to the challenger. The challenger returns the corresponding search token TKid,L.Challenge: the adversary submits two keywordsω0 and ω1 that satisfy the following constraint. If the adversary has queried the private key or search token for the attributes set L that satisfies both access policies P0 and P1, then we require that ω0=ω1. The challenger flips a random coin γ∈0,1 and returns the challenge ciphertext CT∗⟵ Enc ωγ,Pγ,SKo,PK to the adversary.Query Phase2: phase 1 is repeated with the restriction that the adversary cannot query the private key or search token for the attributes setL when L⊨P0∧L⊨P1 and ω0≠ω1.Guess: the adversary outputs a guessγ′∈0,1.The adversary wins this game ifγ=γ′, and his advantage is defined as Prγ=γ′−1/2.Definition 2.
A TR-HABKS scheme is said to be selectively secure if all PPT adversaries have only a negligible advantage in the above security game.
The traceability game of TR-HABKS is described as follows:Setup: the challenger runs the setup algorithmMK,PK⟵ Setup λ and gives the public parameter PK to the adversary.Key query: the adversary queries the private keys corresponding to pairsidj,Ljj∈qs, where idj is an identity, Lj is an attributes set, and qs is the maximum number of private keys that the adversary can query. The challenger returns the corresponding user private keys SKidj,Ljj∈qs.Key forgery: the adversary outputs a user private keySK∗.
In this game, the adversary’s advantage is defined asPrTraceSK∗,PK,T2∉id1,id2,…,idqs,⊤.Definition 3.
A TR-HABKS scheme is said to be fully traceable if all PPT adversaries have only a negligible advantage in this traceability game.


## 3.1. Algorithm Definition

A TR-HABKS scheme is formally defined as follows:MK,PK⟵ Setup λ: the setup algorithm gets the security parameter as input. It outputs the master key MK and the public parameter PK. In addition, it also generates two empty identity tables T1 and T2.SKid,L,SKo⟵ KeyGen MK,PK,id,L: the key generation algorithm gets an attributes set L, an identity id, the master key MK, and the public parameter PK as input. It outputs a private key SKid,L for a data user and a private key SKo for the data owner. In addition, it adds id to T1 and T2.CT⟵ Enc ω,P,SKo,PK: the encryption algorithm gets a keyword ω, an access policy P, the data owner’s private key SKo, and the public parameter PK as input. It outputs a ciphertext CT.TKid,L⟵ TokenGen SKid,L,PK,ω′: the token generation algorithm gets a data user’s private key SKid,L, the public parameter PK, and a keyword ω′ as input. It outputs a search token TKid,L.0/1⟵ Search TKid,L,CT,T1: the searching algorithm gets a ciphertext CT, a search token TKid,L, and an identity table T1 as input. It outputs 1 if 1L⊨P, 2id∈T1, and 3ω=ω′ and outputs 0 otherwise.id/⊤⟵ Trace SKid,L,PK,T2: the tracing algorithm gets a secret key SKid,L, the public parameter PK, and an identity table T2 as input. It outputs a user identity id if SKid,L passes the key sanity check and outputs symbol ⊤ otherwise. Key sanity check is a deterministic algorithm to test whether SKid,L needs to be traced.T1⟵ Revoke id,T1: the revocation algorithm gets a revocation user identity id and an identity table T1 as input. It outputs an updated table T1.


### 3.1.1. Correctness

A TR-HABKS scheme is correct if the following condition holds: GivenMK,PK⟵ Setup λ,SKid,L,SKo⟵ KeyGenMK,PK,id,L,CT⟵ Enc ω,P,SKo,PK, TKid,L⟵ TokenGen SKid,L,PK,ω′, where L⊨P and id∈T1; then Search TKid,L,CT,T1 outputs 1 when ω=ω′.


## 3.1.1. Correctness

A TR-HABKS scheme is correct if the following condition holds: GivenMK,PK⟵ Setup λ,SKid,L,SKo⟵ KeyGenMK,PK,id,L,CT⟵ Enc ω,P,SKo,PK, TKid,L⟵ TokenGen SKid,L,PK,ω′, where L⊨P and id∈T1; then Search TKid,L,CT,T1 outputs 1 when ω=ω′.


## 3.2. System Model

As depicted in Figure1, our TR-HABKS system includes four entities: a trusted authority (TA), a data owner (DO), a cloud sever (CS), and multiple data users (DUs). Specifically, the role of each entity in our system model is described below.TA: TA first runs the setup algorithm, keeps the master keyMK secretly, and publishes the public parameter PK. Then, he uses his master key to generate private keys for DO and DUs. In addition, he creates an identity table T1 for user revocation and another identity table T2 for the malicious user tracing. When a malicious user sells his private key on the Internet, TA runs the tracing algorithm and then obtains the malicious user identity id from T2. Finally, TA deletes id from table T1 and sends T1 to CS to revoke the malicious user’s search ability.DO: when DO wants to encrypt a keywordω under an access policy P, he runs the encryption algorithm with his private key SKo and then generates a ciphertext CT corresponding to P,ω. Finally, he outsources the corresponding ciphertext CT to the cloud.DU: when DU wants to search the data files with the keywordω′, he runs the token generation algorithm with his private key SKid,L and then generates a search token TKid,L corresponding to id,L,ω′. Finally, he sends TKid,L to CS to query documents containing the keyword ω′.CS: when CS receives the search tokenTKid,L from DU, he first searches id in the table T1. If id∉T1, CS returns 0 and aborts; otherwise, CS runs the searching algorithm and returns the search result to DU.Figure 1
System model of TR-HABKS.In our threat model, TA and DO are assumed to be fully trusted; that is, they execute the above algorithm honestly and will not attack the system. CS is assumed to be an honest-but-curious adversary who honestly executes the searching algorithm but tries to infer the privacy of keywords. Note that the generation of ciphertext needs to use the private key of DO, so CS cannot generate ciphertext by itself and carry out keyword guessing attack. DUs in our system may be malicious adversaries who not only try to retrieve the ciphertext beyond their retrieval permission but also leak their private keys to others.


## 3.3. Security Model

In order to realize the confidentiality of keywords and access policies simultaneously, the security model of our TR-HABKS scheme requires that the adversary cannot distinguish between the encryption of a keywordω0 under an access policy P0 and the encryption of a keyword ω1 under an access policy P1. In the selective security model, the adversary needs to submit two challenge access policies P0 and P1 before the Setup phase. The selective security game includes the following phases:Inti: the adversary declares two challenge access policiesP0 and P1 that he tries to attack and gives them to the challenger.Setup: the challenger calls the setup algorithmMK,PK⟵ Setup λ and gives the public parameter PK to the adversary.Query Phase1: the adversary can repeatedly ask for private keys and search tokens as follows:(1)
Private Key QueryOKeyGenid,L: the adversary submits an identity id and an attributes set L to the challenger. If L⊨P0∧L⊭P1 or L⊭P0∧L⊨P1, then abort; otherwise, the challenger returns the corresponding private key SKid,L.(2)
Search Token QueryOTokenGenid,L,w: the adversary submits an identity id, an attributes set L, and a keyword ω to the challenger. The challenger returns the corresponding search token TKid,L.Challenge: the adversary submits two keywordsω0 and ω1 that satisfy the following constraint. If the adversary has queried the private key or search token for the attributes set L that satisfies both access policies P0 and P1, then we require that ω0=ω1. The challenger flips a random coin γ∈0,1 and returns the challenge ciphertext CT∗⟵ Enc ωγ,Pγ,SKo,PK to the adversary.Query Phase2: phase 1 is repeated with the restriction that the adversary cannot query the private key or search token for the attributes setL when L⊨P0∧L⊨P1 and ω0≠ω1.Guess: the adversary outputs a guessγ′∈0,1.The adversary wins this game ifγ=γ′, and his advantage is defined as Prγ=γ′−1/2.Definition 2.
A TR-HABKS scheme is said to be selectively secure if all PPT adversaries have only a negligible advantage in the above security game.
The traceability game of TR-HABKS is described as follows:Setup: the challenger runs the setup algorithmMK,PK⟵ Setup λ and gives the public parameter PK to the adversary.Key query: the adversary queries the private keys corresponding to pairsidj,Ljj∈qs, where idj is an identity, Lj is an attributes set, and qs is the maximum number of private keys that the adversary can query. The challenger returns the corresponding user private keys SKidj,Ljj∈qs.Key forgery: the adversary outputs a user private keySK∗.
In this game, the adversary’s advantage is defined asPrTraceSK∗,PK,T2∉id1,id2,…,idqs,⊤.Definition 3.
A TR-HABKS scheme is said to be fully traceable if all PPT adversaries have only a negligible advantage in this traceability game.


## 4. Our TR-HABKS Scheme

In this section, we propose the construction of our TR-HABKS scheme and prove that it is selectively secure and fully traceable in the generic bilinear group model. We first adopt the technique from [18, 25] to realize hidden policy. The access policy P is embedded in the ciphertext CT as follows: if vi,t∈Pi, we set Ci,t,1=Ai,t,1αi,Ci,t,2=Ai,t,2αi; otherwise, we set Ci,t,1 and Ci,t,2 as two random elements in G1. That is, if vi,t∈Pi, these ciphertext components Ci,t,1,Ci,t,2 are well formed and can be used for successful search; otherwise, the ciphertext components Ci,t,1,Ci,t,2 are malformed. As it is hard to distinguish the well-formed ciphertext components from the malformed ciphertext components, the user cannot get the access policy from the corresponding ciphertext. Then, we exploit the signature technique in [31, 44] to realize the user traceability. On one hand, we inject the message yid and its signature into the user private key; then DU cannot rerandomize the private key component yid. On the other hand, we add the message yid and the corresponding user identity id in the identity table T2; then TA can identify the malicious user by the private key and the table T2. Finally, we add the legitimate user to the system by storing the user identity id and its corresponding element Cid in the registered identity table T1 and revoke the malicious user by deleting the corresponding pair id,Cid from the table T1.


### 4.1. Construction

Setupλ: TA first runs Gλ to obtain p,G1,G2,GT,g1,g2,e, where G1,G2, and GT are cyclic groups with prime order p, and e:G1×G2⟶GT is a bilinear map. Then, TA picks a,b,c⟵Rℤp and a one-way hash function H:0,1∗⟶ℤp. For each i∈n, TA chooses random exponents ai,t∈ℤpt∈ni and computes Ai,t,1=g1ai,t,Ai,t,2=g1cai,tt∈ni. Next, TA sets MK=a,b,c,ai,tt∈nii∈n as his master key and publishes the public parameter PK=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,g1c,g1bc,H,Ai,t,1,Ai,t,2t∈nii∈n. Finally, TA creates two empty identity tables T1 and T2.KeyGenMK,PK,id,L: DU submits his identity id and attributes set L=vi,tii∈n to TA in order to apply for the user private key. TA first picks xid,yid,β⟵Rℤp and sets K=xid,K0=g2a/bc+yidg2β/b,K1=yid. For each i∈n, TA picks λi⟵Rℤp and computes Ki,1=g2β+λiai,ti,Ki,2=g2λi. Then, TA sets SKid,L=K,K0,K1,Ki,1,Ki,2i∈n as DU private key and sends it to the DU with identity id. Next, TA picks α⟵Rℤp, sets SKo=α as DO private key, and sends it to DO. After that, TA computes Cid=eg1,g2−aαxid, stores id,Cid in the registered identity table T1, and sends T1 to CS for search permission revocation. Finally, TA adds id,yid in the identity table T2 and secretly stores T2 for user tracing.Encω,P,SKo,PK: to encrypt a keyword under an access policy P=Pii∈n, DO computes C=eg1,g2aα,C0=g1bα/Hω,C1=g1bcα/Hω. For each i∈n, DO chooses αi⟵Rℤp such that ∑i∈nαi=α, computes Ci,1=g1αi,Ci,2=g1cαi, and sets Ci,t,1 for each t∈ni as follows: if vi,t∈Pi, it sets Ci,t,1=Ai,t,1αi,Ci,t,2=Ai,t,2αi; otherwise, it sets Ci,t,1 and Ci,t,2 as two random elements in G1. Finally, DO uploads the ciphertext CT=C,C0,C1,Ci,1,Ci,2,Ci,t,1,Ci,t,2t∈nii∈n into the cloud.TokenGenSKid,L,PK,ω′: to generate a search token for a keyword ω′∈0,1∗, DU picks s⟵Rℤp and computes tok0=K0Hω′s,tok=K+s,tok1=K1. For each i∈n, DU computes Ti,1=Ki,1s,Ti,2=Ki,2s. Finally, DU sends the search token TKid,L=tok0,tok,tok1,Ti,1,Ti,2i∈n to CS.SearchTKid,L,CT,T1: when CS receives the search token TKid,L=tok0,tok,tok1,Ti,1,Ti,2i∈n from the DU with identity id, it first searches the entry id,Cid in the table T1. If no such entry exists, CS returns 0 and aborts; otherwise, CS obtains Cid from T1 and runs the following search algorithm. If Algorithm. If L=vi,tii∈n, it computes E=∏i∈neCi,1tok1Ci,2,Ti,1/eCi,ti,1tok1Ci,ti,2,Ti,2=eg1,g2αβsyid+c. Finally, CS returns 1 if ECtokCid=eC0tok1C1,tok0 and 0 otherwise.TraceSKid,L,PK,T2: if the private key is not in the form of SKid,L=K,K0,K1,Ki,1,Ki,2i∈n, TA returns ⊤ and aborts; otherwise, TA runs the following key sanity check algorithm. K,K1∈ℤp,K0,Ki,1,Ki,2∈G2,∃i∈n,s.t.(1)eg1bcg1bK1,K0eAi,ti,1K1Ai,ti,2,Ki,2=eg1,g2aeg1cg1K1,Ki,1.If the private keySKid,L does not pass the above check, TA returns ⊤ and aborts; otherwise, TA searches the entry id,K1 in table T2 and returns the corresponding id.Revokeid,T1: to revoke the search permission of the malicious user with identity id, TA updates table T1 by deleting the entry id,Cid and sends new table T1 to CS.


### 4.2. Correctness Proof

We now prove the correctness of our TR-HABKS scheme.If Scheme. If the user attributes L=vi,tii∈n satisfy the access policy P=Pii∈n, we have vi,ti∈Pi and Ci,ti,1=Ai,ti,1αi,Ci,ti,2=Ai,ti,2αi for each i∈n. Then,(2)∏i∈neCi,1tok1Ci,2,Ti,1eCi,ti,1tok1Ci,ti,2,Ti,2=∏i∈neg1αiyidg1cαi,Ki,1seAi,ti,1αiyidAi,ti,2αi,Ki,2s=∏i∈neg1yid+c,g2β+λiai,tisαieg1yid+cai,ti,g2λisαi=∏i∈neg1yid+c,g2βsαieg1yid+c,g2λiai,tisαieg1yid+cai,ti,g2λisαi=∏i∈neg1,g2βsyid+cαi=eg1,g2βsyid+c∑i∈nαi=eg1,g2αβsyid+c.If the userid is in table T1, then CS can obtain the corresponding Cid=eg1,g2−aαxid. Therefore,(3)ECtokCid=eg1,g2αβsyid+ceg1,g2aαxid+seg1,g2−aαxid=eg1,g2αβsyid+ceg1,g2aαs.In this case, ifω=ω′, we have(4)eC0tok1C1,tok0=eg1bαyid/Hωg1bcα/Hω,K0Hω′s=eg1bαc+yid,g2a/bc+yidg2β/bs=eg1bαc+yid,g2a/bc+yidseg1bαc+yid,g2β/bs=eg1,g2aαseg1,g2αβsyid+c=ECtokCid.


### 4.3. Proof of Selective Security

In this part, we prove the confidentiality of keywords and access policies in our scheme by a security reduction to the QLSZ scheme [18]. More specifically, if there are any attacks in our TR-HABKS scheme, then we can use these attacks to break the QLSZ scheme in the generic bilinear group model [18, 45]. Followed by the definition in [45], we consider three random encodings φ1,φ2,φT:Fp⟶0,1m, where Fp is an additive group and m>3logp. For i=1,2,T, let Gi=φix:x∈Fp. Therefore, there are three oracles to compute the group action on G1,G2,GT and an oracle to compute the bilinear map e. We refer to G1 as a generic bilinear group. In addition, our TR-HABKS scheme only allows DO to generate ciphertext by his private key, so the adversary cannot successfully carry out the keyword guessing attack.Theorem 1.
If the QLSZ scheme is selectively secure in the generic bilinear group model, then our TR-HABKS scheme is selectively secure.Proof.
Suppose that there exists a PPT adversaryA that can break our TR-HABKS scheme with advantage ε in the selective security model. We will build a simulator ℬ that can break the QLSZ scheme with advantage ε. Let C be the challenger corresponding to ℬ in the security game of QLSZ scheme. For more information about the QLSZ scheme and its security, please refer to [18].Inti: simulatorℬ receives two challenge access policies P0 and P1 from adversary A and then sends these policies to challenger C.Setup:C sends the QLSZ public parameter PK¯=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,H,Ai,tt∈nii∈n to ℬ. Then, ℬ picks c⟵Rℤp, sets Ai,t,1=Ai,t,Ai,t,2=Ai,tct∈ni, and sends the public parameter PK=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,g1c,g1bc,H,Ai,t,1,Ai,t,2t∈nii∈n to A.Query Phase1:ℬ answers the adversary’s private key and search token queries in our TR-HABKS scheme as follows:(1)
Private key queryOKeyGenid,L: in order to create the user private key for a pair id,L requested by A, ℬ first sends id,L to C to query the corresponding user private key in QLSZ scheme. When ℬ receives the QLSZ private key SK=xid,K0′=g2a+β′/b,Ki,1′=g2β′+λi′ai,ti,Ki,2′=g2λi′i∈n, it picks yid⟵Rℤp, implicitly sets β=β′/yid+c, λi=λi′/yid+c, and sets K=xid,K1=yid. Then, it computes K0=K0′1/yid+c=g2a/bc+yidg2β′/bc+yid=g2a/bc+yidg2β/b,Ki,1=Ki,1′1/yid+c=g2β′/yid+c+λi′/yid+cai,ti=g2β+λiai,ti,Ki,2=Ki,2′1/yid+c=g2λi′/yid+c=g2λi. Finally, ℬ sets the user private key SKid,L=K,K0,K1,Ki,1,Ki,2i∈n and sends it to A.(2)
Search token queryOTokenGenid,L,w: in order to create the search token for a tuple id,L,w requested by A, ℬ first runs OKeyGenid,L to obtain SKid,L=K,K0,K1,Ki,1,Ki,2i∈n. Then, ℬ picks s⟵Rℤp and computes tok0=K0Hω′s,tok=K+s,tok1=K1, Ti,1=Ki,1s,Ti,2=Ki,2s. Finally, ℬ sets the search token TKid,L=tok0,tok,tok1,Ti,1,Ti,2i∈n and sends it to A.Challenge:A submits two keywords ω0 and ω1 to ℬ, where the pair ω0,ω1 satisfies the following constraint. If the adversary has queried the private key or search token for the attributes set L that satisfies both access policies P0 and P1, then we require that ω0=ω1. Next, ℬ sends ω0 and ω1 to C to obtain the QLSZ challenge ciphertext CT′=C′,C0′,Ci,1′,Ci,t,2′t∈nii∈n. Finally, ℬ sets C=C′,C0=C0′,C1=C0c,Ci,1=Ci,1′,Ci,2=Ci,1c,Ci,t,1=Ci,t,2′,Ci,t,2=Ci,t,1c and returns the challenge ciphertext CT∗=C,C0,C1,Ci,1,Ci,2,Ci,t,1,Ci,t,2t∈nii∈n to A.Query Phase2: same as Phase 1.Guess: finally,A outputs a guess γ′∈0,1, and then ℬ sends γ′ to C.
According to the above simulation, ifA has advantage ε in the selective security game against our scheme, then ℬ can use A to break the QLSZ scheme with the same advantage ε.


### 4.4. Proof of Traceability

In this part, we prove that our TR-HABKS scheme is fully traceable based on the BB basic signature scheme, which has been proved to be existentially unforgeable under a weak chosen message attack in [44]. In order to prove the traceability, we assume that there exists a PPT adversary A who can win the traceability game, and then we construct a simulator ℬ that can break the BB basic signature scheme under a weak chosen message attack. Let C denote the BB challenger corresponding to ℬ in the signature security game. For more information about the BB basic signature scheme and its security, please refer to [44].Theorem 2.
If the BB basic signature scheme is existentially unforgeable under a weak chosen message attack, then our TR-HABKS scheme is fully traceable.Proof.
Before the game starts, challengerC sets a bilinear group p,G1,G2,GT,g1,g2,e. G1,G2, and GT are the cyclic groups of prime order p, g1 is a generator of G1, g2 is a generator of G2, and e:G1×G2⟶GT is a bilinear map.


#### 4.4.1. Setup

Simulatorℬ first chooses random values yj∈ℤpj∈qs and makes signature queries by submitting the values yj∈ℤpj∈qs to challenger C. Then, C sends the BB public parameter PK¯=p,G1,G2,GT,e,g1,g2,g1c and the corresponding signatures yj,σj=g21/yj+cj∈qs to ℬ. For each i∈n, ℬ chooses random exponents ai,t∈ℤpt∈ni and computes Ai,t,1=g1ai,t,Ai,t,2=g1cai,tt∈ni. Next, ℬ picks a,b⟵Rℤp and a one-way hash function H:0,1∗⟶ℤp and computes eg1,g2a,g1b,g1c,g1bc. Finally, ℬ sends the public parameter PK=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,g1c,g1bc,H,Ai,t,1,Ai,t,2t∈nii∈n to adversary A and initializes an empty identity table T2.


#### 4.4.2. Key query

WhenA makes user private key query for idj,Lj, ℬ first picks xj,β⟵Rℤp and sets Kj=xj,K0,j=σja/bg2β/b=g2a/bc+yjg2β/b,K1,j=yj. For each i∈n, ℬ picks λi,j⟵Rℤp and computes Ki,1,j=g2β+λi,jai,ti,Ki,2,j=g2λi,j. Then, ℬ sets SKidj,Lj=Kj,K0,j,K1,j,Ki,1,j,Ki,2,ji∈n as the corresponding private key and returns it to A. Finally, ℬ adds idj,yj to T2.


#### 4.4.3. Key forgery

AdversaryA outputs a user private key SK∗.IfA wins the above traceability game, then TraceSK∗,PK,T2∉id1,id2,…,idqs,⊤. Hence, the key SK∗=K,K0,K1,Ki,1,Ki,2,Ki,3i∈n satisfies the following conditions: K1∉y1,y2,…,yqs, K,K1∈ℤp,K0,Ki,1,Ki,2∈G2, and ∃i∈n,s.t.eg1bcg1bK1,K0⋅eAi,ti,1K1Ai,ti,2,Ki,2=eg1,g2aeg1cg1K1,Ki,1.Assuming thatKi,1=g2βi,Ki,2=g2λi, where βi∈ℤp and λi∈ℤp are unknown, we have eg1bK1+c,K0eg1K1+cai,ti,g2λi=eg1,g2aeg1K1+c,g2βi, and then eg1,K0K1+c=eg1,g2a+K1+cβi−λiK1+cai,ti. Therefore, K0b=g2a+K1+cβi−λiK1+cai,ti/K1+c=g2a/K1+cg2βig2−λiai,ti=g2a/K1+cKi,1Ki,2−ai,ti.Finally,ℬ computes σ=K0bKi,2ai,ti/Ki,11/a=g21/K1+c and then obtains a valid signature σ on message K1, where K1∉y1,y2,…,yqs. Hence, if A has advantage ε in the traceability game, then ℬ can forge a valid BB basic signature scheme with advantage ε under a weak chosen message attack.


## 4.1. Construction

Setupλ: TA first runs Gλ to obtain p,G1,G2,GT,g1,g2,e, where G1,G2, and GT are cyclic groups with prime order p, and e:G1×G2⟶GT is a bilinear map. Then, TA picks a,b,c⟵Rℤp and a one-way hash function H:0,1∗⟶ℤp. For each i∈n, TA chooses random exponents ai,t∈ℤpt∈ni and computes Ai,t,1=g1ai,t,Ai,t,2=g1cai,tt∈ni. Next, TA sets MK=a,b,c,ai,tt∈nii∈n as his master key and publishes the public parameter PK=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,g1c,g1bc,H,Ai,t,1,Ai,t,2t∈nii∈n. Finally, TA creates two empty identity tables T1 and T2.KeyGenMK,PK,id,L: DU submits his identity id and attributes set L=vi,tii∈n to TA in order to apply for the user private key. TA first picks xid,yid,β⟵Rℤp and sets K=xid,K0=g2a/bc+yidg2β/b,K1=yid. For each i∈n, TA picks λi⟵Rℤp and computes Ki,1=g2β+λiai,ti,Ki,2=g2λi. Then, TA sets SKid,L=K,K0,K1,Ki,1,Ki,2i∈n as DU private key and sends it to the DU with identity id. Next, TA picks α⟵Rℤp, sets SKo=α as DO private key, and sends it to DO. After that, TA computes Cid=eg1,g2−aαxid, stores id,Cid in the registered identity table T1, and sends T1 to CS for search permission revocation. Finally, TA adds id,yid in the identity table T2 and secretly stores T2 for user tracing.Encω,P,SKo,PK: to encrypt a keyword under an access policy P=Pii∈n, DO computes C=eg1,g2aα,C0=g1bα/Hω,C1=g1bcα/Hω. For each i∈n, DO chooses αi⟵Rℤp such that ∑i∈nαi=α, computes Ci,1=g1αi,Ci,2=g1cαi, and sets Ci,t,1 for each t∈ni as follows: if vi,t∈Pi, it sets Ci,t,1=Ai,t,1αi,Ci,t,2=Ai,t,2αi; otherwise, it sets Ci,t,1 and Ci,t,2 as two random elements in G1. Finally, DO uploads the ciphertext CT=C,C0,C1,Ci,1,Ci,2,Ci,t,1,Ci,t,2t∈nii∈n into the cloud.TokenGenSKid,L,PK,ω′: to generate a search token for a keyword ω′∈0,1∗, DU picks s⟵Rℤp and computes tok0=K0Hω′s,tok=K+s,tok1=K1. For each i∈n, DU computes Ti,1=Ki,1s,Ti,2=Ki,2s. Finally, DU sends the search token TKid,L=tok0,tok,tok1,Ti,1,Ti,2i∈n to CS.SearchTKid,L,CT,T1: when CS receives the search token TKid,L=tok0,tok,tok1,Ti,1,Ti,2i∈n from the DU with identity id, it first searches the entry id,Cid in the table T1. If no such entry exists, CS returns 0 and aborts; otherwise, CS obtains Cid from T1 and runs the following search algorithm. If Algorithm. If L=vi,tii∈n, it computes E=∏i∈neCi,1tok1Ci,2,Ti,1/eCi,ti,1tok1Ci,ti,2,Ti,2=eg1,g2αβsyid+c. Finally, CS returns 1 if ECtokCid=eC0tok1C1,tok0 and 0 otherwise.TraceSKid,L,PK,T2: if the private key is not in the form of SKid,L=K,K0,K1,Ki,1,Ki,2i∈n, TA returns ⊤ and aborts; otherwise, TA runs the following key sanity check algorithm. K,K1∈ℤp,K0,Ki,1,Ki,2∈G2,∃i∈n,s.t.(1)eg1bcg1bK1,K0eAi,ti,1K1Ai,ti,2,Ki,2=eg1,g2aeg1cg1K1,Ki,1.If the private keySKid,L does not pass the above check, TA returns ⊤ and aborts; otherwise, TA searches the entry id,K1 in table T2 and returns the corresponding id.Revokeid,T1: to revoke the search permission of the malicious user with identity id, TA updates table T1 by deleting the entry id,Cid and sends new table T1 to CS.


## 4.2. Correctness Proof

We now prove the correctness of our TR-HABKS scheme.If Scheme. If the user attributes L=vi,tii∈n satisfy the access policy P=Pii∈n, we have vi,ti∈Pi and Ci,ti,1=Ai,ti,1αi,Ci,ti,2=Ai,ti,2αi for each i∈n. Then,(2)∏i∈neCi,1tok1Ci,2,Ti,1eCi,ti,1tok1Ci,ti,2,Ti,2=∏i∈neg1αiyidg1cαi,Ki,1seAi,ti,1αiyidAi,ti,2αi,Ki,2s=∏i∈neg1yid+c,g2β+λiai,tisαieg1yid+cai,ti,g2λisαi=∏i∈neg1yid+c,g2βsαieg1yid+c,g2λiai,tisαieg1yid+cai,ti,g2λisαi=∏i∈neg1,g2βsyid+cαi=eg1,g2βsyid+c∑i∈nαi=eg1,g2αβsyid+c.If the userid is in table T1, then CS can obtain the corresponding Cid=eg1,g2−aαxid. Therefore,(3)ECtokCid=eg1,g2αβsyid+ceg1,g2aαxid+seg1,g2−aαxid=eg1,g2αβsyid+ceg1,g2aαs.In this case, ifω=ω′, we have(4)eC0tok1C1,tok0=eg1bαyid/Hωg1bcα/Hω,K0Hω′s=eg1bαc+yid,g2a/bc+yidg2β/bs=eg1bαc+yid,g2a/bc+yidseg1bαc+yid,g2β/bs=eg1,g2aαseg1,g2αβsyid+c=ECtokCid.


## 4.3. Proof of Selective Security

In this part, we prove the confidentiality of keywords and access policies in our scheme by a security reduction to the QLSZ scheme [18]. More specifically, if there are any attacks in our TR-HABKS scheme, then we can use these attacks to break the QLSZ scheme in the generic bilinear group model [18, 45]. Followed by the definition in [45], we consider three random encodings φ1,φ2,φT:Fp⟶0,1m, where Fp is an additive group and m>3logp. For i=1,2,T, let Gi=φix:x∈Fp. Therefore, there are three oracles to compute the group action on G1,G2,GT and an oracle to compute the bilinear map e. We refer to G1 as a generic bilinear group. In addition, our TR-HABKS scheme only allows DO to generate ciphertext by his private key, so the adversary cannot successfully carry out the keyword guessing attack.Theorem 1.
If the QLSZ scheme is selectively secure in the generic bilinear group model, then our TR-HABKS scheme is selectively secure.Proof.
Suppose that there exists a PPT adversaryA that can break our TR-HABKS scheme with advantage ε in the selective security model. We will build a simulator ℬ that can break the QLSZ scheme with advantage ε. Let C be the challenger corresponding to ℬ in the security game of QLSZ scheme. For more information about the QLSZ scheme and its security, please refer to [18].Inti: simulatorℬ receives two challenge access policies P0 and P1 from adversary A and then sends these policies to challenger C.Setup:C sends the QLSZ public parameter PK¯=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,H,Ai,tt∈nii∈n to ℬ. Then, ℬ picks c⟵Rℤp, sets Ai,t,1=Ai,t,Ai,t,2=Ai,tct∈ni, and sends the public parameter PK=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,g1c,g1bc,H,Ai,t,1,Ai,t,2t∈nii∈n to A.Query Phase1:ℬ answers the adversary’s private key and search token queries in our TR-HABKS scheme as follows:(1)
Private key queryOKeyGenid,L: in order to create the user private key for a pair id,L requested by A, ℬ first sends id,L to C to query the corresponding user private key in QLSZ scheme. When ℬ receives the QLSZ private key SK=xid,K0′=g2a+β′/b,Ki,1′=g2β′+λi′ai,ti,Ki,2′=g2λi′i∈n, it picks yid⟵Rℤp, implicitly sets β=β′/yid+c, λi=λi′/yid+c, and sets K=xid,K1=yid. Then, it computes K0=K0′1/yid+c=g2a/bc+yidg2β′/bc+yid=g2a/bc+yidg2β/b,Ki,1=Ki,1′1/yid+c=g2β′/yid+c+λi′/yid+cai,ti=g2β+λiai,ti,Ki,2=Ki,2′1/yid+c=g2λi′/yid+c=g2λi. Finally, ℬ sets the user private key SKid,L=K,K0,K1,Ki,1,Ki,2i∈n and sends it to A.(2)
Search token queryOTokenGenid,L,w: in order to create the search token for a tuple id,L,w requested by A, ℬ first runs OKeyGenid,L to obtain SKid,L=K,K0,K1,Ki,1,Ki,2i∈n. Then, ℬ picks s⟵Rℤp and computes tok0=K0Hω′s,tok=K+s,tok1=K1, Ti,1=Ki,1s,Ti,2=Ki,2s. Finally, ℬ sets the search token TKid,L=tok0,tok,tok1,Ti,1,Ti,2i∈n and sends it to A.Challenge:A submits two keywords ω0 and ω1 to ℬ, where the pair ω0,ω1 satisfies the following constraint. If the adversary has queried the private key or search token for the attributes set L that satisfies both access policies P0 and P1, then we require that ω0=ω1. Next, ℬ sends ω0 and ω1 to C to obtain the QLSZ challenge ciphertext CT′=C′,C0′,Ci,1′,Ci,t,2′t∈nii∈n. Finally, ℬ sets C=C′,C0=C0′,C1=C0c,Ci,1=Ci,1′,Ci,2=Ci,1c,Ci,t,1=Ci,t,2′,Ci,t,2=Ci,t,1c and returns the challenge ciphertext CT∗=C,C0,C1,Ci,1,Ci,2,Ci,t,1,Ci,t,2t∈nii∈n to A.Query Phase2: same as Phase 1.Guess: finally,A outputs a guess γ′∈0,1, and then ℬ sends γ′ to C.
According to the above simulation, ifA has advantage ε in the selective security game against our scheme, then ℬ can use A to break the QLSZ scheme with the same advantage ε.


## 4.4. Proof of Traceability

In this part, we prove that our TR-HABKS scheme is fully traceable based on the BB basic signature scheme, which has been proved to be existentially unforgeable under a weak chosen message attack in [44]. In order to prove the traceability, we assume that there exists a PPT adversary A who can win the traceability game, and then we construct a simulator ℬ that can break the BB basic signature scheme under a weak chosen message attack. Let C denote the BB challenger corresponding to ℬ in the signature security game. For more information about the BB basic signature scheme and its security, please refer to [44].Theorem 2.
If the BB basic signature scheme is existentially unforgeable under a weak chosen message attack, then our TR-HABKS scheme is fully traceable.Proof.
Before the game starts, challengerC sets a bilinear group p,G1,G2,GT,g1,g2,e. G1,G2, and GT are the cyclic groups of prime order p, g1 is a generator of G1, g2 is a generator of G2, and e:G1×G2⟶GT is a bilinear map.


### 4.4.1. Setup

Simulatorℬ first chooses random values yj∈ℤpj∈qs and makes signature queries by submitting the values yj∈ℤpj∈qs to challenger C. Then, C sends the BB public parameter PK¯=p,G1,G2,GT,e,g1,g2,g1c and the corresponding signatures yj,σj=g21/yj+cj∈qs to ℬ. For each i∈n, ℬ chooses random exponents ai,t∈ℤpt∈ni and computes Ai,t,1=g1ai,t,Ai,t,2=g1cai,tt∈ni. Next, ℬ picks a,b⟵Rℤp and a one-way hash function H:0,1∗⟶ℤp and computes eg1,g2a,g1b,g1c,g1bc. Finally, ℬ sends the public parameter PK=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,g1c,g1bc,H,Ai,t,1,Ai,t,2t∈nii∈n to adversary A and initializes an empty identity table T2.


### 4.4.2. Key query

WhenA makes user private key query for idj,Lj, ℬ first picks xj,β⟵Rℤp and sets Kj=xj,K0,j=σja/bg2β/b=g2a/bc+yjg2β/b,K1,j=yj. For each i∈n, ℬ picks λi,j⟵Rℤp and computes Ki,1,j=g2β+λi,jai,ti,Ki,2,j=g2λi,j. Then, ℬ sets SKidj,Lj=Kj,K0,j,K1,j,Ki,1,j,Ki,2,ji∈n as the corresponding private key and returns it to A. Finally, ℬ adds idj,yj to T2.


### 4.4.3. Key forgery

AdversaryA outputs a user private key SK∗.IfA wins the above traceability game, then TraceSK∗,PK,T2∉id1,id2,…,idqs,⊤. Hence, the key SK∗=K,K0,K1,Ki,1,Ki,2,Ki,3i∈n satisfies the following conditions: K1∉y1,y2,…,yqs, K,K1∈ℤp,K0,Ki,1,Ki,2∈G2, and ∃i∈n,s.t.eg1bcg1bK1,K0⋅eAi,ti,1K1Ai,ti,2,Ki,2=eg1,g2aeg1cg1K1,Ki,1.Assuming thatKi,1=g2βi,Ki,2=g2λi, where βi∈ℤp and λi∈ℤp are unknown, we have eg1bK1+c,K0eg1K1+cai,ti,g2λi=eg1,g2aeg1K1+c,g2βi, and then eg1,K0K1+c=eg1,g2a+K1+cβi−λiK1+cai,ti. Therefore, K0b=g2a+K1+cβi−λiK1+cai,ti/K1+c=g2a/K1+cg2βig2−λiai,ti=g2a/K1+cKi,1Ki,2−ai,ti.Finally,ℬ computes σ=K0bKi,2ai,ti/Ki,11/a=g21/K1+c and then obtains a valid signature σ on message K1, where K1∉y1,y2,…,yqs. Hence, if A has advantage ε in the traceability game, then ℬ can forge a valid BB basic signature scheme with advantage ε under a weak chosen message attack.


## 4.4.1. Setup

Simulatorℬ first chooses random values yj∈ℤpj∈qs and makes signature queries by submitting the values yj∈ℤpj∈qs to challenger C. Then, C sends the BB public parameter PK¯=p,G1,G2,GT,e,g1,g2,g1c and the corresponding signatures yj,σj=g21/yj+cj∈qs to ℬ. For each i∈n, ℬ chooses random exponents ai,t∈ℤpt∈ni and computes Ai,t,1=g1ai,t,Ai,t,2=g1cai,tt∈ni. Next, ℬ picks a,b⟵Rℤp and a one-way hash function H:0,1∗⟶ℤp and computes eg1,g2a,g1b,g1c,g1bc. Finally, ℬ sends the public parameter PK=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,g1c,g1bc,H,Ai,t,1,Ai,t,2t∈nii∈n to adversary A and initializes an empty identity table T2.


## 4.4.2. Key query

WhenA makes user private key query for idj,Lj, ℬ first picks xj,β⟵Rℤp and sets Kj=xj,K0,j=σja/bg2β/b=g2a/bc+yjg2β/b,K1,j=yj. For each i∈n, ℬ picks λi,j⟵Rℤp and computes Ki,1,j=g2β+λi,jai,ti,Ki,2,j=g2λi,j. Then, ℬ sets SKidj,Lj=Kj,K0,j,K1,j,Ki,1,j,Ki,2,ji∈n as the corresponding private key and returns it to A. Finally, ℬ adds idj,yj to T2.


## 4.4.3. Key forgery

AdversaryA outputs a user private key SK∗.IfA wins the above traceability game, then TraceSK∗,PK,T2∉id1,id2,…,idqs,⊤. Hence, the key SK∗=K,K0,K1,Ki,1,Ki,2,Ki,3i∈n satisfies the following conditions: K1∉y1,y2,…,yqs, K,K1∈ℤp,K0,Ki,1,Ki,2∈G2, and ∃i∈n,s.t.eg1bcg1bK1,K0⋅eAi,ti,1K1Ai,ti,2,Ki,2=eg1,g2aeg1cg1K1,Ki,1.Assuming thatKi,1=g2βi,Ki,2=g2λi, where βi∈ℤp and λi∈ℤp are unknown, we have eg1bK1+c,K0eg1K1+cai,ti,g2λi=eg1,g2aeg1K1+c,g2βi, and then eg1,K0K1+c=eg1,g2a+K1+cβi−λiK1+cai,ti. Therefore, K0b=g2a+K1+cβi−λiK1+cai,ti/K1+c=g2a/K1+cg2βig2−λiai,ti=g2a/K1+cKi,1Ki,2−ai,ti.Finally,ℬ computes σ=K0bKi,2ai,ti/Ki,11/a=g21/K1+c and then obtains a valid signature σ on message K1, where K1∉y1,y2,…,yqs. Hence, if A has advantage ε in the traceability game, then ℬ can forge a valid BB basic signature scheme with advantage ε under a weak chosen message attack.


## 5. Our eTR-HABKS System

In this section, we describe our enhanced TR-HABKS system based on our TR-HABKS scheme inSection 4. Different from the TR-HABKS scheme, the tracing algorithm in this system is public traceable and does not require any identity table. In addition, the efficiency comparison shows that the storage overhead of the eTR-HABKS system is much smaller than that of the TR-HABKS scheme.


### 5.1. Concrete System

#### 5.1.1. System Initialization

In this phase, TA generates the system parameter, the master key for himself, and an identity table for revocation.TA first runsGλ to obtain p,G1,G2,GT,g1,g2,e. For each i∈n, TA chooses random exponents ai,t∈ℤpt∈ni and computes Ai,t=g1ai,tt∈ni. Then, TA picks a,b,c,d⟵Rℤp and a one-way hash function H:0,1∗⟶ℤp. Next, TA sets MK=a,b,c,d,ai,tt∈nii∈n as his master key and publishes the public parameter PK=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,g1c,g1d,g1bc,g1bd,H,Ai,tt∈nii∈n. Finally, TA creates an empty identity table T1.


#### 5.1.2. User Registration

In this phase, TA uses his master key to generate the private keys for the registered DUs and DO.When DU wants to join the system, he submits his identityid∈ℤp and attributes set L=vi,tii∈n to TA to apply for his private key. TA first picks xid,r,β⟵Rℤp and sets K=xid,K0=g2a/bc+id+drg2β/b,K1=id,K2=r. For each i∈n, TA picks λi⟵Rℤp and computes Ki,1=g2β+λiai,ti,Ki,2=g2λi,Ki,3=g2c+drλi. TA sets SKid,L=K,K0,K1,K2,Ki,1,Ki,2,Ki,3i∈n as the user private key and sends it to the corresponding DU. Then, TA picks α⟵Rℤp and sets SKo=α as the data owner private key and sends it to DO. Finally, TA computes Cid=eg1,g2−aαxid, stores id,Cid in the identity table T1, and sends T1 to CS.


#### 5.1.3. Secure Index Generation

In this phase, DO uses his private key to generate a secure index for each file and outsources all the files and indexes in the cloud.When DO wants to share a file with the specific data users, he extracts a keywordω∈0,1∗ from the file and encrypts the keyword ω under an access policy P=Pii∈n. DO first computes C=eg1,g2aα,C0=g1bα/Hω,C1=g1bcα/Hω,C2=g1bdα/Hω. For each i∈n, DO chooses αi⟵Rℤp such that ∑i∈nαi=α, computes Ci,1=g1αi,Ci,2=g1cαi,Ci,3=g1dαi, and sets Ci,t,2 for each t∈ni as follows: if vi,t∈Pi, it sets Ci,t,2=Ai,tαi; otherwise, it sets Ci,t,2 as a random element in G1. Finally, DO stores the encrypted index CT=C,C0,C1,C2,Ci,1,Ci,2,Ci,3,Ci,t,2t∈nii∈n in the cloud.


#### 5.1.4. Search Token Generation

In this phase, DU generates a search token for a keywordω′∈0,1∗, and sends the search token to CS for the data retrieval request.DU first pickss⟵Rℤp, computes tok0=K0Hω′s,tok=K+s,tok1=K1,tok2=K2. For each i∈n, DU computes Ti,1=Ki,1s,Ti,2=Ki,2s,Ti,3=Ki,3s. Finally, DU sets the search token TKid,L=tok0,tok,tok1,tok2,Ti,1,Ti,2,Ti,3i∈n.


#### 5.1.5. Data Retrieval

In this phase, CS uses the token to search the data in the cloud and responds the search results to DU.When CS receives the retrieval request and the search tokenTKid,L=tok0,tok,tok1,tok2,Ti,1,Ti,2,Ti,3i∈n from DU, it first searches the entry id,Cid in T1. If no such entry exists, CS returns error symbol ⊥ and aborts; otherwise, CS obtains Cid from T1 and then runs the following search algorithm. If Algorithm. If L=vi,tii∈n, it computes E=∏i∈neCi,1tok1Ci,2Ci,3tok2,Ti,1/eCi,ti,2,Ti,2tok1Ti,3=eg1,g2αβsc+id+dr. Finally, CS returns 1 if ECtokCid=eC0tok1C1C2tok2,tok0 and 0 otherwise.


#### 5.1.6. User Tracing

In this phase, TA traces the malicious user who sales his private keySKid,L on the Internet and outputs the malicious user’s identity.TA first checks whetherSKid,L is a well-formed key. If the private key is not in the form of SKid,L=K,K0,K1,K2Ki,1,Ki,2,Ki,3i∈n, it returns ⊤ and aborts; otherwise, it runs the following key sanity check algorithm. K,K1,K2∈ℤp,K0,Ki,1,Ki,2,Ki,3∈G2,∃i∈n,s.t.(5)eg1cg1dK2,Ki,2=eg1,Ki,3,eg1bcg1bK1g1bdK2,K0eAi,ti,Ki,2K1Ki,3=eg1,g2aeg1cg1K1g1dK2,Ki,1.IfSKid,L does not pass the above check, it returns ⊤ and aborts; otherwise, it returns K1 as the corresponding user identity.


#### 5.1.7. User Revocation

In this phase, TA revokes the search permissions of the malicious users. When TA obtains the malicious user identityid, he updates table T1 by deleting the entry id,Cid and sends the new table T1 to CS.


### 5.2. Correctness Proof

The correctness of our TR-HABKS scheme is proved as follows. If the user attributesL=vi,tii∈n satisfy the access policy P=Pii∈n, we have vi,ti∈Pi and Ci,ti,2=Ai,tiαi for each i∈n. Then,(6)∏i∈neCi,1tok1Ci,2Ci,3tok2,Ti,1eCi,ti,2,Ti,2tok1Ti,3=∏i∈neg1id⋅αig1cαig1d⋅rαi,Ki,1seAi,tiαi,Ki,2id⋅sKi,3s=∏i∈neg1id+c+dr,g2β+λiai,tisαieg1ai,ti,g2λiid+c+drsαi=∏i∈neg1id+c+dr,g2βsαieg1id+c+dr,g2λiai,tisαieg1ai,ti,g2λiid+c+drsαi=∏i∈neg1,g2βsid+c+drαi=eg1,g2βsid+c+dr∑i∈nαi=eg1,g2αβsid+c+dr.If the userid is in the table T1, then CS has the corresponding Cid=eg1,g2−aαxid. Therefore,(7)ECtokCid=eg1,g2αβsid+c+dreg1,g2aαxid+seg1,g2−aαxid=eg1,g2αβsid+c+dreg1,g2aαs.In this case, ifω=ω′, we have(8)eC0tok1C1C2tok2,tok0=eg1id⋅bα/Hωg1bcα/Hωg1r⋅bdα/Hω,K0Hω′s=eg1bαid+c+dr,g2a/bid+c+drg2β/bs=eg1bαid+c+dr,g2a/bid+c+drseg1bαid+c+dr,g2β/bs=eg1,g2aαseg1,g2αβsid+c+dr=ECtokCid.The security proofs of our eTR-HABKS scheme are almost the same as that inSection 4, so we omit the details here.


### 5.3. Comparison

Table2 compares the storage costs of our schemes with that of QLSZ scheme [18]. The length of the public parameter/ciphertext of all three schemes increases linearly with ∑i∈nni, where n is the total number of attributes in the system and ni is the number of possible values for attribute index i. Compared with QLSZ scheme, the public key and ciphertext size of our TR-HABKS scheme have almost doubled, but the public key and ciphertext size of our eTR-HABKS scheme are only increased by 4 and 2+n elements, respectively. The user private key/token size of all schemes grows linearly with the total number of attributes, and the user private key/token of the eTR-HABKS scheme is about 1.5 times as long as that of other schemes. Note that n is far less than ∑i∈nni, so the system storage overhead of the eTR-HABKS scheme is much less than that of the TR-HABKS scheme, although the user storage overhead of the eTR-HABKS scheme is slightly greater. In addition, the eTR-HABKS scheme only needs to maintain an identity table T1 for revocation but does not require any identity table for tracing, which makes our eTR-HABKS scheme more practical. Figure 2 illustrates the system storage overhead for tracing (including the public parameter and the storage for tracing) in our TR-HABKS and eTR-HABKS schemes. We set the group element size to 160 bits and the random number and identity size to 1024 bits, and ∑i∈nni=100. From Figure 2, it is easy to see that the system storage overhead for tracing in our eTR-HABKS scheme is constant and significantly smaller than that grows linearly with the number of users in TR-HABKS scheme.Table 2
Storage cost comparison.
Scheme[18]TR-HABKSeTR-HABKSPublic parameter size4+∑i∈nni6+2∑i∈nni8+∑i∈nniUser private key size2+2n3+2n4+3nCiphertext size2+n+∑i∈nni3+2n+2∑i∈nni4+3n+∑i∈nniToken size2+2n3+2n4+3nThe storage for tracing—T20The storage for revocation—T1T1Figure 2
System storage overhead for tracing.Table3 gives a computation cost comparison that ignores nondominant operations in the schemes. E1, E2, and ET denote an exponentiation operation in groups G1, G2, and GT, respectively. P is a bilinear pairing operation and PiPi≤ni is the number of attribute values in Pi. Let “Trace (max)” and “Trace (min)” denote the maximum and minimum computation cost for successful tracing, respectively. From Table 3, we can see that the computation cost in the setup and encryption algorithms of the eTR-HABKS scheme is almost the same as that of QLSZ scheme, but it is obviously smaller than that of the TR-HABKS scheme. All three schemes have the same level of computation overhead in key generation and token generation algorithms. Compared with QLSZ scheme, our TR-HABKS and eTR-HABKS schemes do not add any computation overhead to achieve user revocation but add more computation overhead to realize user accountability. However, the increased computation burden has little effect on the performance of our eTR-HABKS system, because the search and tracing algorithms can be executed by the cloud with powerful computing capability.Table 3
Computation cost comparison.
Scheme[18]TR-HABKSeTR-HABKSSetup1+∑i∈nniE1+ET3+2∑i∈nniE1+ET5+∑i∈nniE1+ETKeyGen1+2nE2+ET1+2nE2+ET1+3nE2+ETEnc1+n+∑i∈nPiE1+ET2+2n+2∑i∈nPiE1+ET3+3n+∑i∈nPiE1+ETTokenGen1+2nE21+2nE21+3nE2Search1+2nP+E11+2nP+2+2nE11+2nP+3+2nE1+nE2Trace (max)—1+2nP+2+nE11+4nP+4E1+nE2Trace (min)—3P+3E15P+4E1+E2Revoke—00


## 5.1. Concrete System

### 5.1.1. System Initialization

In this phase, TA generates the system parameter, the master key for himself, and an identity table for revocation.TA first runsGλ to obtain p,G1,G2,GT,g1,g2,e. For each i∈n, TA chooses random exponents ai,t∈ℤpt∈ni and computes Ai,t=g1ai,tt∈ni. Then, TA picks a,b,c,d⟵Rℤp and a one-way hash function H:0,1∗⟶ℤp. Next, TA sets MK=a,b,c,d,ai,tt∈nii∈n as his master key and publishes the public parameter PK=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,g1c,g1d,g1bc,g1bd,H,Ai,tt∈nii∈n. Finally, TA creates an empty identity table T1.


### 5.1.2. User Registration

In this phase, TA uses his master key to generate the private keys for the registered DUs and DO.When DU wants to join the system, he submits his identityid∈ℤp and attributes set L=vi,tii∈n to TA to apply for his private key. TA first picks xid,r,β⟵Rℤp and sets K=xid,K0=g2a/bc+id+drg2β/b,K1=id,K2=r. For each i∈n, TA picks λi⟵Rℤp and computes Ki,1=g2β+λiai,ti,Ki,2=g2λi,Ki,3=g2c+drλi. TA sets SKid,L=K,K0,K1,K2,Ki,1,Ki,2,Ki,3i∈n as the user private key and sends it to the corresponding DU. Then, TA picks α⟵Rℤp and sets SKo=α as the data owner private key and sends it to DO. Finally, TA computes Cid=eg1,g2−aαxid, stores id,Cid in the identity table T1, and sends T1 to CS.


### 5.1.3. Secure Index Generation

In this phase, DO uses his private key to generate a secure index for each file and outsources all the files and indexes in the cloud.When DO wants to share a file with the specific data users, he extracts a keywordω∈0,1∗ from the file and encrypts the keyword ω under an access policy P=Pii∈n. DO first computes C=eg1,g2aα,C0=g1bα/Hω,C1=g1bcα/Hω,C2=g1bdα/Hω. For each i∈n, DO chooses αi⟵Rℤp such that ∑i∈nαi=α, computes Ci,1=g1αi,Ci,2=g1cαi,Ci,3=g1dαi, and sets Ci,t,2 for each t∈ni as follows: if vi,t∈Pi, it sets Ci,t,2=Ai,tαi; otherwise, it sets Ci,t,2 as a random element in G1. Finally, DO stores the encrypted index CT=C,C0,C1,C2,Ci,1,Ci,2,Ci,3,Ci,t,2t∈nii∈n in the cloud.


### 5.1.4. Search Token Generation

In this phase, DU generates a search token for a keywordω′∈0,1∗, and sends the search token to CS for the data retrieval request.DU first pickss⟵Rℤp, computes tok0=K0Hω′s,tok=K+s,tok1=K1,tok2=K2. For each i∈n, DU computes Ti,1=Ki,1s,Ti,2=Ki,2s,Ti,3=Ki,3s. Finally, DU sets the search token TKid,L=tok0,tok,tok1,tok2,Ti,1,Ti,2,Ti,3i∈n.


### 5.1.5. Data Retrieval

In this phase, CS uses the token to search the data in the cloud and responds the search results to DU.When CS receives the retrieval request and the search tokenTKid,L=tok0,tok,tok1,tok2,Ti,1,Ti,2,Ti,3i∈n from DU, it first searches the entry id,Cid in T1. If no such entry exists, CS returns error symbol ⊥ and aborts; otherwise, CS obtains Cid from T1 and then runs the following search algorithm. If Algorithm. If L=vi,tii∈n, it computes E=∏i∈neCi,1tok1Ci,2Ci,3tok2,Ti,1/eCi,ti,2,Ti,2tok1Ti,3=eg1,g2αβsc+id+dr. Finally, CS returns 1 if ECtokCid=eC0tok1C1C2tok2,tok0 and 0 otherwise.


### 5.1.6. User Tracing

In this phase, TA traces the malicious user who sales his private keySKid,L on the Internet and outputs the malicious user’s identity.TA first checks whetherSKid,L is a well-formed key. If the private key is not in the form of SKid,L=K,K0,K1,K2Ki,1,Ki,2,Ki,3i∈n, it returns ⊤ and aborts; otherwise, it runs the following key sanity check algorithm. K,K1,K2∈ℤp,K0,Ki,1,Ki,2,Ki,3∈G2,∃i∈n,s.t.(5)eg1cg1dK2,Ki,2=eg1,Ki,3,eg1bcg1bK1g1bdK2,K0eAi,ti,Ki,2K1Ki,3=eg1,g2aeg1cg1K1g1dK2,Ki,1.IfSKid,L does not pass the above check, it returns ⊤ and aborts; otherwise, it returns K1 as the corresponding user identity.


### 5.1.7. User Revocation

In this phase, TA revokes the search permissions of the malicious users. When TA obtains the malicious user identityid, he updates table T1 by deleting the entry id,Cid and sends the new table T1 to CS.


## 5.1.1. System Initialization

In this phase, TA generates the system parameter, the master key for himself, and an identity table for revocation.TA first runsGλ to obtain p,G1,G2,GT,g1,g2,e. For each i∈n, TA chooses random exponents ai,t∈ℤpt∈ni and computes Ai,t=g1ai,tt∈ni. Then, TA picks a,b,c,d⟵Rℤp and a one-way hash function H:0,1∗⟶ℤp. Next, TA sets MK=a,b,c,d,ai,tt∈nii∈n as his master key and publishes the public parameter PK=p,G1,G2,GT,g1,g2,e,eg1,g2a,g1b,g1c,g1d,g1bc,g1bd,H,Ai,tt∈nii∈n. Finally, TA creates an empty identity table T1.


## 5.1.2. User Registration

In this phase, TA uses his master key to generate the private keys for the registered DUs and DO.When DU wants to join the system, he submits his identityid∈ℤp and attributes set L=vi,tii∈n to TA to apply for his private key. TA first picks xid,r,β⟵Rℤp and sets K=xid,K0=g2a/bc+id+drg2β/b,K1=id,K2=r. For each i∈n, TA picks λi⟵Rℤp and computes Ki,1=g2β+λiai,ti,Ki,2=g2λi,Ki,3=g2c+drλi. TA sets SKid,L=K,K0,K1,K2,Ki,1,Ki,2,Ki,3i∈n as the user private key and sends it to the corresponding DU. Then, TA picks α⟵Rℤp and sets SKo=α as the data owner private key and sends it to DO. Finally, TA computes Cid=eg1,g2−aαxid, stores id,Cid in the identity table T1, and sends T1 to CS.


## 5.1.3. Secure Index Generation

In this phase, DO uses his private key to generate a secure index for each file and outsources all the files and indexes in the cloud.When DO wants to share a file with the specific data users, he extracts a keywordω∈0,1∗ from the file and encrypts the keyword ω under an access policy P=Pii∈n. DO first computes C=eg1,g2aα,C0=g1bα/Hω,C1=g1bcα/Hω,C2=g1bdα/Hω. For each i∈n, DO chooses αi⟵Rℤp such that ∑i∈nαi=α, computes Ci,1=g1αi,Ci,2=g1cαi,Ci,3=g1dαi, and sets Ci,t,2 for each t∈ni as follows: if vi,t∈Pi, it sets Ci,t,2=Ai,tαi; otherwise, it sets Ci,t,2 as a random element in G1. Finally, DO stores the encrypted index CT=C,C0,C1,C2,Ci,1,Ci,2,Ci,3,Ci,t,2t∈nii∈n in the cloud.


## 5.1.4. Search Token Generation

In this phase, DU generates a search token for a keywordω′∈0,1∗, and sends the search token to CS for the data retrieval request.DU first pickss⟵Rℤp, computes tok0=K0Hω′s,tok=K+s,tok1=K1,tok2=K2. For each i∈n, DU computes Ti,1=Ki,1s,Ti,2=Ki,2s,Ti,3=Ki,3s. Finally, DU sets the search token TKid,L=tok0,tok,tok1,tok2,Ti,1,Ti,2,Ti,3i∈n.


## 5.1.5. Data Retrieval

In this phase, CS uses the token to search the data in the cloud and responds the search results to DU.When CS receives the retrieval request and the search tokenTKid,L=tok0,tok,tok1,tok2,Ti,1,Ti,2,Ti,3i∈n from DU, it first searches the entry id,Cid in T1. If no such entry exists, CS returns error symbol ⊥ and aborts; otherwise, CS obtains Cid from T1 and then runs the following search algorithm. If Algorithm. If L=vi,tii∈n, it computes E=∏i∈neCi,1tok1Ci,2Ci,3tok2,Ti,1/eCi,ti,2,Ti,2tok1Ti,3=eg1,g2αβsc+id+dr. Finally, CS returns 1 if ECtokCid=eC0tok1C1C2tok2,tok0 and 0 otherwise.


## 5.1.6. User Tracing

In this phase, TA traces the malicious user who sales his private keySKid,L on the Internet and outputs the malicious user’s identity.TA first checks whetherSKid,L is a well-formed key. If the private key is not in the form of SKid,L=K,K0,K1,K2Ki,1,Ki,2,Ki,3i∈n, it returns ⊤ and aborts; otherwise, it runs the following key sanity check algorithm. K,K1,K2∈ℤp,K0,Ki,1,Ki,2,Ki,3∈G2,∃i∈n,s.t.(5)eg1cg1dK2,Ki,2=eg1,Ki,3,eg1bcg1bK1g1bdK2,K0eAi,ti,Ki,2K1Ki,3=eg1,g2aeg1cg1K1g1dK2,Ki,1.IfSKid,L does not pass the above check, it returns ⊤ and aborts; otherwise, it returns K1 as the corresponding user identity.


## 5.1.7. User Revocation

In this phase, TA revokes the search permissions of the malicious users. When TA obtains the malicious user identityid, he updates table T1 by deleting the entry id,Cid and sends the new table T1 to CS.


## 5.2. Correctness Proof

The correctness of our TR-HABKS scheme is proved as follows. If the user attributesL=vi,tii∈n satisfy the access policy P=Pii∈n, we have vi,ti∈Pi and Ci,ti,2=Ai,tiαi for each i∈n. Then,(6)∏i∈neCi,1tok1Ci,2Ci,3tok2,Ti,1eCi,ti,2,Ti,2tok1Ti,3=∏i∈neg1id⋅αig1cαig1d⋅rαi,Ki,1seAi,tiαi,Ki,2id⋅sKi,3s=∏i∈neg1id+c+dr,g2β+λiai,tisαieg1ai,ti,g2λiid+c+drsαi=∏i∈neg1id+c+dr,g2βsαieg1id+c+dr,g2λiai,tisαieg1ai,ti,g2λiid+c+drsαi=∏i∈neg1,g2βsid+c+drαi=eg1,g2βsid+c+dr∑i∈nαi=eg1,g2αβsid+c+dr.If the userid is in the table T1, then CS has the corresponding Cid=eg1,g2−aαxid. Therefore,(7)ECtokCid=eg1,g2αβsid+c+dreg1,g2aαxid+seg1,g2−aαxid=eg1,g2αβsid+c+dreg1,g2aαs.In this case, ifω=ω′, we have(8)eC0tok1C1C2tok2,tok0=eg1id⋅bα/Hωg1bcα/Hωg1r⋅bdα/Hω,K0Hω′s=eg1bαid+c+dr,g2a/bid+c+drg2β/bs=eg1bαid+c+dr,g2a/bid+c+drseg1bαid+c+dr,g2β/bs=eg1,g2aαseg1,g2αβsid+c+dr=ECtokCid.The security proofs of our eTR-HABKS scheme are almost the same as that inSection 4, so we omit the details here.


## 5.3. Comparison

Table2 compares the storage costs of our schemes with that of QLSZ scheme [18]. The length of the public parameter/ciphertext of all three schemes increases linearly with ∑i∈nni, where n is the total number of attributes in the system and ni is the number of possible values for attribute index i. Compared with QLSZ scheme, the public key and ciphertext size of our TR-HABKS scheme have almost doubled, but the public key and ciphertext size of our eTR-HABKS scheme are only increased by 4 and 2+n elements, respectively. The user private key/token size of all schemes grows linearly with the total number of attributes, and the user private key/token of the eTR-HABKS scheme is about 1.5 times as long as that of other schemes. Note that n is far less than ∑i∈nni, so the system storage overhead of the eTR-HABKS scheme is much less than that of the TR-HABKS scheme, although the user storage overhead of the eTR-HABKS scheme is slightly greater. In addition, the eTR-HABKS scheme only needs to maintain an identity table T1 for revocation but does not require any identity table for tracing, which makes our eTR-HABKS scheme more practical. Figure 2 illustrates the system storage overhead for tracing (including the public parameter and the storage for tracing) in our TR-HABKS and eTR-HABKS schemes. We set the group element size to 160 bits and the random number and identity size to 1024 bits, and ∑i∈nni=100. From Figure 2, it is easy to see that the system storage overhead for tracing in our eTR-HABKS scheme is constant and significantly smaller than that grows linearly with the number of users in TR-HABKS scheme.Table 2
Storage cost comparison.
Scheme[18]TR-HABKSeTR-HABKSPublic parameter size4+∑i∈nni6+2∑i∈nni8+∑i∈nniUser private key size2+2n3+2n4+3nCiphertext size2+n+∑i∈nni3+2n+2∑i∈nni4+3n+∑i∈nniToken size2+2n3+2n4+3nThe storage for tracing—T20The storage for revocation—T1T1Figure 2
System storage overhead for tracing.Table3 gives a computation cost comparison that ignores nondominant operations in the schemes. E1, E2, and ET denote an exponentiation operation in groups G1, G2, and GT, respectively. P is a bilinear pairing operation and PiPi≤ni is the number of attribute values in Pi. Let “Trace (max)” and “Trace (min)” denote the maximum and minimum computation cost for successful tracing, respectively. From Table 3, we can see that the computation cost in the setup and encryption algorithms of the eTR-HABKS scheme is almost the same as that of QLSZ scheme, but it is obviously smaller than that of the TR-HABKS scheme. All three schemes have the same level of computation overhead in key generation and token generation algorithms. Compared with QLSZ scheme, our TR-HABKS and eTR-HABKS schemes do not add any computation overhead to achieve user revocation but add more computation overhead to realize user accountability. However, the increased computation burden has little effect on the performance of our eTR-HABKS system, because the search and tracing algorithms can be executed by the cloud with powerful computing capability.Table 3
Computation cost comparison.
Scheme[18]TR-HABKSeTR-HABKSSetup1+∑i∈nniE1+ET3+2∑i∈nniE1+ET5+∑i∈nniE1+ETKeyGen1+2nE2+ET1+2nE2+ET1+3nE2+ETEnc1+n+∑i∈nPiE1+ET2+2n+2∑i∈nPiE1+ET3+3n+∑i∈nPiE1+ETTokenGen1+2nE21+2nE21+3nE2Search1+2nP+E11+2nP+2+2nE11+2nP+3+2nE1+nE2Trace (max)—1+2nP+2+nE11+4nP+4E1+nE2Trace (min)—3P+3E15P+4E1+E2Revoke—00


## 6. Conclusion

In this paper, we first presented a new privacy-preserving ABKS construction for cloud-assisted IoT and then proved that it is selectively secure and fully traceable in the generic bilinear group model. We also proposed another ABKS construction with public traceability and showed that it is more efficient than the first construction. In short, our two constructions not only reduce privacy leakage by hiding access policies but also prevent private key abuse by tracing and revoking malicious users. As our schemes are designed for just one-owner setting, we aim to construct a traceable and revocable ABKS scheme with policy protection in multiowner setting in the future.



---

*Source: 9929663-2021-05-30.xml*