# Attribute Set-Based Boolean Keyword Search over Encrypted Personal Health Records

Authors: Yu Lin; Lingling Xu; Wanhua Li; Zhiwei Sun
Journal: Security and Communication Networks
 (2021)

---

## Abstract

A personal health record (PHR) is an electronic application which enables patients to collect and share their health information. With the development of cloud computing, many PHR services have been outsourced to cloud servers. Cloud computing makes it easier for patients to manage their personal health records and makes it easier for doctors and researchers to share and access this information. However, due to the high sensitivity of PHR, a series of security protections are needed to protect them, such as encryption and access control. In this article, we propose an attribute set-based Boolean keyword search scheme, which can realize fine-grained access control and Boolean keyword search over encrypted PHR. Compared with the existing attribute-based searchable encryption, our solution can not only improve the flexibility in specifying access policies but also perform Boolean keyword search, which can meet the needs of large-scale PHR users. Furthermore, we simulate our scheme, and the experimental results show that our scheme is practical for PHR systems in cloud computing.


---

## Body

## 1. Introduction

In recent years, with the rapid development of cloud computing, it has been successfully deployed in a wide variety of real-world applications, such as the medical industry. A personal health record (PHR) is an electronic application through which patients can maintain and manage their health information in a private, secure, and confidential environment. The intention of PHR is to provide a complete and accurate summary of an individual’s medical history which is accessible online. PHR benefits in many aspects, including strengthening the connection between doctors, patients, medical researchers, and hospitals. Doctors and medical researchers can obtain patient’s information more conveniently by using PHR. At the same time, patients can better control their personal health information (PHI) since only people with necessary electronic credentials can get access to their PHR. However, PHR is under security threat such as information leakage, lack of access control, and untrusted cloud servers. A lot of security issues have happened in recent years, which have brought huge economic losses. Thus, it is very important to develop a method for protecting the security and privacy of PHR. The most common method is to encrypt the PHR before uploading them to the server. However, performing searches on encrypted PHR would be a challenge.Searchable encryption (SE) is a well-studied method that can deal with this issue. In SE, firstly, data owners encrypt their data and upload them to the cloud server. Then, each legitimate data user can generate a trapdoor using his secret key and interested keywords where the trapdoor enables data user to search over encrypted PHR. However, due to the high sensitivity, it is desired that each user can only query the authorized PHR. That is, fine-grained access control is needed for PHR. Thus, attribute-based keyword search has been implemented by many researchers [1–12]. In these schemes, data owners can encrypt their data with predefined access control policies. A trusted authority is responsible for managing all data users and distributing secret keys to them, where the secret key is generated according to the user’s attributes. Thus, when a data user searches over encrypted PHR stored in the server with his interested keywords, the server can judge whether his attributes satisfy the access policy.However, there are some limitations in existing schemes. Firstly, in the schemes [7–10], each user’s attributes are organized in a single set, which cannot support the compounded attributes. For example, consider a user who is a “Researcher” working in “College A” and serves as both “Director” of “Department of Medicine” and “Professor” of “Department of Chemistry,” and the above attributes are both valid and are likely to be used to describe him. A possible method is expressing above attributes as strings, like “Researcher_CollegeA_Director_Department OfM−edicine_Professor_Department Of Chemistry”. Unfortunately, it becomes challenging in satisfying policies which combine some of the singleton attributes. Secondly, in the schemes [10–12], data users are only allowed to search with a single keyword, which is not flexible enough. Although the scheme [7] supports recursive attribute set structure for more flexibility in specifying policies and the scheme [3] supports Boolean keyword search, none of the schemes support both of the two functionalities.


### 1.1. Our Contributions

In this paper, we present an attribute set-based Boolean keyword search (ASBBKS) scheme over encrypted PHR in cloud computing. In our scheme, each data user’s attributes are organized as recursive set structure, which enables more flexibility in user attribute organization and more efficiency in specifying policies than the existing ABKS schemes. Meanwhile, our scheme supports Boolean keyword search which is flexible in keyword expressivity. The ASBBKS model for encrypted PHR is shown in Figure1. The main contributions of our paper are described in detail as follows:(i)
In our scheme, each data user’s attributes can be organized as recursive set structure. That is, multiple values are assigned to an attribute in different sets. In the above example, the researcher’s attributes can be organized into a 2-depth recursive set structure as follows. For each role that a researcher has, a separate set of values {Department, Role} can be assigned.{Agency: College A, Role: Researcher,{Department: Medicine, Role: Director},{Department: Chemistry, Role: Professor}}.(ii)
All authorized users can perform Boolean keyword search which is a more flexible search mechanism. For example, the PHR users can query the PHR which contains the keywords “(Treatment time: Jun 2021∧ Doctor name: Mike) ∧ (Drug name: Aspirin ∨ Disease name: Neuralgia)” to the cloud server.(iii)
We present the theoretical performance analysis of the ASBBKS scheme for computation and communication costs. In addition, the simulated results show that it is practical for the PHR systems.Figure 1
Our scheme model.


### 1.2. Related Works

Searchable encryption (SE) was first proposed by Sont et al. [13] which enables users to implement keyword research over the encrypted data. There are two categories for existing SE schemes: symmetric searchable encryption (SSE) [13–17] and public key encryption with keyword search (PEKS) [18–21]. SSE enables a user to encrypt his data and implement the keyword search by using his secret key. In a PEKS scheme, data owners can authorize search ability to each user by encrypting data with the user’s public key. Thus, each user can perform searches over encrypted data with his private key. However, the above two types of SE have a vulnerability that they do not support access control on data users. It means that each legitimate user can query all of the encrypted data, which may cause security issues.To solve this problem, researchers have proposed SE schemes with access control such as attribute-based encryption with keyword search (ABKS) [22–26]. In such SE schemes, data owners can authorize search ability to data users whose attributes satisfy the access policy predefined by the data owner. There is a trusted authority in ABKS to generate public parameters. In addition, it also generates secret keys for data users. In [27], each user needs to submit his attribute structure and interested keywords to the trusted authority for generating trapdoors. Then, the data user can search over encrypted data with his trapdoors. However, it fails to preserve the privacy of interested keywords and they will be revealed to the trusted authority, which is not desired by the data user. Thus, Zheng et al. [28] proposed an improved SE scheme that makes use of an access tree to fulfill access control. In [28], each user sends an attribute set to the trusted authority for generating an attribute-related private key. The private key is used to generate trapdoors of interested keywords. Then, users can search over encrypted data with trapdoors without revealing interested keywords. However, in these schemes, user’s attributes are organized to a single set, which decreases the flexibility in specifying access policies.In [29], the researchers proposed attribute set-based encryption (ASBE). In ASBE, the user’s attributes are organized in the form of recursive set structure which enables the data owners to encrypt data with more flexible access policies than ABE. Based on this technique, Xu et al. [7] proposed attribute set-based keyword search (ASBKS). Their scheme has better flexibility in user attribute organization and more efficiency in specifying policies. However, it only supports single keyword query, which limits the performance of searching.To achieve multi-keyword search, Boolean keyword expression search was presented in [1]. In [1], keywords are divided into two parts: value and name, which are both organized in the form of an access tree structure. Inspired by this, we propose an ASBBKS scheme that can support Boolean keyword search, compounded attributes, and flexible search policies simultaneously.


### 1.3. Paper Organization

The rest of the paper is organized as follows. We introduce some preliminaries in Section2. In Section 3, the concrete construction of the ASBBKS scheme is presented and the formal security proof of the ASBBKS scheme is provided. In Section 4, we evaluate the performance of our ASBBKS scheme and conduct simulation experiments to demonstrate its efficiency and practicality. Finally, we conclude the paper in Section 5.


## 1.1. Our Contributions

In this paper, we present an attribute set-based Boolean keyword search (ASBBKS) scheme over encrypted PHR in cloud computing. In our scheme, each data user’s attributes are organized as recursive set structure, which enables more flexibility in user attribute organization and more efficiency in specifying policies than the existing ABKS schemes. Meanwhile, our scheme supports Boolean keyword search which is flexible in keyword expressivity. The ASBBKS model for encrypted PHR is shown in Figure1. The main contributions of our paper are described in detail as follows:(i)
In our scheme, each data user’s attributes can be organized as recursive set structure. That is, multiple values are assigned to an attribute in different sets. In the above example, the researcher’s attributes can be organized into a 2-depth recursive set structure as follows. For each role that a researcher has, a separate set of values {Department, Role} can be assigned.{Agency: College A, Role: Researcher,{Department: Medicine, Role: Director},{Department: Chemistry, Role: Professor}}.(ii)
All authorized users can perform Boolean keyword search which is a more flexible search mechanism. For example, the PHR users can query the PHR which contains the keywords “(Treatment time: Jun 2021∧ Doctor name: Mike) ∧ (Drug name: Aspirin ∨ Disease name: Neuralgia)” to the cloud server.(iii)
We present the theoretical performance analysis of the ASBBKS scheme for computation and communication costs. In addition, the simulated results show that it is practical for the PHR systems.Figure 1
Our scheme model.


## 1.2. Related Works

Searchable encryption (SE) was first proposed by Sont et al. [13] which enables users to implement keyword research over the encrypted data. There are two categories for existing SE schemes: symmetric searchable encryption (SSE) [13–17] and public key encryption with keyword search (PEKS) [18–21]. SSE enables a user to encrypt his data and implement the keyword search by using his secret key. In a PEKS scheme, data owners can authorize search ability to each user by encrypting data with the user’s public key. Thus, each user can perform searches over encrypted data with his private key. However, the above two types of SE have a vulnerability that they do not support access control on data users. It means that each legitimate user can query all of the encrypted data, which may cause security issues.To solve this problem, researchers have proposed SE schemes with access control such as attribute-based encryption with keyword search (ABKS) [22–26]. In such SE schemes, data owners can authorize search ability to data users whose attributes satisfy the access policy predefined by the data owner. There is a trusted authority in ABKS to generate public parameters. In addition, it also generates secret keys for data users. In [27], each user needs to submit his attribute structure and interested keywords to the trusted authority for generating trapdoors. Then, the data user can search over encrypted data with his trapdoors. However, it fails to preserve the privacy of interested keywords and they will be revealed to the trusted authority, which is not desired by the data user. Thus, Zheng et al. [28] proposed an improved SE scheme that makes use of an access tree to fulfill access control. In [28], each user sends an attribute set to the trusted authority for generating an attribute-related private key. The private key is used to generate trapdoors of interested keywords. Then, users can search over encrypted data with trapdoors without revealing interested keywords. However, in these schemes, user’s attributes are organized to a single set, which decreases the flexibility in specifying access policies.In [29], the researchers proposed attribute set-based encryption (ASBE). In ASBE, the user’s attributes are organized in the form of recursive set structure which enables the data owners to encrypt data with more flexible access policies than ABE. Based on this technique, Xu et al. [7] proposed attribute set-based keyword search (ASBKS). Their scheme has better flexibility in user attribute organization and more efficiency in specifying policies. However, it only supports single keyword query, which limits the performance of searching.To achieve multi-keyword search, Boolean keyword expression search was presented in [1]. In [1], keywords are divided into two parts: value and name, which are both organized in the form of an access tree structure. Inspired by this, we propose an ASBBKS scheme that can support Boolean keyword search, compounded attributes, and flexible search policies simultaneously.


## 1.3. Paper Organization

The rest of the paper is organized as follows. We introduce some preliminaries in Section2. In Section 3, the concrete construction of the ASBBKS scheme is presented and the formal security proof of the ASBBKS scheme is provided. In Section 4, we evaluate the performance of our ASBBKS scheme and conduct simulation experiments to demonstrate its efficiency and practicality. Finally, we conclude the paper in Section 5.


## 2. Preliminaries

### 2.1. Bilinear Pairings

LetG1 and G2 represent the multiplicative cyclic group of order p, where p represents the prime number. Assume that g is the generator of group G1; then, when e:G1×G1⟶G2 satisfies the following conditions, we say it is a bilinear mapping [30]:(1)
Bilinear: for anyg,h∈G1 and a,b∈Zp, ega,hb=eg,hab.(2)
Non-degenerate:eg,g≠1.If there exists an efficient algorithm that can computeeg,h for all g,h∈G1, then G1 is called a bilinear group.


### 2.2. Recursive Set Structure

We construct user’s attributes as the recursive structure mentioned in [29]. In this structure, each element of a set can be an associated attribute or a set. They are organized like the tree structure with the notation of depth which limits this recursion. Here, we provide an example of this kind of set structure with depth 2 in Figure 2.Figure 2
The recursive set structure.At the first layer, there are attribute elements and set elements. At the second layer, there are only attribute elements. For a set with depth 2, we can denote it asA=A0,A1,…,An where A0 is the set of attributes at depth 1 and Ai is the ith set at depth 2 for 1⩽i⩽n.


### 2.3. Access Tree

In our scheme, the access tree structure is the same as that in [29], and Figure 3 shows an example of access tree T. In T, each inner node x represents a threshold gate which has a threshold value kx. Assume that the set of child nodes of x is represented by childx and the number of child nodes is represented by nx. In addition, each child node of x is labeled from left to right as 1 to nx. Then, we have 1≤kx≤nx. When kx=1, the threshold gate transforms to a “ OR ” gate; when kx=nx, it transforms to an “ AND ” gate. In addition, each leaf node x of T represents an attribute, denoted as attx. Furthermore, the parent of node x is presented as parentx, the label associated with x is presented as labelx, the set of leaf nodes of T is presented as lvsT, and the subtree of T rooted at the node x is presented as Tx.Figure 3
Access tree.For an attribute set structureA=A0,A1,…,. An with depth 2 and an access tree T, if at least one of the following conditions holds, we say that A satisfies T: (1) there is at least one subset of A, in which the combination of its attributes satisfies T; (2) there are some translating nodes where the attributes from multiple sets in A can be combined to satisfy T. The translating node allows attributes from different sets to be combined to satisfy an access tree. Thus, by using some translating nodes, data users can combine attributes from multiple sets to satisfy an access tree. To make an explanation, we take the recursive set structure in Figure 2 and T for example. In access tree T, there are two inner nodes and one of them is a translating node. Their threshold gates are 1 and 2, respectively. For the attribute set structure A in Figure 2, it can easily satisfy node v1. For node v2, subsets A1 and A2 can be combined together to satisfy it. However, if node v2 is not a translating node, then there is no subset of A that can satisfy node v2. Thus, using some translating nodes, data owners can selectively require users to combine attributes from either a single set or multiple sets to satisfy the access tree.Secret share: for an access tree T, each node x of T with associated threshold kx would equip with a polynomial qx. qx is generated by running the secret share algorithm mentioned in [31]. This algorithm is used for distributing a secret s, and the process of this algorithm is as follows:(i)
For the root nodeR, let qR0=s and then randomly select kR−1 coefficients for the polynomial qR.(ii)
For an inner nodex, let qx0=qparentxlabelx and then randomly select kx−1 coefficients for the polynomial qx.(iii)
For a leaf nodex, let the degree of qx be dx=0 and qx0=qparentxlabelx.After executing the algorithm, the valueqx0 corresponding to each leaf node x becomes the secret share of s. We represent this algorithm as qx0|x∈lvsT⟵ Share T,s.


### 2.4. Boolean Query

In [3], a Boolean query requires that a server can find out all the encrypted data associated with an arbitrary Boolean expression among keywords. The expression can be denoted as Expw1,w2,…,wn. While calculating a Boolean expression, let bi=1 if the encrypted data contains wi; otherwise, set bi=0. Then, replace corresponding wi in the expression with bi. After that, if the result of the Boolean expression is “1,” encrypted data satisfy the condition of the Boolean query. In our scheme, keywords are divided into two parts: name and value. They are organized as an access tree structure as shown in Figure 4, which is a more expressive searchable mechanism.Figure 4
Boolean keyword expression.


### 2.5. Definition of ASBBKS

In an ASBBKS scheme, there are several participants including multiple data owners and data users, a cloud server, and a trusted authority used for authorizing and managing data owners/users. An ASBBKS scheme consists of five algorithms:Setup, KeyGen, Encrypt, Trapdoor, and Test.(i)
Setupk⟶pk,mk: given the security parameter k, the Setup algorithm generates a public key pk and a master key mk.(ii)
KeyGenmk,A⟶sk: the KeyGen algorithm uses the master key mk and the given attribute set structure A to generate secret key sk corresponding to A.(iii)
Encryptpk,WV,T⟶C: the Encrypt algorithm inputs public key pk, a set of keyword values WV, and an access tree T and outputs the corresponding ciphertext C.(iv)
Trapdoorsk,BV⟶T: the Trapdoor algorithm inputs secret key sk and a Boolean keyword value expression Bv and outputs the corresponding trapdoor T.(v)
TestC,T⟶0,1: the Test algorithm takes trapdoor T and ciphertext C as input. When the attribute set related to T matches with the access tree encrypted in C and a minimum subset WN′ of keyword names WN encrypted in C satisfies the Boolean keyword expression BV encrypted in T, it outputs 1. Otherwise, it outputs “⊥”.In an ASBBKS scheme, the trusted authority firstly executesSetup to initialize the system parameters. Then, according to the user’s attribute set, it computes secret key for each user. Data owners should execute Encrypt on their data using preset access control policies to generate the corresponding ciphertexts and then upload them to the server. For data users, they can execute Trapdoor to generate trapdoors for searching over ciphertexts. In the end, the server executes Test to find all the data that are authorized to a user by the policies.


### 2.6. Security Model of ASBBKS

We will give the security definition of ASBBKS. If there is no adversary who can win the following game with a non-negligible advantage in probabilistically polynomial time (PPT), then we can say that an ASBBKS scheme is secure against selectively chosen keyword attack (INDSCKA). In the following game, adversaryA interacts with the game challenger C as follows.(i)
Setup: in this stage, challenger C first generates pk,mk through running Setupk. Then, pk will be sent to adversary A.(ii)
Phase 1: in this stage, adversary A can make a polynomial number of queries as follows:(1)
Secret key queries: adversary A adaptively queries secret keys for recursive attribute set structures to challenger C.(2)
Trapdoor queries: adversary A adaptively queries Boolean keyword value expressions BV to challenger C and gets the corresponding trapdoors.(iii)
Challenge: after the above queries, adversary A submits two distinct keyword value sets WV0 and WV1 to challenger C. These sets cannot satisfy the Boolean keyword value expression BV that is queried with the form of Trapdoorqueries in Phase 1. Then, C randomly selects a bit β∈0,1, constructs the challenge ciphertext C∗ofWVβ, and returns it to A.(iv)
Phase 2: adversary A continues to make secret key queries and trapdoor queries similar to phase 1. It requires both WV0 and WV1 to not satisfy the Boolean keyword value expression BV.(v)
Guess: adversary A has to guess and output a bit β′∈0,1. It wins the game if β′=β.


## 2.1. Bilinear Pairings

LetG1 and G2 represent the multiplicative cyclic group of order p, where p represents the prime number. Assume that g is the generator of group G1; then, when e:G1×G1⟶G2 satisfies the following conditions, we say it is a bilinear mapping [30]:(1)
Bilinear: for anyg,h∈G1 and a,b∈Zp, ega,hb=eg,hab.(2)
Non-degenerate:eg,g≠1.If there exists an efficient algorithm that can computeeg,h for all g,h∈G1, then G1 is called a bilinear group.


## 2.2. Recursive Set Structure

We construct user’s attributes as the recursive structure mentioned in [29]. In this structure, each element of a set can be an associated attribute or a set. They are organized like the tree structure with the notation of depth which limits this recursion. Here, we provide an example of this kind of set structure with depth 2 in Figure 2.Figure 2
The recursive set structure.At the first layer, there are attribute elements and set elements. At the second layer, there are only attribute elements. For a set with depth 2, we can denote it asA=A0,A1,…,An where A0 is the set of attributes at depth 1 and Ai is the ith set at depth 2 for 1⩽i⩽n.


## 2.3. Access Tree

In our scheme, the access tree structure is the same as that in [29], and Figure 3 shows an example of access tree T. In T, each inner node x represents a threshold gate which has a threshold value kx. Assume that the set of child nodes of x is represented by childx and the number of child nodes is represented by nx. In addition, each child node of x is labeled from left to right as 1 to nx. Then, we have 1≤kx≤nx. When kx=1, the threshold gate transforms to a “ OR ” gate; when kx=nx, it transforms to an “ AND ” gate. In addition, each leaf node x of T represents an attribute, denoted as attx. Furthermore, the parent of node x is presented as parentx, the label associated with x is presented as labelx, the set of leaf nodes of T is presented as lvsT, and the subtree of T rooted at the node x is presented as Tx.Figure 3
Access tree.For an attribute set structureA=A0,A1,…,. An with depth 2 and an access tree T, if at least one of the following conditions holds, we say that A satisfies T: (1) there is at least one subset of A, in which the combination of its attributes satisfies T; (2) there are some translating nodes where the attributes from multiple sets in A can be combined to satisfy T. The translating node allows attributes from different sets to be combined to satisfy an access tree. Thus, by using some translating nodes, data users can combine attributes from multiple sets to satisfy an access tree. To make an explanation, we take the recursive set structure in Figure 2 and T for example. In access tree T, there are two inner nodes and one of them is a translating node. Their threshold gates are 1 and 2, respectively. For the attribute set structure A in Figure 2, it can easily satisfy node v1. For node v2, subsets A1 and A2 can be combined together to satisfy it. However, if node v2 is not a translating node, then there is no subset of A that can satisfy node v2. Thus, using some translating nodes, data owners can selectively require users to combine attributes from either a single set or multiple sets to satisfy the access tree.Secret share: for an access tree T, each node x of T with associated threshold kx would equip with a polynomial qx. qx is generated by running the secret share algorithm mentioned in [31]. This algorithm is used for distributing a secret s, and the process of this algorithm is as follows:(i)
For the root nodeR, let qR0=s and then randomly select kR−1 coefficients for the polynomial qR.(ii)
For an inner nodex, let qx0=qparentxlabelx and then randomly select kx−1 coefficients for the polynomial qx.(iii)
For a leaf nodex, let the degree of qx be dx=0 and qx0=qparentxlabelx.After executing the algorithm, the valueqx0 corresponding to each leaf node x becomes the secret share of s. We represent this algorithm as qx0|x∈lvsT⟵ Share T,s.


## 2.4. Boolean Query

In [3], a Boolean query requires that a server can find out all the encrypted data associated with an arbitrary Boolean expression among keywords. The expression can be denoted as Expw1,w2,…,wn. While calculating a Boolean expression, let bi=1 if the encrypted data contains wi; otherwise, set bi=0. Then, replace corresponding wi in the expression with bi. After that, if the result of the Boolean expression is “1,” encrypted data satisfy the condition of the Boolean query. In our scheme, keywords are divided into two parts: name and value. They are organized as an access tree structure as shown in Figure 4, which is a more expressive searchable mechanism.Figure 4
Boolean keyword expression.


## 2.5. Definition of ASBBKS

In an ASBBKS scheme, there are several participants including multiple data owners and data users, a cloud server, and a trusted authority used for authorizing and managing data owners/users. An ASBBKS scheme consists of five algorithms:Setup, KeyGen, Encrypt, Trapdoor, and Test.(i)
Setupk⟶pk,mk: given the security parameter k, the Setup algorithm generates a public key pk and a master key mk.(ii)
KeyGenmk,A⟶sk: the KeyGen algorithm uses the master key mk and the given attribute set structure A to generate secret key sk corresponding to A.(iii)
Encryptpk,WV,T⟶C: the Encrypt algorithm inputs public key pk, a set of keyword values WV, and an access tree T and outputs the corresponding ciphertext C.(iv)
Trapdoorsk,BV⟶T: the Trapdoor algorithm inputs secret key sk and a Boolean keyword value expression Bv and outputs the corresponding trapdoor T.(v)
TestC,T⟶0,1: the Test algorithm takes trapdoor T and ciphertext C as input. When the attribute set related to T matches with the access tree encrypted in C and a minimum subset WN′ of keyword names WN encrypted in C satisfies the Boolean keyword expression BV encrypted in T, it outputs 1. Otherwise, it outputs “⊥”.In an ASBBKS scheme, the trusted authority firstly executesSetup to initialize the system parameters. Then, according to the user’s attribute set, it computes secret key for each user. Data owners should execute Encrypt on their data using preset access control policies to generate the corresponding ciphertexts and then upload them to the server. For data users, they can execute Trapdoor to generate trapdoors for searching over ciphertexts. In the end, the server executes Test to find all the data that are authorized to a user by the policies.


## 2.6. Security Model of ASBBKS

We will give the security definition of ASBBKS. If there is no adversary who can win the following game with a non-negligible advantage in probabilistically polynomial time (PPT), then we can say that an ASBBKS scheme is secure against selectively chosen keyword attack (INDSCKA). In the following game, adversaryA interacts with the game challenger C as follows.(i)
Setup: in this stage, challenger C first generates pk,mk through running Setupk. Then, pk will be sent to adversary A.(ii)
Phase 1: in this stage, adversary A can make a polynomial number of queries as follows:(1)
Secret key queries: adversary A adaptively queries secret keys for recursive attribute set structures to challenger C.(2)
Trapdoor queries: adversary A adaptively queries Boolean keyword value expressions BV to challenger C and gets the corresponding trapdoors.(iii)
Challenge: after the above queries, adversary A submits two distinct keyword value sets WV0 and WV1 to challenger C. These sets cannot satisfy the Boolean keyword value expression BV that is queried with the form of Trapdoorqueries in Phase 1. Then, C randomly selects a bit β∈0,1, constructs the challenge ciphertext C∗ofWVβ, and returns it to A.(iv)
Phase 2: adversary A continues to make secret key queries and trapdoor queries similar to phase 1. It requires both WV0 and WV1 to not satisfy the Boolean keyword value expression BV.(v)
Guess: adversary A has to guess and output a bit β′∈0,1. It wins the game if β′=β.


## 3. Our Construction of ASBBKS

In this section, we will provide a concrete construction of our scheme and the formal security proof. In the following construction and security proof, we assume the depth of the user’s attribute set structure to be 2.


### 3.1. The Concrete Construction

#### 3.1.1.Setupκ⟶pk,mk

Lete:G×G⟶GT be a bilinear pairing in which G and GT represent two cyclic groups of prime order p. Assume that g is the generator of G and H0:0,1∗⟶Zp∗ and H1:0,1∗⟶G are two collision-resistant hash functions. Next, it randomly selects β1,β2,α∈Zp∗ and calculates h1=gβ1, h2=gβ2, h3=gα. The master key and the public key pk,mk are set to be(1)pk=G,GT,p,g,e,h1,h2,h3,H0⋅,H1⋅,mk=β1,β2,α.


#### 3.1.2.KeyGenA,mk⟶sk

The input recursive attribute set structure is parsed asA=A0,A1,…,An. Assume that each Ai has mi attribute members; then, there is Ai=ai,1,…,ai,mi for 0≤i≤n. Firstly, it randomly selects a value r∈Zp∗ for attribute set structure A. For each subset Ai, it randomly selects n values ri∈Zp∗|1≤i≤n and sets r0=r. Furthermore, it randomly selects a set of values ri,j∈Zp∗|0≤i≤n,1≤j≤mi for each attribute. Finally, it calculates B=gα−r/β1, Bi,j=griH1ai,jri,j and Bi,j′=gri,j for 0≤i≤n, 1≤j≤mi and Di=gr+ri/β2 for 1≤i≤n. The secret key for A is set to be(2)sk=A,B,Bi,j,Bi,j′|0≤i≤n,1≤j≤mi,Di|1≤i≤n.At the translating node, each elementDi in a secret key supporting ri of set Ai at depth 2 translates to r of set A0 at depth 1. Elements Di and Di′ can be combined as Di/Di′ to translate ri′ to ri at the translating nodes.


#### 3.1.3.Encryptpk,WV,T⟶C

WV=wρ1,wρ2,…,wρm is a set of keyword values and WN=ρ1,ρ2,…,ρm is the set of the keyword names. This algorithm randomly selects m+1 values s0,s1,…,sm∈Zp∗ and computes C1=h1s0, C2=h2s0, Ci,1=gsi, Ci,2=h3s0+si⋅h2H0wρisi for 1≤i≤m. After that, it computes secret shares of s0 through implementing qv0|v∈lvsT⟵ShareT,s0. Further, for each v∈lvsT, it computes Cv=gqv0 and Cv′=H1attvqv0. We assume that the set of translating nodes in T is represented as transT. Then, it calculates C˜x=h2qx0 for each x∈transT. Finally, the ciphertext is set to be(3)C=T,WN,C1,C2,Ci,1,Ci,2|1≤i≤m,Cv,Cv′|v∈lvsT,C˜x|x∈transT.In user keys, elementsC˜x′s and Di′s support translation between sets at a translating node x. We will describe it later in the Test algorithm.


#### 3.1.4.Trapdoorsk,ℬV⟶T

ℬV represents the Boolean keyword value expression which is an access tree. ℬN represents the Boolean keyword name expression which is an access tree with the same structure as ℬV. Taking sk and ℬV as inputs, it randomly selects a value t∈Zp∗ and calculates the secret shares of t by implementing q^v0|v∈lvsℬN⟵ShareℬN,t. Then, this algorithm calculates Tρv,1=h3h2H0w¯ρvq^v0 and Tρv,2=gq^v0. Parsing sk as A,B,Bi,j,Bi,j′|0≤i≤n,1≤j≤mi,Di|1≤i≤n, it further computes B¯=Bt, B¯i,j=Bi,jt, B′¯i,j=Bi,j′t for 0≤i≤n, 1≤j≤mi and D¯i=Dit for 1≤i≤n. Finally, the trapdoor for ℬV is(4)T=A,ℬN,Tρv,1,Tρv,2|v∈lvsℬN,B¯,B¯i,j,B′¯i,j|0≤i≤n,1≤j≤mi,D¯i|1≤i≤n.


#### 3.1.5.TestC,T⟶0,1

Cloud server takes input ciphertextC=T,WN,C1,C2,Ci,1,Ci,2|1≤i≤m,Cv,Cv′|v∈Y,C˜x|x∈transT and the trapdoor T=〈A,ℬN,Tρv,1,Tρv,2|v∈lvsℬN,B¯,B¯i,j,B′¯i,j|0≤i≤n,1≤j≤mi, D¯i|1≤i≤n〉. The complete Test algorithm consists of the following 3 steps.Step 1.
In this step, for the given access treeT and key structure A, it returns a set Sτ. The elements of this set are some labels for each node τ within T. Each label t in Sτ represents a set At and each set satisfies the subtree Tτ. There is TR=T for the root node R and the related set is SR. If A does not satisfy T, the return of this algorithm is “0.” Otherwise, for node τ, it picks one label from the set Sτ, denoted as i. Then, it executes a recursive function DecryptNodeC,T,τ,i, which will return Fτ as the result. According to the type of node τ, the function DecryptNodeC,T,τ,i will be computed in two different ways.(1)
Whenτ is a leaf node: if attτ∉Ai, it returns “⊥”. Otherwise, we have(5)DecryptNodeC,T,τ,i=eCτ,B¯i,jeCτ′,B′¯i,j=eg,gt⋅ri⋅qτ0.(2)
Whenτ is not a leaf node:(i)
Firstly, it calculates a setEτ, which is composed of kτ child nodes of τ. In Eτ, each node z must satisfy one of the following two cases: (1) label i∈Sz and (2) z is a translating node and there exists a label i′ that satisfies i′∈Sz and i′≠i. If such a set does not exist, it returns “⊥”.(ii)
ExecuteDecryptNodeC,T,z,i for each node z∈Eτ which satisfies label i∈Sz and then return Fz as the result.(iii)
ExecuteDecryptNodeC,T,z,i′ for each translating node z∈Eτ which satisfies i′∈Sz and i′≠i and return Fz′ as the result.Ifi=0, elements D¯i′ and C˜z can be used to translate Fz′ to Fz.(6)Fz=eD¯i′,C˜zFz′=egtr+ri′/β2,gβ2⋅qz0eg,gt⋅ri′⋅qz0=eg,gt⋅r⋅qz0.Ifi≠0, elements D¯i and D¯i′ together with C˜z can be used to translate Fz′ to Fz.(7)Fz=eD¯iD¯i′,C˜z⋅Fz′=egtri−ri′β2,gβ2⋅qz0eg,gt⋅ri′⋅qz0=eg,gt⋅ri⋅qz0.(iv)
After computingFz for each node z in Eτ, it computes Fτ as follows:(8)Fτ=∏z∈EτFzΔi,Uz0=eg,gt⋅r⋅qτ0,i=0eg,gt⋅ri⋅qτ0,i≠0,where Δi,Sx=∏j∈S,j≠ix−j/i−j, v=labelz, and Uz=labelz:z∈Eτ.
After the above steps, it further computes the functionDecryptNodeC,T,R,i for root node R and returns FR as the result as follows.(9)FR=eg,gt⋅r⋅s0,i=0,eg,gt⋅ri⋅s0,i≠0,.
In the end, it computes a valueF. When i=0, it assumes F=FR. When i≠0, it computes F as follows:(10)F=eD¯i,C3FR=eg,gt⋅r+ri⋅s0eg,gt⋅ri⋅s0=eg,gtrs0.Step 2.
Firstly, it computes a valueL with the following formula:(11)L=eB¯,C1=egtα−r/β1,gβ1s0=eg,gtα−rs0.
Then, it computesF⋅L with the following formula:(12)F⋅L=eg,gtrs0eg,gtα−rs0=eg,gtαs0.Step 3.
It selects a minimum subsetWN′ from the set of keyword names WN, which satisfies the Boolean keyword name expression ℬN. If WN′ does not exist, it returns “0.” If node x^ is a leaf node of access tree ℬN and is related to the search token T, then the keyword name associated with this node is denoted by ρx^. Further, for each keyword name ρx^∈WN′, it computes(13)Ex^=eCρx^,2,Tρx^,2eTρx^,1,Cρx^,1=eh3s0+sρx^h2H0wρx^sρx^,gq^x^0eh3h2H0w¯ρx^q^x^0,gsρx^.
Ifwρx^=w¯ρx^, then there is Ex^=eg,gαs0q^x^0.
When nodex^ is not a leaf node, for all child nodes z^ of x^, assume that Sx^ represents an arbitrary set with size kx^ consisting of children nodes z^ and Ez^≠⊥. If Sx^ does not exist, then Ez^≠⊥; otherwise, it utilizes the polynomial interpolation to calculate Ex^ to get(14)Ex^=eg,gαs0q^x^0.
At last, for the root node ofℬN, it computes ER^ and checks whether the following equation holds:(15)ER^=F⋅L.
If the equation above does not hold, then the algorithm would keep finding another subset of keyword names from the set of keyword namesWN which satisfies ℬN and repeat the checking as above. If there exists no such keyword name subset such that the above equation holds, it returns “⊥”.
We depict the whole processing steps of our scheme in Figure5.Figure 5
Workflow of our scheme.Remark 1.
For the user’s attribute set structure with depthd, for each level i, a value βi needs to be selected. βi supports the translations between sets at level i or between a set at level i and its outer set at level i−1. Translations across multiple levels will use corresponding translating values and different βs.


### 3.2. Security Proof

In this section, we will provide the formal proof of Theorem1 to prove that our scheme is secure.Theorem 1.
The above scheme is selectively secure against chosen keyword attack in the generic bilinear group model.Proof.
In our security model, the adversaryA assumes to distinguish gαs0+sigβ2H0wρi0si from gθ and gαs0+sigβ2H0wρi1si from gθ, where θ is randomly selected from Zp∗, W0 and W1 are two different keyword sets, wρi0∈W0, and wρi1∈W1. Since A has the same probability to distinguish both of them, it is easy to distinguish gβ2H0wρi0si from gθ. That is, this game can be transformed to A that has the advantage ϵ/2 to distinguish gαs0+si from gθ.
The challengerC can be constructed in this game as follows.(i)
Setup: the challenger C selects parameters α, β1, β2∈Zp∗ and sends public parameter pk=G,GT,p,g,e,gβ1,gβ2,gα,H0 to A. After that, A selects a challenge access tree T∗ and returns it to C.(ii)
Hash1-Queries: challenger C would maintain an H-list, which is empty at first. Given an input attribute ai,j, if ai,j has not been queried, it randomly selects ti,j∈Zp∗ and then returns gti,j to A and the tuple ai,j,ti,j will be added to H-list. For those attributes ai,j that have been queried, C will directly return gti,j to A. A can query this random oracle for polynomially many times.Phase 1.
AdversaryA can make the secret key and trapdoor queries for polynomially many times.(i)
Secret key queries: firstly, for an attribute set structure A=A0,A1,…,An where Ai=ai,1,…,ai,mi for 0≤i≤n, C will randomly select a value r∈Zp∗ for A and compute B=gα−r/β1. For each subset Ai, it will randomly select ri∈Zp∗ and a value ri,j∈Zp∗ for 0≤i≤n, 1≤j≤mi. Next, use these parameters to compute corresponding Bi,j=grigti,jri,j, Bi,j′=gri,j, and Di=gr+ri/β2. Finally, C constructs the secret key sk=A,B,Bi,j,Bi,j′∣0≤i≤n,1≤j≤mi,Di|1≤i≤n with the above parameters and returns it to A.(ii)
Trapdoor queries: if A has queried secret key sk, then C directly runs the Trapdoor algorithm to get the trapdoor T. Challenger C randomly selects t∈Zp∗ and computes the secret shares of t by running q^v0|v∈lvsℬN⟵ShareℬN,t and computes corresponding Tρv,1=gαgβ2H0w¯ρvq^v0, Tρv,2=gq^v0, B¯=Bt,B¯i,j=Bi,jt, B′¯i,j=B′i,jt, and D¯i=Dit. Then the trapdoor for Boolean keyword value expression ℬV is T=〈A,ℬN,Tρv,1,Tρv,2|v∈lvsℬN,B¯,B¯i,j,B′¯i,j∣0≤i≤n,1≤j≤mi,D¯i|1≤i≤n〉, and the challenger C returns it to A.
Challenge:A submits two distinct keyword value sets WV0=wρ1′0,wρ2′0,…,wρm0 and WV1=wρ1′1,wρ2′1⋯,wρm1 to C, and these sets are of equal size. Then, let WN=ρ1,ρ2,…,ρm represent the set of keyword name. For these two sets, they cannot satisfy the Boolean keyword value expression BV. Then, C randomly selects s0,si∈Zp∗, for 1≤i≤m and computes secret shares of s0 by executing ShareT∗,s0⟶qv0|v∈lvsT∗.
Then,C randomly selects a bit β∈0,1 and constructs the challenge ci-phertext C∗=〈T∗,WN,C1,C2,Ci,1,Ci,2∣1≤i≤m, Cv,Cv′|v∈lvsT, C˜x|x∈transT∗〉, and then C returns it to A.(i)
Ifβ=0, it randomly selects θ∈Zp∗ and outputs C1=gβ1s0,C2=gβ2s0, for 1≤i≤m, Ci,1=gsi,Ci,2=gθ, Cv=gqv0,Cv′=gti,jqv0|v∈lvsT∗,attv=ai,j, C˜x=gβ2qx0|x∈transT∗(ii)
Ifβ=1, it outputs C1=gβ1s0, C2=gβ2s0, for1≤i≤m, Ci,1=gsi, Ci,2=gαs0+si, Cv=gqv0,Cv′=gti,jqv0|v∈lvsT∗,attv=ai,j, C˜x=gβ2qx0|x∈transT∗.Phase 2.
After receiving the challenge ciphertextC∗, A can perform secret key queries and trapdoor queries mentioned in phase 1. It requires both WV0 and WV1 to not satisfy the Boolean keyword value expression BV.
Guess:A outputs its guess, which requires A to distinguish gs0+si from gθ to win this game.
Analysis: if A can construct egη,gαs0+si for some gη, A has the ability to distinguish gαs0+si from a random element gθ. Thus, we continue to analyze that adversary A constructs eg,gηαs1+s2 for some gη with negligible advantage. That means A cannot win our game with a non-negligible advantage.
From the above phases, it can be easily found thatsi and α have appeared, so A only needs to construct αs0. With terms gβ1s0 and gα−r/β1, A can construct eg,gαs0eg,g−rs0 and then A needs to conceal eg,grs0. With terms gβ2s0 and gr+ri/β2, A can construct eg,gαs0+ris0 and A needs to conceal eg,gris0. Then, gris0 should be constructed which will use terms gri+aijri, grij, gqv0, and gai,jqv0 because qv(0) is the secret share of s0. However, gris0 cannot be constructed since there are not enough attribute values gqv0 for A to satisfy the access tree T.


## 3.1. The Concrete Construction

### 3.1.1.Setupκ⟶pk,mk

Lete:G×G⟶GT be a bilinear pairing in which G and GT represent two cyclic groups of prime order p. Assume that g is the generator of G and H0:0,1∗⟶Zp∗ and H1:0,1∗⟶G are two collision-resistant hash functions. Next, it randomly selects β1,β2,α∈Zp∗ and calculates h1=gβ1, h2=gβ2, h3=gα. The master key and the public key pk,mk are set to be(1)pk=G,GT,p,g,e,h1,h2,h3,H0⋅,H1⋅,mk=β1,β2,α.


### 3.1.2.KeyGenA,mk⟶sk

The input recursive attribute set structure is parsed asA=A0,A1,…,An. Assume that each Ai has mi attribute members; then, there is Ai=ai,1,…,ai,mi for 0≤i≤n. Firstly, it randomly selects a value r∈Zp∗ for attribute set structure A. For each subset Ai, it randomly selects n values ri∈Zp∗|1≤i≤n and sets r0=r. Furthermore, it randomly selects a set of values ri,j∈Zp∗|0≤i≤n,1≤j≤mi for each attribute. Finally, it calculates B=gα−r/β1, Bi,j=griH1ai,jri,j and Bi,j′=gri,j for 0≤i≤n, 1≤j≤mi and Di=gr+ri/β2 for 1≤i≤n. The secret key for A is set to be(2)sk=A,B,Bi,j,Bi,j′|0≤i≤n,1≤j≤mi,Di|1≤i≤n.At the translating node, each elementDi in a secret key supporting ri of set Ai at depth 2 translates to r of set A0 at depth 1. Elements Di and Di′ can be combined as Di/Di′ to translate ri′ to ri at the translating nodes.


### 3.1.3.Encryptpk,WV,T⟶C

WV=wρ1,wρ2,…,wρm is a set of keyword values and WN=ρ1,ρ2,…,ρm is the set of the keyword names. This algorithm randomly selects m+1 values s0,s1,…,sm∈Zp∗ and computes C1=h1s0, C2=h2s0, Ci,1=gsi, Ci,2=h3s0+si⋅h2H0wρisi for 1≤i≤m. After that, it computes secret shares of s0 through implementing qv0|v∈lvsT⟵ShareT,s0. Further, for each v∈lvsT, it computes Cv=gqv0 and Cv′=H1attvqv0. We assume that the set of translating nodes in T is represented as transT. Then, it calculates C˜x=h2qx0 for each x∈transT. Finally, the ciphertext is set to be(3)C=T,WN,C1,C2,Ci,1,Ci,2|1≤i≤m,Cv,Cv′|v∈lvsT,C˜x|x∈transT.In user keys, elementsC˜x′s and Di′s support translation between sets at a translating node x. We will describe it later in the Test algorithm.


### 3.1.4.Trapdoorsk,ℬV⟶T

ℬV represents the Boolean keyword value expression which is an access tree. ℬN represents the Boolean keyword name expression which is an access tree with the same structure as ℬV. Taking sk and ℬV as inputs, it randomly selects a value t∈Zp∗ and calculates the secret shares of t by implementing q^v0|v∈lvsℬN⟵ShareℬN,t. Then, this algorithm calculates Tρv,1=h3h2H0w¯ρvq^v0 and Tρv,2=gq^v0. Parsing sk as A,B,Bi,j,Bi,j′|0≤i≤n,1≤j≤mi,Di|1≤i≤n, it further computes B¯=Bt, B¯i,j=Bi,jt, B′¯i,j=Bi,j′t for 0≤i≤n, 1≤j≤mi and D¯i=Dit for 1≤i≤n. Finally, the trapdoor for ℬV is(4)T=A,ℬN,Tρv,1,Tρv,2|v∈lvsℬN,B¯,B¯i,j,B′¯i,j|0≤i≤n,1≤j≤mi,D¯i|1≤i≤n.


### 3.1.5.TestC,T⟶0,1

Cloud server takes input ciphertextC=T,WN,C1,C2,Ci,1,Ci,2|1≤i≤m,Cv,Cv′|v∈Y,C˜x|x∈transT and the trapdoor T=〈A,ℬN,Tρv,1,Tρv,2|v∈lvsℬN,B¯,B¯i,j,B′¯i,j|0≤i≤n,1≤j≤mi, D¯i|1≤i≤n〉. The complete Test algorithm consists of the following 3 steps.Step 1.
In this step, for the given access treeT and key structure A, it returns a set Sτ. The elements of this set are some labels for each node τ within T. Each label t in Sτ represents a set At and each set satisfies the subtree Tτ. There is TR=T for the root node R and the related set is SR. If A does not satisfy T, the return of this algorithm is “0.” Otherwise, for node τ, it picks one label from the set Sτ, denoted as i. Then, it executes a recursive function DecryptNodeC,T,τ,i, which will return Fτ as the result. According to the type of node τ, the function DecryptNodeC,T,τ,i will be computed in two different ways.(1)
Whenτ is a leaf node: if attτ∉Ai, it returns “⊥”. Otherwise, we have(5)DecryptNodeC,T,τ,i=eCτ,B¯i,jeCτ′,B′¯i,j=eg,gt⋅ri⋅qτ0.(2)
Whenτ is not a leaf node:(i)
Firstly, it calculates a setEτ, which is composed of kτ child nodes of τ. In Eτ, each node z must satisfy one of the following two cases: (1) label i∈Sz and (2) z is a translating node and there exists a label i′ that satisfies i′∈Sz and i′≠i. If such a set does not exist, it returns “⊥”.(ii)
ExecuteDecryptNodeC,T,z,i for each node z∈Eτ which satisfies label i∈Sz and then return Fz as the result.(iii)
ExecuteDecryptNodeC,T,z,i′ for each translating node z∈Eτ which satisfies i′∈Sz and i′≠i and return Fz′ as the result.Ifi=0, elements D¯i′ and C˜z can be used to translate Fz′ to Fz.(6)Fz=eD¯i′,C˜zFz′=egtr+ri′/β2,gβ2⋅qz0eg,gt⋅ri′⋅qz0=eg,gt⋅r⋅qz0.Ifi≠0, elements D¯i and D¯i′ together with C˜z can be used to translate Fz′ to Fz.(7)Fz=eD¯iD¯i′,C˜z⋅Fz′=egtri−ri′β2,gβ2⋅qz0eg,gt⋅ri′⋅qz0=eg,gt⋅ri⋅qz0.(iv)
After computingFz for each node z in Eτ, it computes Fτ as follows:(8)Fτ=∏z∈EτFzΔi,Uz0=eg,gt⋅r⋅qτ0,i=0eg,gt⋅ri⋅qτ0,i≠0,where Δi,Sx=∏j∈S,j≠ix−j/i−j, v=labelz, and Uz=labelz:z∈Eτ.
After the above steps, it further computes the functionDecryptNodeC,T,R,i for root node R and returns FR as the result as follows.(9)FR=eg,gt⋅r⋅s0,i=0,eg,gt⋅ri⋅s0,i≠0,.
In the end, it computes a valueF. When i=0, it assumes F=FR. When i≠0, it computes F as follows:(10)F=eD¯i,C3FR=eg,gt⋅r+ri⋅s0eg,gt⋅ri⋅s0=eg,gtrs0.Step 2.
Firstly, it computes a valueL with the following formula:(11)L=eB¯,C1=egtα−r/β1,gβ1s0=eg,gtα−rs0.
Then, it computesF⋅L with the following formula:(12)F⋅L=eg,gtrs0eg,gtα−rs0=eg,gtαs0.Step 3.
It selects a minimum subsetWN′ from the set of keyword names WN, which satisfies the Boolean keyword name expression ℬN. If WN′ does not exist, it returns “0.” If node x^ is a leaf node of access tree ℬN and is related to the search token T, then the keyword name associated with this node is denoted by ρx^. Further, for each keyword name ρx^∈WN′, it computes(13)Ex^=eCρx^,2,Tρx^,2eTρx^,1,Cρx^,1=eh3s0+sρx^h2H0wρx^sρx^,gq^x^0eh3h2H0w¯ρx^q^x^0,gsρx^.
Ifwρx^=w¯ρx^, then there is Ex^=eg,gαs0q^x^0.
When nodex^ is not a leaf node, for all child nodes z^ of x^, assume that Sx^ represents an arbitrary set with size kx^ consisting of children nodes z^ and Ez^≠⊥. If Sx^ does not exist, then Ez^≠⊥; otherwise, it utilizes the polynomial interpolation to calculate Ex^ to get(14)Ex^=eg,gαs0q^x^0.
At last, for the root node ofℬN, it computes ER^ and checks whether the following equation holds:(15)ER^=F⋅L.
If the equation above does not hold, then the algorithm would keep finding another subset of keyword names from the set of keyword namesWN which satisfies ℬN and repeat the checking as above. If there exists no such keyword name subset such that the above equation holds, it returns “⊥”.
We depict the whole processing steps of our scheme in Figure5.Figure 5
Workflow of our scheme.Remark 1.
For the user’s attribute set structure with depthd, for each level i, a value βi needs to be selected. βi supports the translations between sets at level i or between a set at level i and its outer set at level i−1. Translations across multiple levels will use corresponding translating values and different βs.


## 3.1.1.Setupκ⟶pk,mk

Lete:G×G⟶GT be a bilinear pairing in which G and GT represent two cyclic groups of prime order p. Assume that g is the generator of G and H0:0,1∗⟶Zp∗ and H1:0,1∗⟶G are two collision-resistant hash functions. Next, it randomly selects β1,β2,α∈Zp∗ and calculates h1=gβ1, h2=gβ2, h3=gα. The master key and the public key pk,mk are set to be(1)pk=G,GT,p,g,e,h1,h2,h3,H0⋅,H1⋅,mk=β1,β2,α.


## 3.1.2.KeyGenA,mk⟶sk

The input recursive attribute set structure is parsed asA=A0,A1,…,An. Assume that each Ai has mi attribute members; then, there is Ai=ai,1,…,ai,mi for 0≤i≤n. Firstly, it randomly selects a value r∈Zp∗ for attribute set structure A. For each subset Ai, it randomly selects n values ri∈Zp∗|1≤i≤n and sets r0=r. Furthermore, it randomly selects a set of values ri,j∈Zp∗|0≤i≤n,1≤j≤mi for each attribute. Finally, it calculates B=gα−r/β1, Bi,j=griH1ai,jri,j and Bi,j′=gri,j for 0≤i≤n, 1≤j≤mi and Di=gr+ri/β2 for 1≤i≤n. The secret key for A is set to be(2)sk=A,B,Bi,j,Bi,j′|0≤i≤n,1≤j≤mi,Di|1≤i≤n.At the translating node, each elementDi in a secret key supporting ri of set Ai at depth 2 translates to r of set A0 at depth 1. Elements Di and Di′ can be combined as Di/Di′ to translate ri′ to ri at the translating nodes.


## 3.1.3.Encryptpk,WV,T⟶C

WV=wρ1,wρ2,…,wρm is a set of keyword values and WN=ρ1,ρ2,…,ρm is the set of the keyword names. This algorithm randomly selects m+1 values s0,s1,…,sm∈Zp∗ and computes C1=h1s0, C2=h2s0, Ci,1=gsi, Ci,2=h3s0+si⋅h2H0wρisi for 1≤i≤m. After that, it computes secret shares of s0 through implementing qv0|v∈lvsT⟵ShareT,s0. Further, for each v∈lvsT, it computes Cv=gqv0 and Cv′=H1attvqv0. We assume that the set of translating nodes in T is represented as transT. Then, it calculates C˜x=h2qx0 for each x∈transT. Finally, the ciphertext is set to be(3)C=T,WN,C1,C2,Ci,1,Ci,2|1≤i≤m,Cv,Cv′|v∈lvsT,C˜x|x∈transT.In user keys, elementsC˜x′s and Di′s support translation between sets at a translating node x. We will describe it later in the Test algorithm.


## 3.1.4.Trapdoorsk,ℬV⟶T

ℬV represents the Boolean keyword value expression which is an access tree. ℬN represents the Boolean keyword name expression which is an access tree with the same structure as ℬV. Taking sk and ℬV as inputs, it randomly selects a value t∈Zp∗ and calculates the secret shares of t by implementing q^v0|v∈lvsℬN⟵ShareℬN,t. Then, this algorithm calculates Tρv,1=h3h2H0w¯ρvq^v0 and Tρv,2=gq^v0. Parsing sk as A,B,Bi,j,Bi,j′|0≤i≤n,1≤j≤mi,Di|1≤i≤n, it further computes B¯=Bt, B¯i,j=Bi,jt, B′¯i,j=Bi,j′t for 0≤i≤n, 1≤j≤mi and D¯i=Dit for 1≤i≤n. Finally, the trapdoor for ℬV is(4)T=A,ℬN,Tρv,1,Tρv,2|v∈lvsℬN,B¯,B¯i,j,B′¯i,j|0≤i≤n,1≤j≤mi,D¯i|1≤i≤n.


## 3.1.5.TestC,T⟶0,1

Cloud server takes input ciphertextC=T,WN,C1,C2,Ci,1,Ci,2|1≤i≤m,Cv,Cv′|v∈Y,C˜x|x∈transT and the trapdoor T=〈A,ℬN,Tρv,1,Tρv,2|v∈lvsℬN,B¯,B¯i,j,B′¯i,j|0≤i≤n,1≤j≤mi, D¯i|1≤i≤n〉. The complete Test algorithm consists of the following 3 steps.Step 1.
In this step, for the given access treeT and key structure A, it returns a set Sτ. The elements of this set are some labels for each node τ within T. Each label t in Sτ represents a set At and each set satisfies the subtree Tτ. There is TR=T for the root node R and the related set is SR. If A does not satisfy T, the return of this algorithm is “0.” Otherwise, for node τ, it picks one label from the set Sτ, denoted as i. Then, it executes a recursive function DecryptNodeC,T,τ,i, which will return Fτ as the result. According to the type of node τ, the function DecryptNodeC,T,τ,i will be computed in two different ways.(1)
Whenτ is a leaf node: if attτ∉Ai, it returns “⊥”. Otherwise, we have(5)DecryptNodeC,T,τ,i=eCτ,B¯i,jeCτ′,B′¯i,j=eg,gt⋅ri⋅qτ0.(2)
Whenτ is not a leaf node:(i)
Firstly, it calculates a setEτ, which is composed of kτ child nodes of τ. In Eτ, each node z must satisfy one of the following two cases: (1) label i∈Sz and (2) z is a translating node and there exists a label i′ that satisfies i′∈Sz and i′≠i. If such a set does not exist, it returns “⊥”.(ii)
ExecuteDecryptNodeC,T,z,i for each node z∈Eτ which satisfies label i∈Sz and then return Fz as the result.(iii)
ExecuteDecryptNodeC,T,z,i′ for each translating node z∈Eτ which satisfies i′∈Sz and i′≠i and return Fz′ as the result.Ifi=0, elements D¯i′ and C˜z can be used to translate Fz′ to Fz.(6)Fz=eD¯i′,C˜zFz′=egtr+ri′/β2,gβ2⋅qz0eg,gt⋅ri′⋅qz0=eg,gt⋅r⋅qz0.Ifi≠0, elements D¯i and D¯i′ together with C˜z can be used to translate Fz′ to Fz.(7)Fz=eD¯iD¯i′,C˜z⋅Fz′=egtri−ri′β2,gβ2⋅qz0eg,gt⋅ri′⋅qz0=eg,gt⋅ri⋅qz0.(iv)
After computingFz for each node z in Eτ, it computes Fτ as follows:(8)Fτ=∏z∈EτFzΔi,Uz0=eg,gt⋅r⋅qτ0,i=0eg,gt⋅ri⋅qτ0,i≠0,where Δi,Sx=∏j∈S,j≠ix−j/i−j, v=labelz, and Uz=labelz:z∈Eτ.
After the above steps, it further computes the functionDecryptNodeC,T,R,i for root node R and returns FR as the result as follows.(9)FR=eg,gt⋅r⋅s0,i=0,eg,gt⋅ri⋅s0,i≠0,.
In the end, it computes a valueF. When i=0, it assumes F=FR. When i≠0, it computes F as follows:(10)F=eD¯i,C3FR=eg,gt⋅r+ri⋅s0eg,gt⋅ri⋅s0=eg,gtrs0.Step 2.
Firstly, it computes a valueL with the following formula:(11)L=eB¯,C1=egtα−r/β1,gβ1s0=eg,gtα−rs0.
Then, it computesF⋅L with the following formula:(12)F⋅L=eg,gtrs0eg,gtα−rs0=eg,gtαs0.Step 3.
It selects a minimum subsetWN′ from the set of keyword names WN, which satisfies the Boolean keyword name expression ℬN. If WN′ does not exist, it returns “0.” If node x^ is a leaf node of access tree ℬN and is related to the search token T, then the keyword name associated with this node is denoted by ρx^. Further, for each keyword name ρx^∈WN′, it computes(13)Ex^=eCρx^,2,Tρx^,2eTρx^,1,Cρx^,1=eh3s0+sρx^h2H0wρx^sρx^,gq^x^0eh3h2H0w¯ρx^q^x^0,gsρx^.
Ifwρx^=w¯ρx^, then there is Ex^=eg,gαs0q^x^0.
When nodex^ is not a leaf node, for all child nodes z^ of x^, assume that Sx^ represents an arbitrary set with size kx^ consisting of children nodes z^ and Ez^≠⊥. If Sx^ does not exist, then Ez^≠⊥; otherwise, it utilizes the polynomial interpolation to calculate Ex^ to get(14)Ex^=eg,gαs0q^x^0.
At last, for the root node ofℬN, it computes ER^ and checks whether the following equation holds:(15)ER^=F⋅L.
If the equation above does not hold, then the algorithm would keep finding another subset of keyword names from the set of keyword namesWN which satisfies ℬN and repeat the checking as above. If there exists no such keyword name subset such that the above equation holds, it returns “⊥”.
We depict the whole processing steps of our scheme in Figure5.Figure 5
Workflow of our scheme.Remark 1.
For the user’s attribute set structure with depthd, for each level i, a value βi needs to be selected. βi supports the translations between sets at level i or between a set at level i and its outer set at level i−1. Translations across multiple levels will use corresponding translating values and different βs.


## 3.2. Security Proof

In this section, we will provide the formal proof of Theorem1 to prove that our scheme is secure.Theorem 1.
The above scheme is selectively secure against chosen keyword attack in the generic bilinear group model.Proof.
In our security model, the adversaryA assumes to distinguish gαs0+sigβ2H0wρi0si from gθ and gαs0+sigβ2H0wρi1si from gθ, where θ is randomly selected from Zp∗, W0 and W1 are two different keyword sets, wρi0∈W0, and wρi1∈W1. Since A has the same probability to distinguish both of them, it is easy to distinguish gβ2H0wρi0si from gθ. That is, this game can be transformed to A that has the advantage ϵ/2 to distinguish gαs0+si from gθ.
The challengerC can be constructed in this game as follows.(i)
Setup: the challenger C selects parameters α, β1, β2∈Zp∗ and sends public parameter pk=G,GT,p,g,e,gβ1,gβ2,gα,H0 to A. After that, A selects a challenge access tree T∗ and returns it to C.(ii)
Hash1-Queries: challenger C would maintain an H-list, which is empty at first. Given an input attribute ai,j, if ai,j has not been queried, it randomly selects ti,j∈Zp∗ and then returns gti,j to A and the tuple ai,j,ti,j will be added to H-list. For those attributes ai,j that have been queried, C will directly return gti,j to A. A can query this random oracle for polynomially many times.Phase 1.
AdversaryA can make the secret key and trapdoor queries for polynomially many times.(i)
Secret key queries: firstly, for an attribute set structure A=A0,A1,…,An where Ai=ai,1,…,ai,mi for 0≤i≤n, C will randomly select a value r∈Zp∗ for A and compute B=gα−r/β1. For each subset Ai, it will randomly select ri∈Zp∗ and a value ri,j∈Zp∗ for 0≤i≤n, 1≤j≤mi. Next, use these parameters to compute corresponding Bi,j=grigti,jri,j, Bi,j′=gri,j, and Di=gr+ri/β2. Finally, C constructs the secret key sk=A,B,Bi,j,Bi,j′∣0≤i≤n,1≤j≤mi,Di|1≤i≤n with the above parameters and returns it to A.(ii)
Trapdoor queries: if A has queried secret key sk, then C directly runs the Trapdoor algorithm to get the trapdoor T. Challenger C randomly selects t∈Zp∗ and computes the secret shares of t by running q^v0|v∈lvsℬN⟵ShareℬN,t and computes corresponding Tρv,1=gαgβ2H0w¯ρvq^v0, Tρv,2=gq^v0, B¯=Bt,B¯i,j=Bi,jt, B′¯i,j=B′i,jt, and D¯i=Dit. Then the trapdoor for Boolean keyword value expression ℬV is T=〈A,ℬN,Tρv,1,Tρv,2|v∈lvsℬN,B¯,B¯i,j,B′¯i,j∣0≤i≤n,1≤j≤mi,D¯i|1≤i≤n〉, and the challenger C returns it to A.
Challenge:A submits two distinct keyword value sets WV0=wρ1′0,wρ2′0,…,wρm0 and WV1=wρ1′1,wρ2′1⋯,wρm1 to C, and these sets are of equal size. Then, let WN=ρ1,ρ2,…,ρm represent the set of keyword name. For these two sets, they cannot satisfy the Boolean keyword value expression BV. Then, C randomly selects s0,si∈Zp∗, for 1≤i≤m and computes secret shares of s0 by executing ShareT∗,s0⟶qv0|v∈lvsT∗.
Then,C randomly selects a bit β∈0,1 and constructs the challenge ci-phertext C∗=〈T∗,WN,C1,C2,Ci,1,Ci,2∣1≤i≤m, Cv,Cv′|v∈lvsT, C˜x|x∈transT∗〉, and then C returns it to A.(i)
Ifβ=0, it randomly selects θ∈Zp∗ and outputs C1=gβ1s0,C2=gβ2s0, for 1≤i≤m, Ci,1=gsi,Ci,2=gθ, Cv=gqv0,Cv′=gti,jqv0|v∈lvsT∗,attv=ai,j, C˜x=gβ2qx0|x∈transT∗(ii)
Ifβ=1, it outputs C1=gβ1s0, C2=gβ2s0, for1≤i≤m, Ci,1=gsi, Ci,2=gαs0+si, Cv=gqv0,Cv′=gti,jqv0|v∈lvsT∗,attv=ai,j, C˜x=gβ2qx0|x∈transT∗.Phase 2.
After receiving the challenge ciphertextC∗, A can perform secret key queries and trapdoor queries mentioned in phase 1. It requires both WV0 and WV1 to not satisfy the Boolean keyword value expression BV.
Guess:A outputs its guess, which requires A to distinguish gs0+si from gθ to win this game.
Analysis: if A can construct egη,gαs0+si for some gη, A has the ability to distinguish gαs0+si from a random element gθ. Thus, we continue to analyze that adversary A constructs eg,gηαs1+s2 for some gη with negligible advantage. That means A cannot win our game with a non-negligible advantage.
From the above phases, it can be easily found thatsi and α have appeared, so A only needs to construct αs0. With terms gβ1s0 and gα−r/β1, A can construct eg,gαs0eg,g−rs0 and then A needs to conceal eg,grs0. With terms gβ2s0 and gr+ri/β2, A can construct eg,gαs0+ris0 and A needs to conceal eg,gris0. Then, gris0 should be constructed which will use terms gri+aijri, grij, gqv0, and gai,jqv0 because qv(0) is the secret share of s0. However, gris0 cannot be constructed since there are not enough attribute values gqv0 for A to satisfy the access tree T.


## 4. Performance Analysis

In the existing ABKS schemes, no scheme can support both Boolean keyword search and recursive set structure. At first, we compare the existing schemes [1, 7, 28] in Table 1 with our scheme in the aspect of their functionalities. We assume four parts to compare, search method, access structure, attribute set structure, and translating nodes. From Table 1, we can conclude that our scheme is the first one that supports compound attributes, flexible access policies' specifying, and Boolean keyword search simultaneously.Table 1
Comparison of functionalities between SE schemes.
Boolean keyword searchAccess structureCompound attributesTranslating nodes[1]√LSSS××[28]×Access tree××[7]×Access tree√√Our ASBBKS√Access tree√√


### 4.1. Theoretical Analysis

In our scheme, three operations are the most time consuming which are, respectively, the bilinear pairing, the modular exponentiation, and the hash functionH1. Since H1 can be precomputed, we just consider the former two operations in the following analysis.In theoretical analysis, we focus on the computation complexity and storage overhead of each step. Firstly, we assume a user’s 2-level recursive attribute set to beA=A0,A1,…,An where Ai=ai,1,ai,2,…,ai,mi. Let M=m0+m1+⋯+mn. Then, let the leaf nodes of an access tree T be lvsT and translating nodes be transT. For the keyword set used in Encrypt, we denote the number of keywords in this set to be N and the leaf nodes of a Boolean keyword value expression BV to be lvsBV. We organize the theoretical computation complexity and storage overhead of the existing schemes [1, 7, 28] and our scheme in Table 2.Table 2
Theoretical efficiency analysis and comparison between schemes.
[31][28][11]Our schemeComputation costsKeyGen2M+1E1+2n+2ME2+2nE1+2n+2MEEncrypt2lvsT+4E|transT|+2lvsT+5E1+2lvsT+3NE|transT|+2lvsT+3N+2ETrapdoor2M+4E4+n+2ME1+2M+3lvsBNE1+3lvsBN+n+2METest2l+3e+t−1ET2l+k+3e+t−1ET1+2l+2lvsBNe+lvsT+lvsBNET2l+k+1+2lvsBNe+t−1+lvsBNETCommunication costsKeyGen2MG1+n+2MG1+2MG1+n+2MGEncrypt2lvsT+3G2lvsT+|transT|+4G1+2lvsT+2NG2lvsT+|transT|+2N+2GTrapdoor2M+3G3+n+2MG1+2M+2lvsBNG1+n+2M+2lvsBNGTestNCNCNCNCe: evaluation of a bilinear pairing; E: evaluation of a modular exponentiation in G; ET: evaluation of a modular exponentiation in GT; M: number of attributes in A; n: number of sets in A; l: number of attributes used in A required to satisfy T; t: number of all used nodes in T; lvsT: number of leaf nodes used in T; lvsBN: number of keywords used in BN; transT: number of translating nodes used in T; k: number of all translating nodes on the path from each leaf node used to the root.KeyGen. For the KeyGen algorithm in our scheme, its computation complexity is 2M+2n+1 exponentiations in G. The storage overhead is 2M+n+1 group elements in G. In [28], the KeyGen algorithm takes 2M+1 exponentiations in G. The storage overhead is 2M group elements in G. In [7], the computation complexity of its KeyGen algorithm is 1+2n+2M exponentiations in G. The storage overhead is 2M+n+1 group elements in G. In [1], the KeyGen algorithm takes 2+2n exponentiations in G. The storage takes 2M+1 group elements in G.Encrypt. For the Encrypt algorithm in our scheme, its computation complexity is transT+2lvsT+3N+2 exponentiations in G. The storage overhead is transT+2lvsT+2N+2 group elements in G. In [28], the Encrypt algorithm takes 2lvsT+4 exponentiations in G. The storage overhead is 2lvsT+3 group elements in G. In [28], the computation complexity of its Encrypt algorithm is transT+2lvsT+5 exponentiations in G. The storage overhead is transT+2lvsT+4 group elements in G. In [28], the Encrypt algorithm takes 1+2lvsT+3N exponentiations in G. The storage takes 1+2lvsT+2N group elements in G.Trapdoor. For the Trapdoor algorithm in our scheme, its computation complexity is 2M+n+3lvsBN+1 exponentiations in G. The storage overhead is 2M+n+1+2lvsBN group elements in G. In [1], the Trapdoor algorithm takes 2M+4 exponentiations in G. The storage overhead is 2M+3 group elements in G. In [28], the computation complexity of its Trapdoor algorithm is 4+n+2M exponentiations in G. The storage overhead is 3+n+2M group elements in G. In [7], the Trapdoor algorithm takes 1+2M+3lvsBN exponentiations in G. The storage takes 1+2M+2lvsBN group elements in G.Test. For the Test algorithm in our scheme, we first assume A has l leaf nodes satisfying T and ki translating nodes on the path from ith leaf node used to the root node where 1≤i≤l, and let k=k1+k2+⋯+kl. In addition, we denote the number of all used nodes in T as t, and the computation complexity is 2l+k+1+2lvsBN pairings and t−1+lvsBN exponentiations in GT. The storage overhead depends on the number of the matched ciphertexts, which we denote as NC. In [28], the Test algorithm takes 2l+3 pairings and t−1 exponentiations in GT and the storage overhead we assume is NC. In [7] the computation complexity of its Test algorithm is 3+k+2l pairings and t−1 exponentiations in GT, and the storage overhead we assume is NC. In [1], the Search algorithm takes 1+2l+2lvsBN parings and lvsT+lvsBN exponentiations in GT and the storage overhead we assume is NC.Remark 2.
From the analysis, the difference in computation cost between our scheme and [28] depends linearly on the number of keywords, the number of inner sets in A, and the number of translating nodes in T. When there is only one set in A, one keyword in the Encrypt algorithm and Trapdoor algorithm, and no translating node in access tree T, the computation cost of our scheme is the same as that of the scheme in [28]. The difference in computation cost between our scheme and [7] depends linearly on the number of keywords. When there is only one keyword in the Encrypt algorithm and Trapdoor algorithm, the computation cost of our scheme is the same as that of the scheme in [7]. The difference in computation cost between our scheme and [1] depends linearly on the number of inner sets in A and the number of translating nodes in T. When there is one set in A and no translating node in access tree T, the computation cost of our scheme is the same as that of the scheme in [1]. In summary, our ASBBKS scheme supports compound attributes and Boolean queries by adding some computation operations, which is more suitable for practical application environments.


### 4.2. Experiments

In the following, we have made a series of comprehensive experiments to simulate the execution of our scheme on a personal computer (the CPU is i7-8700U 3.2 GHz with a 24 GB memory and the operating system is Ubuntu 18.04 LTS) and the PBC library. We evaluate our scheme with different parameters and record the execution time of each step in our ASBBKS scheme. In these experiments, we assume that the user’s recursive attribute setA has two levels. We show our experiment results of each step in Figure 6.Figure 6
Operation time of the algorithms in ASBBKS. (a) KeyGen. (b) Encrypt. (c) Trapdoor. (d) Test.
(a)(b)(c)(d)KeyGen. Figure 6(a) shows the time cost of the KeyGen phase for our ASBBKS scheme. We consider two parameters that may affect the execution time of this step: the number of subsets in a user’s set structure and the number of attributes in each subset. We assume the number of subsets to be 1, 10, and 20 and the number of attributes in each subset to be 20, 40, 60, 80, and 100, respectively. As we can see, the time cost of KeyGen is increased linearly with the above two parameters. It only takes 638 ms when there are 20 subsets and 100 attributes in each subset. The number of attributes in each subset influences the execution time most, while the number of subsets has a smaller impact.Encrypt. Figure 6(b) shows the time cost of the Encrypt phase. We consider three parameters that may affect the execution time of this step: the number of translating nodes and leaf nodes in an access tree and the number of keywords. We assume that there are 20, 40, 60, 80, and 100 leaf nodes and keywords and there are 0, 5, and 10 translating nodes, respectively. As we can see, the time cost of Encrypt is increased linearly with the above parameters. It only takes 990 ms when there are 10 translating nodes and 100 leaf nodes in an access tree and 100 keywords in a document. In these parameters, the main influencing factors are the number of leaf nodes and the number of keywords, while the number of translating nodes only affects the execution time for several milliseconds.Trapdoor. Figure 6(c) shows the time cost of the Trapdoor phase. We consider three parameters that may affect the execution time of this step: the number of subsets in a user’s set structure, the number of attributes in each subset, and the number of leaf nodes in a keyword structure. We assume the number of attributes and leaf nodes to be 20, 40, 60, 80, and 100 and the number of subsets to be 1, 10, and 20, respectively. As we can see, the execution time of the Trapdoor phase is increased linearly with the above parameters. It only takes 603 ms when there are 20 subsets with 100 attributes in each subset and 100 leaf nodes for the keyword structure. In these parameters, the main influencing factors are the number of attributes and the number of leaf nodes, while the number of subsets has a smaller impact.Test. Figure 6(d) shows the time cost of the Test phase. We consider three parameters that may affect the execution time of this step: the number of keywords, the number of attributes in each subset, and the number of translating nodes. We assume that there are 20, 40, 60, 80, and 100 attributes and keywords. We also assume that there are 0, 5, and 10 translating nodes. Further, we assume that the number of subsets in a user’s set structure is fixed to 10. As we can see, the execution time of the Test phase is increased linearly with the above parameters. It only takes 370 ms when there are 100 attributes in each subset, 10 translating nodes in an access tree, and 100 keywords in the document. In these parameters, the main influencing factors are the number of attributes and the number of keywords, while the number of translating nodes has a certain impact on it.From the above experiments for each algorithm in our scheme, we can conclude that it is an efficient and practical scheme for use in a PHR application.


## 4.1. Theoretical Analysis

In our scheme, three operations are the most time consuming which are, respectively, the bilinear pairing, the modular exponentiation, and the hash functionH1. Since H1 can be precomputed, we just consider the former two operations in the following analysis.In theoretical analysis, we focus on the computation complexity and storage overhead of each step. Firstly, we assume a user’s 2-level recursive attribute set to beA=A0,A1,…,An where Ai=ai,1,ai,2,…,ai,mi. Let M=m0+m1+⋯+mn. Then, let the leaf nodes of an access tree T be lvsT and translating nodes be transT. For the keyword set used in Encrypt, we denote the number of keywords in this set to be N and the leaf nodes of a Boolean keyword value expression BV to be lvsBV. We organize the theoretical computation complexity and storage overhead of the existing schemes [1, 7, 28] and our scheme in Table 2.Table 2
Theoretical efficiency analysis and comparison between schemes.
[31][28][11]Our schemeComputation costsKeyGen2M+1E1+2n+2ME2+2nE1+2n+2MEEncrypt2lvsT+4E|transT|+2lvsT+5E1+2lvsT+3NE|transT|+2lvsT+3N+2ETrapdoor2M+4E4+n+2ME1+2M+3lvsBNE1+3lvsBN+n+2METest2l+3e+t−1ET2l+k+3e+t−1ET1+2l+2lvsBNe+lvsT+lvsBNET2l+k+1+2lvsBNe+t−1+lvsBNETCommunication costsKeyGen2MG1+n+2MG1+2MG1+n+2MGEncrypt2lvsT+3G2lvsT+|transT|+4G1+2lvsT+2NG2lvsT+|transT|+2N+2GTrapdoor2M+3G3+n+2MG1+2M+2lvsBNG1+n+2M+2lvsBNGTestNCNCNCNCe: evaluation of a bilinear pairing; E: evaluation of a modular exponentiation in G; ET: evaluation of a modular exponentiation in GT; M: number of attributes in A; n: number of sets in A; l: number of attributes used in A required to satisfy T; t: number of all used nodes in T; lvsT: number of leaf nodes used in T; lvsBN: number of keywords used in BN; transT: number of translating nodes used in T; k: number of all translating nodes on the path from each leaf node used to the root.KeyGen. For the KeyGen algorithm in our scheme, its computation complexity is 2M+2n+1 exponentiations in G. The storage overhead is 2M+n+1 group elements in G. In [28], the KeyGen algorithm takes 2M+1 exponentiations in G. The storage overhead is 2M group elements in G. In [7], the computation complexity of its KeyGen algorithm is 1+2n+2M exponentiations in G. The storage overhead is 2M+n+1 group elements in G. In [1], the KeyGen algorithm takes 2+2n exponentiations in G. The storage takes 2M+1 group elements in G.Encrypt. For the Encrypt algorithm in our scheme, its computation complexity is transT+2lvsT+3N+2 exponentiations in G. The storage overhead is transT+2lvsT+2N+2 group elements in G. In [28], the Encrypt algorithm takes 2lvsT+4 exponentiations in G. The storage overhead is 2lvsT+3 group elements in G. In [28], the computation complexity of its Encrypt algorithm is transT+2lvsT+5 exponentiations in G. The storage overhead is transT+2lvsT+4 group elements in G. In [28], the Encrypt algorithm takes 1+2lvsT+3N exponentiations in G. The storage takes 1+2lvsT+2N group elements in G.Trapdoor. For the Trapdoor algorithm in our scheme, its computation complexity is 2M+n+3lvsBN+1 exponentiations in G. The storage overhead is 2M+n+1+2lvsBN group elements in G. In [1], the Trapdoor algorithm takes 2M+4 exponentiations in G. The storage overhead is 2M+3 group elements in G. In [28], the computation complexity of its Trapdoor algorithm is 4+n+2M exponentiations in G. The storage overhead is 3+n+2M group elements in G. In [7], the Trapdoor algorithm takes 1+2M+3lvsBN exponentiations in G. The storage takes 1+2M+2lvsBN group elements in G.Test. For the Test algorithm in our scheme, we first assume A has l leaf nodes satisfying T and ki translating nodes on the path from ith leaf node used to the root node where 1≤i≤l, and let k=k1+k2+⋯+kl. In addition, we denote the number of all used nodes in T as t, and the computation complexity is 2l+k+1+2lvsBN pairings and t−1+lvsBN exponentiations in GT. The storage overhead depends on the number of the matched ciphertexts, which we denote as NC. In [28], the Test algorithm takes 2l+3 pairings and t−1 exponentiations in GT and the storage overhead we assume is NC. In [7] the computation complexity of its Test algorithm is 3+k+2l pairings and t−1 exponentiations in GT, and the storage overhead we assume is NC. In [1], the Search algorithm takes 1+2l+2lvsBN parings and lvsT+lvsBN exponentiations in GT and the storage overhead we assume is NC.Remark 2.
From the analysis, the difference in computation cost between our scheme and [28] depends linearly on the number of keywords, the number of inner sets in A, and the number of translating nodes in T. When there is only one set in A, one keyword in the Encrypt algorithm and Trapdoor algorithm, and no translating node in access tree T, the computation cost of our scheme is the same as that of the scheme in [28]. The difference in computation cost between our scheme and [7] depends linearly on the number of keywords. When there is only one keyword in the Encrypt algorithm and Trapdoor algorithm, the computation cost of our scheme is the same as that of the scheme in [7]. The difference in computation cost between our scheme and [1] depends linearly on the number of inner sets in A and the number of translating nodes in T. When there is one set in A and no translating node in access tree T, the computation cost of our scheme is the same as that of the scheme in [1]. In summary, our ASBBKS scheme supports compound attributes and Boolean queries by adding some computation operations, which is more suitable for practical application environments.


## 4.2. Experiments

In the following, we have made a series of comprehensive experiments to simulate the execution of our scheme on a personal computer (the CPU is i7-8700U 3.2 GHz with a 24 GB memory and the operating system is Ubuntu 18.04 LTS) and the PBC library. We evaluate our scheme with different parameters and record the execution time of each step in our ASBBKS scheme. In these experiments, we assume that the user’s recursive attribute setA has two levels. We show our experiment results of each step in Figure 6.Figure 6
Operation time of the algorithms in ASBBKS. (a) KeyGen. (b) Encrypt. (c) Trapdoor. (d) Test.
(a)(b)(c)(d)KeyGen. Figure 6(a) shows the time cost of the KeyGen phase for our ASBBKS scheme. We consider two parameters that may affect the execution time of this step: the number of subsets in a user’s set structure and the number of attributes in each subset. We assume the number of subsets to be 1, 10, and 20 and the number of attributes in each subset to be 20, 40, 60, 80, and 100, respectively. As we can see, the time cost of KeyGen is increased linearly with the above two parameters. It only takes 638 ms when there are 20 subsets and 100 attributes in each subset. The number of attributes in each subset influences the execution time most, while the number of subsets has a smaller impact.Encrypt. Figure 6(b) shows the time cost of the Encrypt phase. We consider three parameters that may affect the execution time of this step: the number of translating nodes and leaf nodes in an access tree and the number of keywords. We assume that there are 20, 40, 60, 80, and 100 leaf nodes and keywords and there are 0, 5, and 10 translating nodes, respectively. As we can see, the time cost of Encrypt is increased linearly with the above parameters. It only takes 990 ms when there are 10 translating nodes and 100 leaf nodes in an access tree and 100 keywords in a document. In these parameters, the main influencing factors are the number of leaf nodes and the number of keywords, while the number of translating nodes only affects the execution time for several milliseconds.Trapdoor. Figure 6(c) shows the time cost of the Trapdoor phase. We consider three parameters that may affect the execution time of this step: the number of subsets in a user’s set structure, the number of attributes in each subset, and the number of leaf nodes in a keyword structure. We assume the number of attributes and leaf nodes to be 20, 40, 60, 80, and 100 and the number of subsets to be 1, 10, and 20, respectively. As we can see, the execution time of the Trapdoor phase is increased linearly with the above parameters. It only takes 603 ms when there are 20 subsets with 100 attributes in each subset and 100 leaf nodes for the keyword structure. In these parameters, the main influencing factors are the number of attributes and the number of leaf nodes, while the number of subsets has a smaller impact.Test. Figure 6(d) shows the time cost of the Test phase. We consider three parameters that may affect the execution time of this step: the number of keywords, the number of attributes in each subset, and the number of translating nodes. We assume that there are 20, 40, 60, 80, and 100 attributes and keywords. We also assume that there are 0, 5, and 10 translating nodes. Further, we assume that the number of subsets in a user’s set structure is fixed to 10. As we can see, the execution time of the Test phase is increased linearly with the above parameters. It only takes 370 ms when there are 100 attributes in each subset, 10 translating nodes in an access tree, and 100 keywords in the document. In these parameters, the main influencing factors are the number of attributes and the number of keywords, while the number of translating nodes has a certain impact on it.From the above experiments for each algorithm in our scheme, we can conclude that it is an efficient and practical scheme for use in a PHR application.


## 5. Conclusion

In this paper, we present an attribute set-based Boolean keyword search over encrypted PHR. In our scheme, each data user’s attributes are organized as recursive set structure, which enables more flexibility in user attribute organization and more efficiency in specifying policies than the existing ABKS schemes. Meanwhile, all authorized users can perform Boolean keyword search over the encrypted PHR. We have proved the security of our scheme formally. The experimental results show that it is feasible and practical for PHR systems.



---

*Source: 9023141-2021-12-23.xml*