# Fine-Grained Task Access Control System for Mobile Crowdsensing

Authors: Jingwei Wang; Xinchun Yin; Jianting Ning
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Mobile crowdsensing enables people to collect and process a massive amount of information by using social resources without any cost on sensor deployment or model training. Many schemes focusing on the problems of task assignment and privacy preservation have been proposed so far. However, the privacy-preserving of requesters and task access control, which are vital to mobile crowdsensing, is barely considered in the literature. To address the aforementioned issues, a fine-grained task access control system for mobile crowdsensing is proposed. In particular, the requester can decide the group of task performers who can access the task by utilizing attribute-based encryption technology. T he untrusted crowdsensing platform cannot obtain any sensitive information concerning the requester or the task, while the qualified task performers are capable of retrieving tasks within 0.85 ms. Security analysis and experimental results are presented to show the feasibility and efficiency of the proposed system.


---

## Body

## 1. Introduction

The evolution of mobile device promotes a new sensing paradigm called mobile crowdsensing. Integrated with a set of powerful sensors (e.g., camera, recorder, and GPS), the mobile device is capable of collecting different kinds of information for specific purposes [1]. Formally, mobile crowdsensing refers to a group of mobile users being coordinated to perform large-scale sensing tasks over urban environments by using their mobile devices [2]. Figure 1 shows a typical workflow of mobile crowdsensing. As we can see, there are three kinds of participants: the requester, the crowdsensing platform, and the task performer. The process of mobile crowdsensing consists of eight stages: design task, release task, scan task, choose task, resolve task, submit result, accept/refuse, and integration. If a requester wants to launch a task, he needs to submit his requirement about the task to the crowdsensing platform. The task performers in the crowdsensing platform scan the tasks and choose appropriate ones. After accomplishing the task, the task performers submit the results back to the platform, and the requester can decide whether the results are qualified. If yes, all the results are integrated, and the task is finished [3].Figure 1
Workflow of mobile crowdsensing.Due to the convenience of deployment and communication, mobile crowdsensing has been applied in a large number of scenarios such as smart transportation, environmental monitoring, and data labelling [4–7]. Although mobile crowdsensing provides an unprecedented solution for data collecting and processing, it brings many new challenges as well. Privacy preservation is one of the main problems that need to be considered when designing a mobile crowdsensing scheme. Most of the previous studies focus on protecting task performers [8, 9]. That is, they mainly consider how to preserve the privacy of task performers in the stage of submit result. For some specific tasks, the privacy leakage may also occur in the stage of release task since the platform is not fully trusted. The platform may deduce the privacy of requesters according to their tasks. Besides, task access control is another problem that needs to be addressed. In mobile crowdsensing, the tasks are stored on the platform. Anyone in the system can access and accept the task. For the tasks that require users with specific conditions, it may lead to poor quality of task results if task performers are not qualified. Moreover, task access control can efficiently prevent the task information from been obtained by irrelevant entities (e.g., the crowdsensing platform). Thus, task access control is vital to mobile crowdsensing.Attribute-based encryption (ABE) [10–12] is a promising data-sharing tool that provides fine-grained access control over the encrypted data. There are mainly two branches: ciphertext policy ABE (CP-ABE) [11] and key policy ABE (KP-ABE) [10]. In CP-ABE, the user secret key is associated with an attribute set, and the ciphertext is associated with an access policy. Only when the attribute set satisfies the access policy can the ciphertext be decrypted [13]. In KP-ABE, the situation is reversed. The user secret key and ciphertext are associated with an attribute set and access policy, respectively. Apparently, data owners in CP-ABE can decide the access policy, which makes CP-ABE more suitable for mobile crowdsensing. However, there still exist some problems if it is directly used in mobile crowdsensing [14].A Motivating Story. Consider a researcher who would like to collect the heart rate record of people in regionA for research. To achieve the purpose, he decides to issue his requirement to a crowdsensing platform. To encourage task performers in the system, everyone who contributes to this task will get some allowance. The researcher needs to encrypt the task with ABE technology, and the corresponding access policy is {“region A” AND “male”}. Thus, only male users in region A can accept this task. As the platform is not fully trusted, the access policy should not be included in the ciphertext. Otherwise, the platform may deduce the privacy of the researcher or task performers who accepted this task.The crowdsensing platform is public, which contains a variety of task performers. Generally speaking, the more the task performers take part in the task, the better the result is. However, the requester may get a contrary result without a selecting mechanism for task performers. To address this problem, many task allocation algorithms have been proposed [2, 3, 15, 16]. Most of them let the crowdsensing platform perform the task allocation. Since the crowdsensing platform is not fully trusted, it may collect the attributes of the task and thus deduce the privacy of the requester or task performers who are qualified to accept this task. Therefore, we need to design a better solution that achieves fine-grained task access control without loss of confidentiality by using ABE technology. However, the following two issues arise.By employing ABE technology, the content of the task is unknowable to the crowdsensing platform. However, the encrypted information is also difficult for task performers to browse. A task performer may need to download all the ciphertexts and try to decrypt them one by one, which is inefficient especially in the scenario of mobile crowdsensing where the devices are resource-limited [17]. How can we let the task performers get the appropriate tasks efficiently when the tasks are encrypted? Besides, in ABE, the access policy embedded in the ciphertext is sent to the crowdsensing platform. Since it is directly connected to the task, the crowdsensing platform may deduce the privacy of requesters and task performers from it. To protect the content of the ciphertext, ABE schemes supporting hidden access policy are needed.


### 1.1. Contributions

In this paper, we propose a fine-grained task access control system for mobile crowdsensing called FGTAC. The contributions are summarized as follows:(1)
Fine-Grained Task Access Control. Considering the situation that the requester needs to recruit a group of users with specific attributes for his task, a fine-grained task access control mechanism is needed. By employing ABE technology, the tasks are encrypted under the access policy defined by requesters. Only users with appropriate attributes can retrieve the encrypted task. In FGTAC, an AND-gate access policy with a wildcard is employed. Every attribute in the access policy has three kinds of possible values: positive, negative, and wildcard. As a result, the proposed system can achieve both fine-grained access control and flexibility.(2)
Privacy Preservation. One of the main purposes of our system is to preserve the privacy of requesters and task performers. To the best of our knowledge, barely of the existing literature pay attention to preserve the privacy of requesters. However, the crowdsensing platform is not fully trusted. If tasks are sent to the crowdsensing platform without any protection, the crowdsensing platform may deduce the information about requesters and thus threaten their privacy. To address this problem, we employ ABE technology in our system. Nevertheless, the access policy in ABE is sent to the crowdsensing platform together with the ciphertext, which may help the crowdsensing platform deduce the content of the task. Thus, we employ Vie`te’s formulas [18] to hide access policy in the ciphertext.(3)
Task Search. As the tasks are encrypted and the access policies are hidden, the task performers cannot search the tasks as usual [19]. In our FGTAC system, an efficient search function is provided. The keyword is encrypted and stored in the ciphertext. Before the search algorithm is performed, the user keyword is transferred into the trapdoor. As a result, the crowdsensing platform cannot obtain any useful information from it. Moreover, the search algorithm only costs two bilinear pairing operations, which can be performed within 9 ms. The predecryption algorithm is performed once search algorithm finishes.(4)
Ciphertext Predecryption. In the scenario of mobile crowdsensing, devices cannot afford the high computational overhead of bilinear pairing operations. To reduce their computational overhead, we design the function of ciphertext predecryption in FGTAC. On the user side, the decryption algorithm only costs two exponentiation operations in GT, which can be performed efficiently by mobile devices.


### 1.2. Related Works

Task assignment and privacy-preserving are the two main problems in mobile crowdsensing [20, 21]. In task assignment, the crowdsensing platform needs to determine who is suitable to perform the task. To find the appropriate performers, many solutions are proposed in the literature [15, 22, 23]. Wu et al. [15] proposed two approximate task assignment algorithms for sweep coverage. Different from the schemes valuing the point of interest, they designed a model that weighs the quality of coverage from the perspective of the area. In Ref. [22], Karaliopoulos et al. employed opportunistic networking technology in choosing performers for crowdsensing tasks. In Ref. [23], the authors designed a crowdsensing system that mainly considers the location and profits of performers. However, the crowdsensing platform is hard to trust in reality. It may threaten the security of task performers and requesters if the crowdsensing platform obtains private information. Wang et al. [24] enabled the performers to select the personal privacy level so that they do not need to upload their true location to the crowdsensing platform. Ni et al. [16] introduced a strong privacy-preserving scheme for mobile crowdsensing called SPOON. Specifically, proxy re-encryption and BBS + signature are used to protect the tasks and results. Sei et al. [9] proposed a data collecting scheme, which is anonymized, by improving the traditional randomized response scheme. Unfortunately, none of the aforementioned schemes is designed to protect the privacy of requesters. In the workflow of mobile crowdsensing, both the privacy of performers and requests can be obtained by the crowdsensing platform through the task information and thus threaten their security.To handle the problems above, ABE technology, which was firstly proposed by Sahai and Water [25], is a promising tool. As a well-known data-sharing tool, many ABE schemes aiming at settling the challenges of confidentiality and flexibility in data access control have been proposed [26–30]. To enable the users to search on the encrypted files, Sun et al. [26] proposed a fine-grained keyword search scheme. With the technologies of lazy re-encryption and proxy re-encryption, the expensive computation cost of ABE is delegated to other entities. As the access policy may leak the privacy, a partially hidden access policy ABE scheme is proposed in Ref. [27]. The access policy in their scheme only consists of the attribute names, and the corresponding values are not provided. Further in Ref. [28], a fully hidden access policy ABE scheme is introduced. Compared with Ref. [27], the scheme in Ref. [28] is more secure. To handle the expensive computation in ABE, Ning et al. set a secret value for users to protect ciphertexts in Ref. [29]. In the stage of decryption, the cloud server performs the decryption algorithm to generate the transformed ciphertext. The cloud server cannot get any useful information from the transformed ciphertext, while users can retrieve the encrypted data efficiently.


### 1.3. Organization

In Section2, we state the preliminaries, including notations, bilinear map, complexity assumption, Vie`te’s formulas, access structure, and the definition of CP-ABE. The system model, definition, and security model are outlined in Section 3. Section 4 gives detailed construction and the security analysis of FGTAC. Section 5 evaluates the proposed system in terms of feature comparison, theoretical analysis, and experimental analysis. A brief conclusion is presented in Section 6.


## 1.1. Contributions

In this paper, we propose a fine-grained task access control system for mobile crowdsensing called FGTAC. The contributions are summarized as follows:(1)
Fine-Grained Task Access Control. Considering the situation that the requester needs to recruit a group of users with specific attributes for his task, a fine-grained task access control mechanism is needed. By employing ABE technology, the tasks are encrypted under the access policy defined by requesters. Only users with appropriate attributes can retrieve the encrypted task. In FGTAC, an AND-gate access policy with a wildcard is employed. Every attribute in the access policy has three kinds of possible values: positive, negative, and wildcard. As a result, the proposed system can achieve both fine-grained access control and flexibility.(2)
Privacy Preservation. One of the main purposes of our system is to preserve the privacy of requesters and task performers. To the best of our knowledge, barely of the existing literature pay attention to preserve the privacy of requesters. However, the crowdsensing platform is not fully trusted. If tasks are sent to the crowdsensing platform without any protection, the crowdsensing platform may deduce the information about requesters and thus threaten their privacy. To address this problem, we employ ABE technology in our system. Nevertheless, the access policy in ABE is sent to the crowdsensing platform together with the ciphertext, which may help the crowdsensing platform deduce the content of the task. Thus, we employ Vie`te’s formulas [18] to hide access policy in the ciphertext.(3)
Task Search. As the tasks are encrypted and the access policies are hidden, the task performers cannot search the tasks as usual [19]. In our FGTAC system, an efficient search function is provided. The keyword is encrypted and stored in the ciphertext. Before the search algorithm is performed, the user keyword is transferred into the trapdoor. As a result, the crowdsensing platform cannot obtain any useful information from it. Moreover, the search algorithm only costs two bilinear pairing operations, which can be performed within 9 ms. The predecryption algorithm is performed once search algorithm finishes.(4)
Ciphertext Predecryption. In the scenario of mobile crowdsensing, devices cannot afford the high computational overhead of bilinear pairing operations. To reduce their computational overhead, we design the function of ciphertext predecryption in FGTAC. On the user side, the decryption algorithm only costs two exponentiation operations in GT, which can be performed efficiently by mobile devices.


## 1.2. Related Works

Task assignment and privacy-preserving are the two main problems in mobile crowdsensing [20, 21]. In task assignment, the crowdsensing platform needs to determine who is suitable to perform the task. To find the appropriate performers, many solutions are proposed in the literature [15, 22, 23]. Wu et al. [15] proposed two approximate task assignment algorithms for sweep coverage. Different from the schemes valuing the point of interest, they designed a model that weighs the quality of coverage from the perspective of the area. In Ref. [22], Karaliopoulos et al. employed opportunistic networking technology in choosing performers for crowdsensing tasks. In Ref. [23], the authors designed a crowdsensing system that mainly considers the location and profits of performers. However, the crowdsensing platform is hard to trust in reality. It may threaten the security of task performers and requesters if the crowdsensing platform obtains private information. Wang et al. [24] enabled the performers to select the personal privacy level so that they do not need to upload their true location to the crowdsensing platform. Ni et al. [16] introduced a strong privacy-preserving scheme for mobile crowdsensing called SPOON. Specifically, proxy re-encryption and BBS + signature are used to protect the tasks and results. Sei et al. [9] proposed a data collecting scheme, which is anonymized, by improving the traditional randomized response scheme. Unfortunately, none of the aforementioned schemes is designed to protect the privacy of requesters. In the workflow of mobile crowdsensing, both the privacy of performers and requests can be obtained by the crowdsensing platform through the task information and thus threaten their security.To handle the problems above, ABE technology, which was firstly proposed by Sahai and Water [25], is a promising tool. As a well-known data-sharing tool, many ABE schemes aiming at settling the challenges of confidentiality and flexibility in data access control have been proposed [26–30]. To enable the users to search on the encrypted files, Sun et al. [26] proposed a fine-grained keyword search scheme. With the technologies of lazy re-encryption and proxy re-encryption, the expensive computation cost of ABE is delegated to other entities. As the access policy may leak the privacy, a partially hidden access policy ABE scheme is proposed in Ref. [27]. The access policy in their scheme only consists of the attribute names, and the corresponding values are not provided. Further in Ref. [28], a fully hidden access policy ABE scheme is introduced. Compared with Ref. [27], the scheme in Ref. [28] is more secure. To handle the expensive computation in ABE, Ning et al. set a secret value for users to protect ciphertexts in Ref. [29]. In the stage of decryption, the cloud server performs the decryption algorithm to generate the transformed ciphertext. The cloud server cannot get any useful information from the transformed ciphertext, while users can retrieve the encrypted data efficiently.


## 1.3. Organization

In Section2, we state the preliminaries, including notations, bilinear map, complexity assumption, Vie`te’s formulas, access structure, and the definition of CP-ABE. The system model, definition, and security model are outlined in Section 3. Section 4 gives detailed construction and the security analysis of FGTAC. Section 5 evaluates the proposed system in terms of feature comparison, theoretical analysis, and experimental analysis. A brief conclusion is presented in Section 6.


## 2. Preliminaries

### 2.1. Notations

Some frequently used notations are given in Table1.Table 1
Some notations used in this paper.
NotationDescriptionG,GTTwo multiplicative cyclic groups.ℤpGroup of integers modulop.eThe bilinear map:G×G⟶GT.WThe AND-gate access policyW=S1ΛS2Λ⋯ΛSL.SThe attribute setS=S1,S2,…,SL.S⊨WThe attribute setS satisfies the access policy W.aThe number list1,2,…,a.N1,N2,N3The maximum number of wildcards, positive attributes, and negative attributes, respectively.


### 2.2. Bilinear Map

LetG and GT be two cyclic groups with prime order p, g be the generator of G, and e:G×G⟶GT be a bilinear map. e has the following properties:(1)
Bilinearity: ∀x,y∈G and α,β∈ℤp, the equation exα,yβ=ex,yαβ=exβ,yα holds.(2)
Nondegeneracy: eg,g≠1.(3)
Computability: ∀x,y∈G, the computation of bilinear pairing ex,y can be performed efficiently.


### 2.3. Complexity Assumption

We use decisionalq-bilinear Diffie-Hellman inversion (q-BDHI) problem in our scheme. A challenger selects two groups G and GT. Let g be a generator of G and x∈ℤp. Given the tuple y=g,gx,…,gxq as input, it must be difficult for adversaries to distinguish eg,g1/x from R∈GT. An algorithm ℬ has advantage ε in breaking it if Prℬy,eg,g1/x=0−Prℬy,eg,g1/x=0≥ε.Definition 1.
(q-BDHI). The decisional q-BDHI assumption holds if all probabilistic polynomial-time (PPT) algorithms have at most a negligible advantage in breaking it.


### 2.4. Viete’s Formulas

Consider two vectorsv⟶=v1,…,vL and z⟶=z1,…,zL. Vector v⟶ contains both alphabets and wildcards, and vector z⟶ only contains alphabets. Let J=j1,j2,…,jn⊂1,2,…,L denotes the positions of wildcards in vector v⟶. Let ∏j∈Ji−j=∑k=0nλkik, where λk are the coefficients, then we have ∑i=1,i∉JLvi∏j∈Ji−j=∑k=0nλk∑i=1Lziik if vi=zivi=∗ for i∈L. To hide the computation, we can choose a random group element Hi and put vi,zi as the exponents of Hi. Then, the above equation becomes ∏i=1,i∉JLHivi∏j∈Ji−j=∏k=0n∏i=0LHiziik. By using Vie`te’s formulas, we can construct the coefficient λk in aforementioned equation by λn−k=−1k∑1≤i1≤i2≤⋯≤ik≤nji1,ji1,…,ji1,k∈0,n, where n=J.


### 2.5. Access Structure

LetW=S1∧S2∧⋯∧SL be an AND-gate access policy. Every attribute Si has three kinds of states. ‘+’ stands for positive, ‘−’ stands for negative, and ‘∗’ stands for wildcard. If a user wants to join the system. An attribute set S will be assigned to him, where S=S1,S2,…,SL. Similar to the access policy, every attribute has two kinds of states. ‘+’ stands for positive and ‘−’ stands for negative. The notation S⊨W means that S satisfies W.


### 2.6. CP-ABE definition

There are four algorithms in a basic ciphertext policy attribute-based encryption scheme: Setup, KeyGen, Encrypt, and Decrypt.(1)
Setupλ⟶PK,MSK: It takes the secure parameter λ as input and outputs the public key PK and the master secret key MSK.(2)
KeyGenPK,MSK,S⟶SK: It takes PKand MSK and an attribute set S as input and outputs the user secret key SK.(3)
EncryptPK,W,msg⟶CT: It takes PK, an access policy W and a message msg as input and outputs the ciphertext CT.(4)
DecryptPK,SK,CT⟶msg: It takes PK, SK, and CT as input and outputs msg if S⊨W. Otherwise, the algorithm outputs ⊥.


## 2.1. Notations

Some frequently used notations are given in Table1.Table 1
Some notations used in this paper.
NotationDescriptionG,GTTwo multiplicative cyclic groups.ℤpGroup of integers modulop.eThe bilinear map:G×G⟶GT.WThe AND-gate access policyW=S1ΛS2Λ⋯ΛSL.SThe attribute setS=S1,S2,…,SL.S⊨WThe attribute setS satisfies the access policy W.aThe number list1,2,…,a.N1,N2,N3The maximum number of wildcards, positive attributes, and negative attributes, respectively.


## 2.2. Bilinear Map

LetG and GT be two cyclic groups with prime order p, g be the generator of G, and e:G×G⟶GT be a bilinear map. e has the following properties:(1)
Bilinearity: ∀x,y∈G and α,β∈ℤp, the equation exα,yβ=ex,yαβ=exβ,yα holds.(2)
Nondegeneracy: eg,g≠1.(3)
Computability: ∀x,y∈G, the computation of bilinear pairing ex,y can be performed efficiently.


## 2.3. Complexity Assumption

We use decisionalq-bilinear Diffie-Hellman inversion (q-BDHI) problem in our scheme. A challenger selects two groups G and GT. Let g be a generator of G and x∈ℤp. Given the tuple y=g,gx,…,gxq as input, it must be difficult for adversaries to distinguish eg,g1/x from R∈GT. An algorithm ℬ has advantage ε in breaking it if Prℬy,eg,g1/x=0−Prℬy,eg,g1/x=0≥ε.Definition 1.
(q-BDHI). The decisional q-BDHI assumption holds if all probabilistic polynomial-time (PPT) algorithms have at most a negligible advantage in breaking it.


## 2.4. Viete’s Formulas

Consider two vectorsv⟶=v1,…,vL and z⟶=z1,…,zL. Vector v⟶ contains both alphabets and wildcards, and vector z⟶ only contains alphabets. Let J=j1,j2,…,jn⊂1,2,…,L denotes the positions of wildcards in vector v⟶. Let ∏j∈Ji−j=∑k=0nλkik, where λk are the coefficients, then we have ∑i=1,i∉JLvi∏j∈Ji−j=∑k=0nλk∑i=1Lziik if vi=zivi=∗ for i∈L. To hide the computation, we can choose a random group element Hi and put vi,zi as the exponents of Hi. Then, the above equation becomes ∏i=1,i∉JLHivi∏j∈Ji−j=∏k=0n∏i=0LHiziik. By using Vie`te’s formulas, we can construct the coefficient λk in aforementioned equation by λn−k=−1k∑1≤i1≤i2≤⋯≤ik≤nji1,ji1,…,ji1,k∈0,n, where n=J.


## 2.5. Access Structure

LetW=S1∧S2∧⋯∧SL be an AND-gate access policy. Every attribute Si has three kinds of states. ‘+’ stands for positive, ‘−’ stands for negative, and ‘∗’ stands for wildcard. If a user wants to join the system. An attribute set S will be assigned to him, where S=S1,S2,…,SL. Similar to the access policy, every attribute has two kinds of states. ‘+’ stands for positive and ‘−’ stands for negative. The notation S⊨W means that S satisfies W.


## 2.6. CP-ABE definition

There are four algorithms in a basic ciphertext policy attribute-based encryption scheme: Setup, KeyGen, Encrypt, and Decrypt.(1)
Setupλ⟶PK,MSK: It takes the secure parameter λ as input and outputs the public key PK and the master secret key MSK.(2)
KeyGenPK,MSK,S⟶SK: It takes PKand MSK and an attribute set S as input and outputs the user secret key SK.(3)
EncryptPK,W,msg⟶CT: It takes PK, an access policy W and a message msg as input and outputs the ciphertext CT.(4)
DecryptPK,SK,CT⟶msg: It takes PK, SK, and CT as input and outputs msg if S⊨W. Otherwise, the algorithm outputs ⊥.


## 3. System Model and Security

In this section, we give out the system model, definition, and security model of FGTAC.


### 3.1. System Model

In Figure2, we show the system model of FGTAC. It consists of four entities: the key generation center (KGC), the crowdsensing platform, the requester, and task performers.(1)
KGC needs to generate the system parameters and distribute secret keys for task performers in FGTAC. As the core management entity, KGC is trusted by other entities.(2)
Crowdsensing Platform is responsible for storing the tasks and receiving the sensing data. When a task performer queries for a task, the crowdsensing platform will perform the predecryption algorithm to relieve his computational overhead. It is semitrusted in the sense that the crowdsensing platform may collect private information for its own interest.(3)
Requester is the entity that issues crowdsensing tasks via the crowdsensing platform to collect sensing data. Since the requester is able to issue tasks at will, we assume the requester has sufficient computation ability. In addition, the requester may have some special requirements on task performers and do not hope the crowdsensing platform knows the content of his task. Thus, the requester needs to encrypt his tasks with ABE technology.(4)
Task Performers are workers in FGTAC. They would like to accomplish the requesters’ tasks to get the allowance. The tasks are encrypted by ABE technology. All the task performers in the system are assigned a set of attributes. Only task performers whose attribute set satisfies the access policy can retrieve the task in the crowdsensing platform. The task performers are untrusted for they may collude to get the tasks that they are not qualified to obtain.Figure 2
System model of FGTAC.


### 3.2. Definition

According to the system model, the definition of the proposed system is designed as follows:(1)
Setupλ⟶PK,MSK: The setup algorithm is run by KGC. It takes a secure parameter λ as input and outputs the public key PK and the master secret key MSK. KGC keeps MSK private and publishes PK.(2)
UserRegPK⟶UK,USK: The user registration algorithm is run by task performers. It takes PK as input and outputs the user public key UK and the user master secret key USK. The task performers keep USK private and publish UK.(3)
KeyGenPK,MSK,UK,S⟶SK: The key generation algorithm is run by KGC. It takes PK,MSK, and UK, and an attribute set S as input, outputs the user secret key SK. KGC distributes SK to corresponding task performers in the system.(4)
EncryptPK,W,msg,KW⟶CT: The encryption algorithm is run by the requester. It takes PK, an access policy W, a message msg, and the keyword KW defined by the requester as input and outputs the ciphertext CT. Note that all the ciphertexts are transferred to the crowdsensing platform for storage.(5)
TrapdoorPK,KWu⟶td: The trapdoor generation algorithm is run by task performers. It takes PK and the user keyword KWu as input and outputs the trapdoor td.(6)
SearchPK,CT,td⟶1 or 0: The search algorithm is run by the crowdsensing platform. It takes PK, CT, and td as input and outputs 1 if td matches CT. Otherwise, the algorithm outputs 0.(7)
PreDecryptPK,SK,CT⟶preCT or ⊥: The predecryption algorithm is run by the crowdsensing platform. It takes PK, SK and CT as input and outputs the predecrypted ciphertext preCT if the attribute set S in SK satisfies W in CT. Otherwise, the algorithm outputs ⊥.(8)
DecryptPK,preCT,USK⟶msg: The decryption algorithm is run by task performers. It takes PK, preCT, and USK as input and outputs the message msg.


### 3.3. Security Model

According to the system model in Section3.1, we say that KGC is fully trusted, the crowdsensing platform is semitrusted, and requesters and task performers are untrusted. We define the security of FGTAC by the security games as follows:


#### 3.3.1. Chosen-Plaintext Attack Security

The security game of chosen-plaintext attack (CPA) is designed between a challengerC and an active adversary (malicious user) A. The interaction is as follows:Initialization: A declares the challenge access policy W∗, challenge user public key UK∗, and sends them to C.Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. After that, PK is sent to A.Query Phase 1: Let T be an empty set and c=0 be an integer counter. A launches queries as follows:Generate.SKS: C sets c=c+1. It runs the UserReg algorithm to get the tuple of user public key and user secret key UK,USK, and runs the KeyGen algorithm with attribute set S and UK to get the user secret key SK. C stores c,UK,USK,S,SK to T. Besides, the situation that S⊨W∗ is not allowed.Corrupt.SKi: C checks whether T contains i,UK,USK,S,SK. If it is, C returns UK,USK to A. Otherwise, C returns ⊥.Challenge: A declares two equal-length plaintexts m0,m1 and sends them to C. C randomly selects b∈0,1 and runs the Encrypt algorithm to get challenge ciphertext CTb∗. It sends CTb∗ to A.Query Phase 2: A adaptively queries SK as in Query Phase 1.Guess: A outputs a guess b′∈0,1 for b.The probability forA to win the security game is Prb=b′−1/2.Definition 2.
(CPA security). The proposed system is CPA secure if all PPT adversaries have at most a negligible probability in breaking CPA security game.


#### 3.3.2. Chosen Keyword Attack Security

The security game of chosen keyword attack (CKA) is designed between a challengerC and an active adversary (malicious user) A. The interaction is as follows:Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. Then, C returns PK to A.Query Phase 1: Let T1,T2 be two empty sets, c=0 be an integer counter. A launches queries as follows:Generate.TrapdoorKW: C sets c=c+1. It runs the Trapdoor algorithm with keyword KW to get the trapdoor td. C stores c,KW,td to T1.Corrupt.Trapdoori: C checks whether T1 contains i,KW,td. If it is, C returns td to A and sets T2=T2∪KW. Otherwise, C returns ⊥.Challenge: A declares two equal-length keywords kw0,kw1 and sends them to C. Note that kw1,kw2∉T2. C randomly selects b∈0,1 and runs the Encrypt algorithm to get challenge ciphertext CTb∗. It returns CTb∗ to A.Guess: A outputs a guess b′∈0,1 for b.The probability forA to win the security game is Prb=b′−1/2.Definition 3.
(CKA security). The proposed system is CKA secure if all PPT adversaries have at most a negligible probability in breaking CKA security game.


#### 3.3.3. Secret Key Exposure Attack Security

The security game of secret key exposure attack is designed between a challengerC and an active adversary (semitrusted crowdsensing platform) A. The interaction is as follows:Initialization: A declares the challenge access policy W∗ and sends it to C.Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. C returns PK to A.Query Phase 1: Let T1,T2 be two empty sets, c1=0,c2=0 be two integer counters. A launches queries as follows:Generate.SKS: C sets c1=c1+1. It runs the UserReg algorithm to get UK,USK, and runs the KeyGen algorithm with attribute set S and UK to get the secret key SK. It stores c1,UK,USK,S,SK to T1. Besides, the situation that S⊨W∗ is not allowed.Generate.CTW,KW: C sets c2=c2+1. It runs the Encrypt algorithm to get the ciphertext CT. It stores c2,W,KW,CT to T2. Besides, the situation that W=W∗ is not allowed.Corrupti,j: C checks whether T1 contains i,UK,USK,S,SK and T2 contains j,W,KW,CT. If it is, C returns the tuple SK,CT to A. Otherwise, C returns ⊥.PreDecryptSK,CT: A runs the PreDecrypt algorithm to get the predecrypted ciphertext preCT.Challenge: A declares two equal-length plaintexts m0,m1 to C. C randomly selects b∈0,1 and runs the Encrypt algorithm to get ciphertext CTb∗. C runs the UserReg algorithm and KeyGen algorithm to get SK. It sends SK,CTb∗ to A, and A performs PreDecrypt algorithm to get the challenge predecrypted ciphertext preCTb.Query Phase 2: A adaptively queries SK andCT as in Query Phase 1.Guess: A outputs a guess b′∈0,1 for b.The probability forA to win the security game is Prb=b′−1/2.Definition 4.
(Secret key exposure attack security). The proposed system is secure against secret key exposure attack if all PPT adversaries have at most a negligible probability in breaking the secret key exposure attack security game.


#### 3.3.4. Collude Attack Security

The security game of collude attack is designed between a challengerC and an active adversary (malicious user) A. The interaction is as follows:Initialization: A declares the challenge access policy W∗ and sends it to C.Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. C returns PK to A.Query Phase: Let T be an empty set, c=0 be an integer counter. A launches queries as follows:Generate.SKS: C sets c=c+1. It runs the UserReg algorithm to get the tuple of user public key and user secret key UK,USK, and runs the KeyGen algorithm with attribute set S and UK to get the user secret key SK. C stores c,UK,USK,S,SK to T. Besides, the situation that S⊨W∗ is not allowed.Corrupt.SKi: C checks whether T contains i,UK,USK,S,SK. If it is, C returns UK,USK to A. Otherwise, C returns ⊥.Forgery: A output a forged secret key for the challenge access policy W∗.Definition 5.
(Collude attack security). The proposed system is collude attack secure if all PPT adversaries have at most a negligible probability in breaking the collude attack security game.


## 3.1. System Model

In Figure2, we show the system model of FGTAC. It consists of four entities: the key generation center (KGC), the crowdsensing platform, the requester, and task performers.(1)
KGC needs to generate the system parameters and distribute secret keys for task performers in FGTAC. As the core management entity, KGC is trusted by other entities.(2)
Crowdsensing Platform is responsible for storing the tasks and receiving the sensing data. When a task performer queries for a task, the crowdsensing platform will perform the predecryption algorithm to relieve his computational overhead. It is semitrusted in the sense that the crowdsensing platform may collect private information for its own interest.(3)
Requester is the entity that issues crowdsensing tasks via the crowdsensing platform to collect sensing data. Since the requester is able to issue tasks at will, we assume the requester has sufficient computation ability. In addition, the requester may have some special requirements on task performers and do not hope the crowdsensing platform knows the content of his task. Thus, the requester needs to encrypt his tasks with ABE technology.(4)
Task Performers are workers in FGTAC. They would like to accomplish the requesters’ tasks to get the allowance. The tasks are encrypted by ABE technology. All the task performers in the system are assigned a set of attributes. Only task performers whose attribute set satisfies the access policy can retrieve the task in the crowdsensing platform. The task performers are untrusted for they may collude to get the tasks that they are not qualified to obtain.Figure 2
System model of FGTAC.


## 3.2. Definition

According to the system model, the definition of the proposed system is designed as follows:(1)
Setupλ⟶PK,MSK: The setup algorithm is run by KGC. It takes a secure parameter λ as input and outputs the public key PK and the master secret key MSK. KGC keeps MSK private and publishes PK.(2)
UserRegPK⟶UK,USK: The user registration algorithm is run by task performers. It takes PK as input and outputs the user public key UK and the user master secret key USK. The task performers keep USK private and publish UK.(3)
KeyGenPK,MSK,UK,S⟶SK: The key generation algorithm is run by KGC. It takes PK,MSK, and UK, and an attribute set S as input, outputs the user secret key SK. KGC distributes SK to corresponding task performers in the system.(4)
EncryptPK,W,msg,KW⟶CT: The encryption algorithm is run by the requester. It takes PK, an access policy W, a message msg, and the keyword KW defined by the requester as input and outputs the ciphertext CT. Note that all the ciphertexts are transferred to the crowdsensing platform for storage.(5)
TrapdoorPK,KWu⟶td: The trapdoor generation algorithm is run by task performers. It takes PK and the user keyword KWu as input and outputs the trapdoor td.(6)
SearchPK,CT,td⟶1 or 0: The search algorithm is run by the crowdsensing platform. It takes PK, CT, and td as input and outputs 1 if td matches CT. Otherwise, the algorithm outputs 0.(7)
PreDecryptPK,SK,CT⟶preCT or ⊥: The predecryption algorithm is run by the crowdsensing platform. It takes PK, SK and CT as input and outputs the predecrypted ciphertext preCT if the attribute set S in SK satisfies W in CT. Otherwise, the algorithm outputs ⊥.(8)
DecryptPK,preCT,USK⟶msg: The decryption algorithm is run by task performers. It takes PK, preCT, and USK as input and outputs the message msg.


## 3.3. Security Model

According to the system model in Section3.1, we say that KGC is fully trusted, the crowdsensing platform is semitrusted, and requesters and task performers are untrusted. We define the security of FGTAC by the security games as follows:


### 3.3.1. Chosen-Plaintext Attack Security

The security game of chosen-plaintext attack (CPA) is designed between a challengerC and an active adversary (malicious user) A. The interaction is as follows:Initialization: A declares the challenge access policy W∗, challenge user public key UK∗, and sends them to C.Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. After that, PK is sent to A.Query Phase 1: Let T be an empty set and c=0 be an integer counter. A launches queries as follows:Generate.SKS: C sets c=c+1. It runs the UserReg algorithm to get the tuple of user public key and user secret key UK,USK, and runs the KeyGen algorithm with attribute set S and UK to get the user secret key SK. C stores c,UK,USK,S,SK to T. Besides, the situation that S⊨W∗ is not allowed.Corrupt.SKi: C checks whether T contains i,UK,USK,S,SK. If it is, C returns UK,USK to A. Otherwise, C returns ⊥.Challenge: A declares two equal-length plaintexts m0,m1 and sends them to C. C randomly selects b∈0,1 and runs the Encrypt algorithm to get challenge ciphertext CTb∗. It sends CTb∗ to A.Query Phase 2: A adaptively queries SK as in Query Phase 1.Guess: A outputs a guess b′∈0,1 for b.The probability forA to win the security game is Prb=b′−1/2.Definition 2.
(CPA security). The proposed system is CPA secure if all PPT adversaries have at most a negligible probability in breaking CPA security game.


### 3.3.2. Chosen Keyword Attack Security

The security game of chosen keyword attack (CKA) is designed between a challengerC and an active adversary (malicious user) A. The interaction is as follows:Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. Then, C returns PK to A.Query Phase 1: Let T1,T2 be two empty sets, c=0 be an integer counter. A launches queries as follows:Generate.TrapdoorKW: C sets c=c+1. It runs the Trapdoor algorithm with keyword KW to get the trapdoor td. C stores c,KW,td to T1.Corrupt.Trapdoori: C checks whether T1 contains i,KW,td. If it is, C returns td to A and sets T2=T2∪KW. Otherwise, C returns ⊥.Challenge: A declares two equal-length keywords kw0,kw1 and sends them to C. Note that kw1,kw2∉T2. C randomly selects b∈0,1 and runs the Encrypt algorithm to get challenge ciphertext CTb∗. It returns CTb∗ to A.Guess: A outputs a guess b′∈0,1 for b.The probability forA to win the security game is Prb=b′−1/2.Definition 3.
(CKA security). The proposed system is CKA secure if all PPT adversaries have at most a negligible probability in breaking CKA security game.


### 3.3.3. Secret Key Exposure Attack Security

The security game of secret key exposure attack is designed between a challengerC and an active adversary (semitrusted crowdsensing platform) A. The interaction is as follows:Initialization: A declares the challenge access policy W∗ and sends it to C.Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. C returns PK to A.Query Phase 1: Let T1,T2 be two empty sets, c1=0,c2=0 be two integer counters. A launches queries as follows:Generate.SKS: C sets c1=c1+1. It runs the UserReg algorithm to get UK,USK, and runs the KeyGen algorithm with attribute set S and UK to get the secret key SK. It stores c1,UK,USK,S,SK to T1. Besides, the situation that S⊨W∗ is not allowed.Generate.CTW,KW: C sets c2=c2+1. It runs the Encrypt algorithm to get the ciphertext CT. It stores c2,W,KW,CT to T2. Besides, the situation that W=W∗ is not allowed.Corrupti,j: C checks whether T1 contains i,UK,USK,S,SK and T2 contains j,W,KW,CT. If it is, C returns the tuple SK,CT to A. Otherwise, C returns ⊥.PreDecryptSK,CT: A runs the PreDecrypt algorithm to get the predecrypted ciphertext preCT.Challenge: A declares two equal-length plaintexts m0,m1 to C. C randomly selects b∈0,1 and runs the Encrypt algorithm to get ciphertext CTb∗. C runs the UserReg algorithm and KeyGen algorithm to get SK. It sends SK,CTb∗ to A, and A performs PreDecrypt algorithm to get the challenge predecrypted ciphertext preCTb.Query Phase 2: A adaptively queries SK andCT as in Query Phase 1.Guess: A outputs a guess b′∈0,1 for b.The probability forA to win the security game is Prb=b′−1/2.Definition 4.
(Secret key exposure attack security). The proposed system is secure against secret key exposure attack if all PPT adversaries have at most a negligible probability in breaking the secret key exposure attack security game.


### 3.3.4. Collude Attack Security

The security game of collude attack is designed between a challengerC and an active adversary (malicious user) A. The interaction is as follows:Initialization: A declares the challenge access policy W∗ and sends it to C.Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. C returns PK to A.Query Phase: Let T be an empty set, c=0 be an integer counter. A launches queries as follows:Generate.SKS: C sets c=c+1. It runs the UserReg algorithm to get the tuple of user public key and user secret key UK,USK, and runs the KeyGen algorithm with attribute set S and UK to get the user secret key SK. C stores c,UK,USK,S,SK to T. Besides, the situation that S⊨W∗ is not allowed.Corrupt.SKi: C checks whether T contains i,UK,USK,S,SK. If it is, C returns UK,USK to A. Otherwise, C returns ⊥.Forgery: A output a forged secret key for the challenge access policy W∗.Definition 5.
(Collude attack security). The proposed system is collude attack secure if all PPT adversaries have at most a negligible probability in breaking the collude attack security game.


## 3.3.1. Chosen-Plaintext Attack Security

The security game of chosen-plaintext attack (CPA) is designed between a challengerC and an active adversary (malicious user) A. The interaction is as follows:Initialization: A declares the challenge access policy W∗, challenge user public key UK∗, and sends them to C.Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. After that, PK is sent to A.Query Phase 1: Let T be an empty set and c=0 be an integer counter. A launches queries as follows:Generate.SKS: C sets c=c+1. It runs the UserReg algorithm to get the tuple of user public key and user secret key UK,USK, and runs the KeyGen algorithm with attribute set S and UK to get the user secret key SK. C stores c,UK,USK,S,SK to T. Besides, the situation that S⊨W∗ is not allowed.Corrupt.SKi: C checks whether T contains i,UK,USK,S,SK. If it is, C returns UK,USK to A. Otherwise, C returns ⊥.Challenge: A declares two equal-length plaintexts m0,m1 and sends them to C. C randomly selects b∈0,1 and runs the Encrypt algorithm to get challenge ciphertext CTb∗. It sends CTb∗ to A.Query Phase 2: A adaptively queries SK as in Query Phase 1.Guess: A outputs a guess b′∈0,1 for b.The probability forA to win the security game is Prb=b′−1/2.Definition 2.
(CPA security). The proposed system is CPA secure if all PPT adversaries have at most a negligible probability in breaking CPA security game.


## 3.3.2. Chosen Keyword Attack Security

The security game of chosen keyword attack (CKA) is designed between a challengerC and an active adversary (malicious user) A. The interaction is as follows:Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. Then, C returns PK to A.Query Phase 1: Let T1,T2 be two empty sets, c=0 be an integer counter. A launches queries as follows:Generate.TrapdoorKW: C sets c=c+1. It runs the Trapdoor algorithm with keyword KW to get the trapdoor td. C stores c,KW,td to T1.Corrupt.Trapdoori: C checks whether T1 contains i,KW,td. If it is, C returns td to A and sets T2=T2∪KW. Otherwise, C returns ⊥.Challenge: A declares two equal-length keywords kw0,kw1 and sends them to C. Note that kw1,kw2∉T2. C randomly selects b∈0,1 and runs the Encrypt algorithm to get challenge ciphertext CTb∗. It returns CTb∗ to A.Guess: A outputs a guess b′∈0,1 for b.The probability forA to win the security game is Prb=b′−1/2.Definition 3.
(CKA security). The proposed system is CKA secure if all PPT adversaries have at most a negligible probability in breaking CKA security game.


## 3.3.3. Secret Key Exposure Attack Security

The security game of secret key exposure attack is designed between a challengerC and an active adversary (semitrusted crowdsensing platform) A. The interaction is as follows:Initialization: A declares the challenge access policy W∗ and sends it to C.Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. C returns PK to A.Query Phase 1: Let T1,T2 be two empty sets, c1=0,c2=0 be two integer counters. A launches queries as follows:Generate.SKS: C sets c1=c1+1. It runs the UserReg algorithm to get UK,USK, and runs the KeyGen algorithm with attribute set S and UK to get the secret key SK. It stores c1,UK,USK,S,SK to T1. Besides, the situation that S⊨W∗ is not allowed.Generate.CTW,KW: C sets c2=c2+1. It runs the Encrypt algorithm to get the ciphertext CT. It stores c2,W,KW,CT to T2. Besides, the situation that W=W∗ is not allowed.Corrupti,j: C checks whether T1 contains i,UK,USK,S,SK and T2 contains j,W,KW,CT. If it is, C returns the tuple SK,CT to A. Otherwise, C returns ⊥.PreDecryptSK,CT: A runs the PreDecrypt algorithm to get the predecrypted ciphertext preCT.Challenge: A declares two equal-length plaintexts m0,m1 to C. C randomly selects b∈0,1 and runs the Encrypt algorithm to get ciphertext CTb∗. C runs the UserReg algorithm and KeyGen algorithm to get SK. It sends SK,CTb∗ to A, and A performs PreDecrypt algorithm to get the challenge predecrypted ciphertext preCTb.Query Phase 2: A adaptively queries SK andCT as in Query Phase 1.Guess: A outputs a guess b′∈0,1 for b.The probability forA to win the security game is Prb=b′−1/2.Definition 4.
(Secret key exposure attack security). The proposed system is secure against secret key exposure attack if all PPT adversaries have at most a negligible probability in breaking the secret key exposure attack security game.


## 3.3.4. Collude Attack Security

The security game of collude attack is designed between a challengerC and an active adversary (malicious user) A. The interaction is as follows:Initialization: A declares the challenge access policy W∗ and sends it to C.Setup: C first runs the Setup algorithm to get the public key PK and the master secret key MSK. C returns PK to A.Query Phase: Let T be an empty set, c=0 be an integer counter. A launches queries as follows:Generate.SKS: C sets c=c+1. It runs the UserReg algorithm to get the tuple of user public key and user secret key UK,USK, and runs the KeyGen algorithm with attribute set S and UK to get the user secret key SK. C stores c,UK,USK,S,SK to T. Besides, the situation that S⊨W∗ is not allowed.Corrupt.SKi: C checks whether T contains i,UK,USK,S,SK. If it is, C returns UK,USK to A. Otherwise, C returns ⊥.Forgery: A output a forged secret key for the challenge access policy W∗.Definition 5.
(Collude attack security). The proposed system is collude attack secure if all PPT adversaries have at most a negligible probability in breaking the collude attack security game.


## 4. The Proposed System

### 4.1. Construction

The attribute universe containsL attributes. For each of the attributes, there are three kinds of states. ‘+’ stands for positive, ‘−’ stands for negative, and ‘∗’ stands for wildcard. Let N1,N2,andN3 be the three upper bounds defined as follows: N1 is the maximum number of the wildcard N1≤L; N2 is the maximum number of positive attributes N2≤L; N3 is the maximum number of negative attributes N3≤L. The detailed construction of the proposed system consists of the following eight algorithms:Setupλ⟶PK,MSK. The setup algorithm is run by KGC. It takes secure parameter λ as input, generates a bilinear pairing group G,GT,p,e and sets n=N1+3. It randomly selects g,h,v,w∈G,α∈ℤp. For ∀i∈n, the algorithm selects ri,ui,ti∈ℤp randomly and calculates Ri=gri,Ui=gui,Ti=vti,Ti′=gti and Y=eg,gα. H:0,1∗⟶ℤp is a hash function. The public key PK and the master secret key MSK are set as(1)PK=G,GT,p,e,g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H,MSK=α,ri,ui,tii∈n.UserRegPK⟶UK,USK. The user registration algorithm is run by task performers in system. A task performer randomly selects β∈ℤp and calculates gβ. The user public key UK and the user master secret key USK are set as(2)UK=gβ,USK=β.KeyGenPK,MSK,UK,S⟶SK : The key generation algorithm is run by KGC. A task performer needs to submit his attribute set S to KGC to get his user secret key. Let the attribute set contains s2 positive attributes and s3 negative attributes. V=v1,v2,…,vs2 and Z=z1,z2,…,zs3 represent the positions of positive attributes and negative attributes, respectively. According to Vie`te’s formulas, for the positive attribute position set V and negative attribute position Z, it sets(3)vk=−∑i∈Vik,k∈0,N1,zk=+∑i∈Vik,k∈0,N1.The algorithm creates vectorsxV⟶ and xZ⟶ as(4)xV⟶=v0,v1,…,vN1,1,0,12,xZ⟶=z0,z1,…,zN1,0,1,12.The key generation algorithm randomly selectsr∈Zp, and computes K0=UKαw1/r. For ∀i∈n, it sets Ki,1=gxVi⟶/r, Ki,1′=gxZi⟶/r, Ki,2=Ri−ti, and Ki,3=Uihriv−xVi⟶+xZi⟶/r. The user secret key is set as follows:(5)SK=K0,Ki,1,Ki,1′,Ki,2,Ki,3i∈n.EncryptPK,W,msg,KW⟶CT: The encryption algorithm is run by the requester. Let the access policy W contains w1 wildcards, w2 positive attributes and w3 negative attributes. J′=j1′,j2′,…,jw1′, V′=v1′,v2′,…,vw2′, and Z′=z1′,z2′,…,zw3′ represent the positions where ‘∗’, ‘+’, and ‘−’ attributes are, respectively. According to Vie`te’s formulas, the algorithm computes the coefficients akk∈0,n1 as(6)an1=1,an1−1=−j1′+j2′+⋯+jn1′,an1−2=j1′j2′+j1′j3′+⋯+jn1−1′jn1′,…a0=−j1′,j2′,…,jn1′.It computes as follows:(7)ΠV′=+∑i∈V′∏jk∈J′i−jk,ΠZ′=+∑i∈Z′∏jk∈J′i−jk.The vectorv⟶ is set as(8)v⟶=a0,a1,…,an1,0n1+1,…,0N1,ΠV′,ΠZ′,1.The encryption algorithm randomly selectss∈Zp and computes C=msgY1/s,C0=g1/s. For ∀i∈n, it computes Ci,1=wv⟶Ti, Ci,2=Uih, and C3,i=Ti′. According to the keyword KW, the algorithm calculates C4=hHKW/s The ciphertext CT is set as follows:(9)CT=C,C0,Ci,1,Ci,2,Ci,3i∈n,C4.TrapdoorPK,KWu⟶td: The trapdoor generation algorithm is run by task performers. The trapdoor is used to search the tasks about the keyword KWu specified by task performers. The algorithm randomly selects t∈ℤp and computes TD1=gt, and TD2=hHKWut. The trapdoor is set as follows:(10)td=TD1,TD2.SearchPK,CT,td⟶1 or 0: The search algorithm is run by the crowdsensing platform. On receiving td, the crowdsensing platform checks if eC0,TD2=eC4,TD1 holds. If yes, the crowdsensing platform performs the PreDecrypt algorithm.PreDecryptPK,SK,CT⟶preCT or ⊥: The predecryption algorithm is run by the crowdsensing platform. If S embedded in SK satisfies the W inCT, the algorithm returns the predecrypted ciphertext preCT. Otherwise, it returns ⊥. The computing process is as follows:(11)P=∏i=1neCi,1,Ki,1eCi,1,Ki,1′eCi,2,Ki,2eCi,3,Ki,3,preCT=eC0,K0P.DecryptPK,preCT,USK⟶msg: The decryption algorithm is run by task performers. To retrieve the predecrypted ciphertext preCT, the algorithm performs the following operations:(12)msg=CpreCT1/β.Note that the proposed system supports multikeyword search ifKW in Encrypt and KWu in Trapdoor consist of a set of keywords.


### 4.2. Security Analysis

#### 4.2.1. Chosen-Plaintext Attack Security

Theorem 1.
The proposed system is chosen-plaintext attack secure for PPT adversaries (malicious users).Proof.
LetA be a PPT adversary who attacks the FGTAC system. The security game is played between A and a simulator ℬ as follows:Initialization: A declares the challenge access policy W∗, challenge user public key UK∗=gβ1, and sends them to ℬ.Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈ℤp. Then, it selects ri,ui,ti∈ℤp and calculates Ri=gri,Ui=gui,Ti=vti,andTi′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H and the master secret key is MSK=α,ri,ui,tii∈n. PK is sent to A.Query Phase 1: Let T be an empty set, c=0 be an integer counter. A launches queries as follows:Generate.SKS: ℬ sets c=c+1. It runs the UserReg algorithm to generate UK=gβ and USK=β. Then, ℬ runs the KeyGen algorithm to get the corresponding user secret key SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n according to the attribute set S and UK. It stores c,UK,USK,S,SK to T. Besides, the situation that S⊨W∗ is not allowed.Corrupt.SKi: ℬ checks whether T contains i,UK,USK,S,SK. If it is, ℬ sends UK,USK to A. Otherwise, ℬ returns ⊥.Challenge: A declares two equal-length plaintexts m0,m1 and sends them to ℬ. ℬ randomly selects b∈0,1 and runs the Encrypt algorithm to get challenge ciphertext CTb∗=C=mbY1/s,C0=g1/s,Ci,1=wv⟶Ti,Ci,2=Uih,C3,i=Ti′i∈n. It sends CTb∗ to A.Query Phase 2: A adaptively queries SK as in Query Phase 1.Guess: A outputs a guess b′∈0,1 for b.
A wins the game if b′ is the same as b. Since the distribution of PK, UK, SK, and CT are identical to that in the real world, the advantage of the adversary to win this game is ignorable.


#### 4.2.2. Chosen Keyword Attack Security

Theorem 2.
The proposed system is chosen keyword attack secure for PPT adversaries (malicious users).Proof.
LetA be a PPT adversary who attacks FGTAC system. The security game is played between A and a simulator ℬ as follows:Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈ℤp. Then, it selects ri,ui,ti∈ℤp and calculates Ri=gri,Ui=gui,Ti=vti,andTi′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H and the master secret key is MSK=α,ri,ui,tii∈n. Then, ℬ returns PK to A.Query Phase 1: Let T1,T2 be two empty sets, c=0 be an integer counter. A launches queries as follows:Generate.TrapdoorKW: ℬ sets c=c+1. It randomly selects t∈Zp and computes TD1=gt and TD2=hHKWut.td is set as TD1,TD2. ℬ stores c,KW,td to T1.Corrupt.Trapdoori: ℬ checks whether T1 contains i,KW,td. If it is, ℬ returns td to A and sets T2=T2∪KW. Otherwise, ℬ returns ⊥.Query Phase 2: A adaptively queries td as in Query Phase 1.Challenge: A declares two equal-length keywords kw0,kw1 and sends them to ℬ. Note that kw0,kw1∉T2. ℬ randomly selects b∈0,1 and runs the Encrypt algorithm to select s∈Zp and get the challenge ciphertext CTb∗=C=Y1/s,C4=hHKWb/s to A.Guess: A outputs a guess b′∈0,1 for b.
A wins the game if b′ is the same as b. Since the distribution of PK, td, and CT are identical to that in the real world, the advantage of adversary to win this game is ignorable.


#### 4.2.3. Secret Key Exposure Attack Security

Theorem 3.
The proposed system is secret key exposure attack secure for a PPT adversary (semitrusted crowdsensing platform).Proof.
LetA be a PPT adversary who attacks the FGTAC system. The security game is played between A and a simulator ℬ as follows:Initialization: The adversary A declares the challenge access policy W∗ and sends it to ℬ.Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈Zp. Then it selects ri,ui,ti∈Zp and calculates Ri=gri,Ui=gui,Ti=vti,Ti′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H and the master secret key is MSK=α,ri,ui,tii∈n. Then, ℬ sends PK to A.Query Phase 1: Let T1andT2 be two empty sets, c1=0andc2=0 be two integer counters. A launches queries as follows:Generate.SKS: ℬ sets c1=c1+1. It runs the UserReg algorithm to get the user public key UK=gβ and the user secret key USK=β. Then, ℬ runs the KeyGen algorithm to get the corresponding user secret key SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n according to the attribute set S and UK. It stores c1,UK,USK,S,SK to T1. Besides, the situation that S⊨W∗ is not allowed.Generate.CTW,KW: ℬ sets c2=c2+1. It runs the Encrypt algorithm to get the ciphertext CT=C=msgY1/s,C0=g1/s,Ci,1=wv⟶Ti,Ci,2=Uih,Ci,3=Ti′i∈n,C4=hHKW/s. It stores c2,W,KW,CT to T2. Besides, the situation that the access policy W=W∗ is not allowed.Corrupti,j: ℬ checks whether T1 contains i,UK,USK,S,SK and T2 contains j,W,KW,CT. If it is, ℬ returns the tuple SK,CT to A. Otherwise, ℬ returns ⊥.PreDecryptSK,CT: A runs the PreDecrypt algorithm to compute P=∏i=1neCi,1,Ki,1eCi,1,Ki,1′eCi,2,Ki,2eCi,3,Ki,3 and set the predecrypted ciphertext preCT=eC0,K0/P.Challenge: A declares two equal-length plaintexts m0,m1 and sends them to ℬ. ℬ randomly selects b∈0,1 and runs the Encrypt algorithm to get CTb∗=C=mbY1/s,C0=g1/s,Ci,1=wv⟶Ti,Ci,2=Uih,Ci,3=Ti′i∈n. ℬ runs the UserReg algorithm and KeyGen algorithm to get SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n. ℬ sends SK,CTb∗ to A, and A performs PreDecrypt algorithm to get the challenge predecrypted ciphertext preCT=eC0,K0/P.Query Phase 2: A adaptively queries SK and CT as in phase 1.Guess: A outputs a guess b′∈0,1 for b.
A wins the game if b′ is the same as b. Since the distribution of PK, SK, UK, and CT are identical to that in the real world, the ciphertext is protected by the USK and the adversary A cannot obtain any sensitive information.


#### 4.2.4. Collude Attack Security

Theorem 4.
The proposed system is colluding attack secure for PPT adversaries (malicious users).Proof.
LetA be a PPT adversary who attacks the FGTAC system. The security game is played between A and a simulator ℬ as follows:Initialization: A declares the challenge access policy W∗ and challenge user public key UK∗=gβ1 and sends them to ℬ.Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈Zp. Then, it selects ri,ui,ti∈Zp and calculates Ri=gri,Ui=gui,Ti=vti,Ti′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H, and the master secret key is MSK=α,ri,ui,tii∈n. After thatPK is sent to A.Query Phase: Let T be an empty set, c=0 be an integer counter. A launches queries as follows:Generate.SK(S): C sets c=c+1. It runs the UserReg algorithm to generate and . Then, runs the KeyGen algorithm to get the corresponding user secret key SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n according to the attribute set and . It stores to . Besides, the situation that is not allowed.Corrupt.SK (i): checks whether contains . If it is, sends to . Otherwise, returns .Forgery: output a forged secret key for the challenge access policy .
wins the game if the forged secret key is valid. Since all the secret keys in are randomized by the random number . The advantage for the adversary to forge a valid secret key is ignorable.


## 4.1. Construction

The attribute universe containsL attributes. For each of the attributes, there are three kinds of states. ‘+’ stands for positive, ‘−’ stands for negative, and ‘∗’ stands for wildcard. Let N1,N2,andN3 be the three upper bounds defined as follows: N1 is the maximum number of the wildcard N1≤L; N2 is the maximum number of positive attributes N2≤L; N3 is the maximum number of negative attributes N3≤L. The detailed construction of the proposed system consists of the following eight algorithms:Setupλ⟶PK,MSK. The setup algorithm is run by KGC. It takes secure parameter λ as input, generates a bilinear pairing group G,GT,p,e and sets n=N1+3. It randomly selects g,h,v,w∈G,α∈ℤp. For ∀i∈n, the algorithm selects ri,ui,ti∈ℤp randomly and calculates Ri=gri,Ui=gui,Ti=vti,Ti′=gti and Y=eg,gα. H:0,1∗⟶ℤp is a hash function. The public key PK and the master secret key MSK are set as(1)PK=G,GT,p,e,g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H,MSK=α,ri,ui,tii∈n.UserRegPK⟶UK,USK. The user registration algorithm is run by task performers in system. A task performer randomly selects β∈ℤp and calculates gβ. The user public key UK and the user master secret key USK are set as(2)UK=gβ,USK=β.KeyGenPK,MSK,UK,S⟶SK : The key generation algorithm is run by KGC. A task performer needs to submit his attribute set S to KGC to get his user secret key. Let the attribute set contains s2 positive attributes and s3 negative attributes. V=v1,v2,…,vs2 and Z=z1,z2,…,zs3 represent the positions of positive attributes and negative attributes, respectively. According to Vie`te’s formulas, for the positive attribute position set V and negative attribute position Z, it sets(3)vk=−∑i∈Vik,k∈0,N1,zk=+∑i∈Vik,k∈0,N1.The algorithm creates vectorsxV⟶ and xZ⟶ as(4)xV⟶=v0,v1,…,vN1,1,0,12,xZ⟶=z0,z1,…,zN1,0,1,12.The key generation algorithm randomly selectsr∈Zp, and computes K0=UKαw1/r. For ∀i∈n, it sets Ki,1=gxVi⟶/r, Ki,1′=gxZi⟶/r, Ki,2=Ri−ti, and Ki,3=Uihriv−xVi⟶+xZi⟶/r. The user secret key is set as follows:(5)SK=K0,Ki,1,Ki,1′,Ki,2,Ki,3i∈n.EncryptPK,W,msg,KW⟶CT: The encryption algorithm is run by the requester. Let the access policy W contains w1 wildcards, w2 positive attributes and w3 negative attributes. J′=j1′,j2′,…,jw1′, V′=v1′,v2′,…,vw2′, and Z′=z1′,z2′,…,zw3′ represent the positions where ‘∗’, ‘+’, and ‘−’ attributes are, respectively. According to Vie`te’s formulas, the algorithm computes the coefficients akk∈0,n1 as(6)an1=1,an1−1=−j1′+j2′+⋯+jn1′,an1−2=j1′j2′+j1′j3′+⋯+jn1−1′jn1′,…a0=−j1′,j2′,…,jn1′.It computes as follows:(7)ΠV′=+∑i∈V′∏jk∈J′i−jk,ΠZ′=+∑i∈Z′∏jk∈J′i−jk.The vectorv⟶ is set as(8)v⟶=a0,a1,…,an1,0n1+1,…,0N1,ΠV′,ΠZ′,1.The encryption algorithm randomly selectss∈Zp and computes C=msgY1/s,C0=g1/s. For ∀i∈n, it computes Ci,1=wv⟶Ti, Ci,2=Uih, and C3,i=Ti′. According to the keyword KW, the algorithm calculates C4=hHKW/s The ciphertext CT is set as follows:(9)CT=C,C0,Ci,1,Ci,2,Ci,3i∈n,C4.TrapdoorPK,KWu⟶td: The trapdoor generation algorithm is run by task performers. The trapdoor is used to search the tasks about the keyword KWu specified by task performers. The algorithm randomly selects t∈ℤp and computes TD1=gt, and TD2=hHKWut. The trapdoor is set as follows:(10)td=TD1,TD2.SearchPK,CT,td⟶1 or 0: The search algorithm is run by the crowdsensing platform. On receiving td, the crowdsensing platform checks if eC0,TD2=eC4,TD1 holds. If yes, the crowdsensing platform performs the PreDecrypt algorithm.PreDecryptPK,SK,CT⟶preCT or ⊥: The predecryption algorithm is run by the crowdsensing platform. If S embedded in SK satisfies the W inCT, the algorithm returns the predecrypted ciphertext preCT. Otherwise, it returns ⊥. The computing process is as follows:(11)P=∏i=1neCi,1,Ki,1eCi,1,Ki,1′eCi,2,Ki,2eCi,3,Ki,3,preCT=eC0,K0P.DecryptPK,preCT,USK⟶msg: The decryption algorithm is run by task performers. To retrieve the predecrypted ciphertext preCT, the algorithm performs the following operations:(12)msg=CpreCT1/β.Note that the proposed system supports multikeyword search ifKW in Encrypt and KWu in Trapdoor consist of a set of keywords.


## 4.2. Security Analysis

### 4.2.1. Chosen-Plaintext Attack Security

Theorem 1.
The proposed system is chosen-plaintext attack secure for PPT adversaries (malicious users).Proof.
LetA be a PPT adversary who attacks the FGTAC system. The security game is played between A and a simulator ℬ as follows:Initialization: A declares the challenge access policy W∗, challenge user public key UK∗=gβ1, and sends them to ℬ.Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈ℤp. Then, it selects ri,ui,ti∈ℤp and calculates Ri=gri,Ui=gui,Ti=vti,andTi′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H and the master secret key is MSK=α,ri,ui,tii∈n. PK is sent to A.Query Phase 1: Let T be an empty set, c=0 be an integer counter. A launches queries as follows:Generate.SKS: ℬ sets c=c+1. It runs the UserReg algorithm to generate UK=gβ and USK=β. Then, ℬ runs the KeyGen algorithm to get the corresponding user secret key SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n according to the attribute set S and UK. It stores c,UK,USK,S,SK to T. Besides, the situation that S⊨W∗ is not allowed.Corrupt.SKi: ℬ checks whether T contains i,UK,USK,S,SK. If it is, ℬ sends UK,USK to A. Otherwise, ℬ returns ⊥.Challenge: A declares two equal-length plaintexts m0,m1 and sends them to ℬ. ℬ randomly selects b∈0,1 and runs the Encrypt algorithm to get challenge ciphertext CTb∗=C=mbY1/s,C0=g1/s,Ci,1=wv⟶Ti,Ci,2=Uih,C3,i=Ti′i∈n. It sends CTb∗ to A.Query Phase 2: A adaptively queries SK as in Query Phase 1.Guess: A outputs a guess b′∈0,1 for b.
A wins the game if b′ is the same as b. Since the distribution of PK, UK, SK, and CT are identical to that in the real world, the advantage of the adversary to win this game is ignorable.


### 4.2.2. Chosen Keyword Attack Security

Theorem 2.
The proposed system is chosen keyword attack secure for PPT adversaries (malicious users).Proof.
LetA be a PPT adversary who attacks FGTAC system. The security game is played between A and a simulator ℬ as follows:Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈ℤp. Then, it selects ri,ui,ti∈ℤp and calculates Ri=gri,Ui=gui,Ti=vti,andTi′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H and the master secret key is MSK=α,ri,ui,tii∈n. Then, ℬ returns PK to A.Query Phase 1: Let T1,T2 be two empty sets, c=0 be an integer counter. A launches queries as follows:Generate.TrapdoorKW: ℬ sets c=c+1. It randomly selects t∈Zp and computes TD1=gt and TD2=hHKWut.td is set as TD1,TD2. ℬ stores c,KW,td to T1.Corrupt.Trapdoori: ℬ checks whether T1 contains i,KW,td. If it is, ℬ returns td to A and sets T2=T2∪KW. Otherwise, ℬ returns ⊥.Query Phase 2: A adaptively queries td as in Query Phase 1.Challenge: A declares two equal-length keywords kw0,kw1 and sends them to ℬ. Note that kw0,kw1∉T2. ℬ randomly selects b∈0,1 and runs the Encrypt algorithm to select s∈Zp and get the challenge ciphertext CTb∗=C=Y1/s,C4=hHKWb/s to A.Guess: A outputs a guess b′∈0,1 for b.
A wins the game if b′ is the same as b. Since the distribution of PK, td, and CT are identical to that in the real world, the advantage of adversary to win this game is ignorable.


### 4.2.3. Secret Key Exposure Attack Security

Theorem 3.
The proposed system is secret key exposure attack secure for a PPT adversary (semitrusted crowdsensing platform).Proof.
LetA be a PPT adversary who attacks the FGTAC system. The security game is played between A and a simulator ℬ as follows:Initialization: The adversary A declares the challenge access policy W∗ and sends it to ℬ.Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈Zp. Then it selects ri,ui,ti∈Zp and calculates Ri=gri,Ui=gui,Ti=vti,Ti′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H and the master secret key is MSK=α,ri,ui,tii∈n. Then, ℬ sends PK to A.Query Phase 1: Let T1andT2 be two empty sets, c1=0andc2=0 be two integer counters. A launches queries as follows:Generate.SKS: ℬ sets c1=c1+1. It runs the UserReg algorithm to get the user public key UK=gβ and the user secret key USK=β. Then, ℬ runs the KeyGen algorithm to get the corresponding user secret key SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n according to the attribute set S and UK. It stores c1,UK,USK,S,SK to T1. Besides, the situation that S⊨W∗ is not allowed.Generate.CTW,KW: ℬ sets c2=c2+1. It runs the Encrypt algorithm to get the ciphertext CT=C=msgY1/s,C0=g1/s,Ci,1=wv⟶Ti,Ci,2=Uih,Ci,3=Ti′i∈n,C4=hHKW/s. It stores c2,W,KW,CT to T2. Besides, the situation that the access policy W=W∗ is not allowed.Corrupti,j: ℬ checks whether T1 contains i,UK,USK,S,SK and T2 contains j,W,KW,CT. If it is, ℬ returns the tuple SK,CT to A. Otherwise, ℬ returns ⊥.PreDecryptSK,CT: A runs the PreDecrypt algorithm to compute P=∏i=1neCi,1,Ki,1eCi,1,Ki,1′eCi,2,Ki,2eCi,3,Ki,3 and set the predecrypted ciphertext preCT=eC0,K0/P.Challenge: A declares two equal-length plaintexts m0,m1 and sends them to ℬ. ℬ randomly selects b∈0,1 and runs the Encrypt algorithm to get CTb∗=C=mbY1/s,C0=g1/s,Ci,1=wv⟶Ti,Ci,2=Uih,Ci,3=Ti′i∈n. ℬ runs the UserReg algorithm and KeyGen algorithm to get SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n. ℬ sends SK,CTb∗ to A, and A performs PreDecrypt algorithm to get the challenge predecrypted ciphertext preCT=eC0,K0/P.Query Phase 2: A adaptively queries SK and CT as in phase 1.Guess: A outputs a guess b′∈0,1 for b.
A wins the game if b′ is the same as b. Since the distribution of PK, SK, UK, and CT are identical to that in the real world, the ciphertext is protected by the USK and the adversary A cannot obtain any sensitive information.


### 4.2.4. Collude Attack Security

Theorem 4.
The proposed system is colluding attack secure for PPT adversaries (malicious users).Proof.
LetA be a PPT adversary who attacks the FGTAC system. The security game is played between A and a simulator ℬ as follows:Initialization: A declares the challenge access policy W∗ and challenge user public key UK∗=gβ1 and sends them to ℬ.Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈Zp. Then, it selects ri,ui,ti∈Zp and calculates Ri=gri,Ui=gui,Ti=vti,Ti′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H, and the master secret key is MSK=α,ri,ui,tii∈n. After thatPK is sent to A.Query Phase: Let T be an empty set, c=0 be an integer counter. A launches queries as follows:Generate.SK(S): C sets c=c+1. It runs the UserReg algorithm to generate and . Then, runs the KeyGen algorithm to get the corresponding user secret key SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n according to the attribute set and . It stores to . Besides, the situation that is not allowed.Corrupt.SK (i): checks whether contains . If it is, sends to . Otherwise, returns .Forgery: output a forged secret key for the challenge access policy .
wins the game if the forged secret key is valid. Since all the secret keys in are randomized by the random number . The advantage for the adversary to forge a valid secret key is ignorable.


## 4.2.1. Chosen-Plaintext Attack Security

Theorem 1.
The proposed system is chosen-plaintext attack secure for PPT adversaries (malicious users).Proof.
LetA be a PPT adversary who attacks the FGTAC system. The security game is played between A and a simulator ℬ as follows:Initialization: A declares the challenge access policy W∗, challenge user public key UK∗=gβ1, and sends them to ℬ.Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈ℤp. Then, it selects ri,ui,ti∈ℤp and calculates Ri=gri,Ui=gui,Ti=vti,andTi′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H and the master secret key is MSK=α,ri,ui,tii∈n. PK is sent to A.Query Phase 1: Let T be an empty set, c=0 be an integer counter. A launches queries as follows:Generate.SKS: ℬ sets c=c+1. It runs the UserReg algorithm to generate UK=gβ and USK=β. Then, ℬ runs the KeyGen algorithm to get the corresponding user secret key SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n according to the attribute set S and UK. It stores c,UK,USK,S,SK to T. Besides, the situation that S⊨W∗ is not allowed.Corrupt.SKi: ℬ checks whether T contains i,UK,USK,S,SK. If it is, ℬ sends UK,USK to A. Otherwise, ℬ returns ⊥.Challenge: A declares two equal-length plaintexts m0,m1 and sends them to ℬ. ℬ randomly selects b∈0,1 and runs the Encrypt algorithm to get challenge ciphertext CTb∗=C=mbY1/s,C0=g1/s,Ci,1=wv⟶Ti,Ci,2=Uih,C3,i=Ti′i∈n. It sends CTb∗ to A.Query Phase 2: A adaptively queries SK as in Query Phase 1.Guess: A outputs a guess b′∈0,1 for b.
A wins the game if b′ is the same as b. Since the distribution of PK, UK, SK, and CT are identical to that in the real world, the advantage of the adversary to win this game is ignorable.


## 4.2.2. Chosen Keyword Attack Security

Theorem 2.
The proposed system is chosen keyword attack secure for PPT adversaries (malicious users).Proof.
LetA be a PPT adversary who attacks FGTAC system. The security game is played between A and a simulator ℬ as follows:Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈ℤp. Then, it selects ri,ui,ti∈ℤp and calculates Ri=gri,Ui=gui,Ti=vti,andTi′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H and the master secret key is MSK=α,ri,ui,tii∈n. Then, ℬ returns PK to A.Query Phase 1: Let T1,T2 be two empty sets, c=0 be an integer counter. A launches queries as follows:Generate.TrapdoorKW: ℬ sets c=c+1. It randomly selects t∈Zp and computes TD1=gt and TD2=hHKWut.td is set as TD1,TD2. ℬ stores c,KW,td to T1.Corrupt.Trapdoori: ℬ checks whether T1 contains i,KW,td. If it is, ℬ returns td to A and sets T2=T2∪KW. Otherwise, ℬ returns ⊥.Query Phase 2: A adaptively queries td as in Query Phase 1.Challenge: A declares two equal-length keywords kw0,kw1 and sends them to ℬ. Note that kw0,kw1∉T2. ℬ randomly selects b∈0,1 and runs the Encrypt algorithm to select s∈Zp and get the challenge ciphertext CTb∗=C=Y1/s,C4=hHKWb/s to A.Guess: A outputs a guess b′∈0,1 for b.
A wins the game if b′ is the same as b. Since the distribution of PK, td, and CT are identical to that in the real world, the advantage of adversary to win this game is ignorable.


## 4.2.3. Secret Key Exposure Attack Security

Theorem 3.
The proposed system is secret key exposure attack secure for a PPT adversary (semitrusted crowdsensing platform).Proof.
LetA be a PPT adversary who attacks the FGTAC system. The security game is played between A and a simulator ℬ as follows:Initialization: The adversary A declares the challenge access policy W∗ and sends it to ℬ.Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈Zp. Then it selects ri,ui,ti∈Zp and calculates Ri=gri,Ui=gui,Ti=vti,Ti′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H and the master secret key is MSK=α,ri,ui,tii∈n. Then, ℬ sends PK to A.Query Phase 1: Let T1andT2 be two empty sets, c1=0andc2=0 be two integer counters. A launches queries as follows:Generate.SKS: ℬ sets c1=c1+1. It runs the UserReg algorithm to get the user public key UK=gβ and the user secret key USK=β. Then, ℬ runs the KeyGen algorithm to get the corresponding user secret key SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n according to the attribute set S and UK. It stores c1,UK,USK,S,SK to T1. Besides, the situation that S⊨W∗ is not allowed.Generate.CTW,KW: ℬ sets c2=c2+1. It runs the Encrypt algorithm to get the ciphertext CT=C=msgY1/s,C0=g1/s,Ci,1=wv⟶Ti,Ci,2=Uih,Ci,3=Ti′i∈n,C4=hHKW/s. It stores c2,W,KW,CT to T2. Besides, the situation that the access policy W=W∗ is not allowed.Corrupti,j: ℬ checks whether T1 contains i,UK,USK,S,SK and T2 contains j,W,KW,CT. If it is, ℬ returns the tuple SK,CT to A. Otherwise, ℬ returns ⊥.PreDecryptSK,CT: A runs the PreDecrypt algorithm to compute P=∏i=1neCi,1,Ki,1eCi,1,Ki,1′eCi,2,Ki,2eCi,3,Ki,3 and set the predecrypted ciphertext preCT=eC0,K0/P.Challenge: A declares two equal-length plaintexts m0,m1 and sends them to ℬ. ℬ randomly selects b∈0,1 and runs the Encrypt algorithm to get CTb∗=C=mbY1/s,C0=g1/s,Ci,1=wv⟶Ti,Ci,2=Uih,Ci,3=Ti′i∈n. ℬ runs the UserReg algorithm and KeyGen algorithm to get SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n. ℬ sends SK,CTb∗ to A, and A performs PreDecrypt algorithm to get the challenge predecrypted ciphertext preCT=eC0,K0/P.Query Phase 2: A adaptively queries SK and CT as in phase 1.Guess: A outputs a guess b′∈0,1 for b.
A wins the game if b′ is the same as b. Since the distribution of PK, SK, UK, and CT are identical to that in the real world, the ciphertext is protected by the USK and the adversary A cannot obtain any sensitive information.


## 4.2.4. Collude Attack Security

Theorem 4.
The proposed system is colluding attack secure for PPT adversaries (malicious users).Proof.
LetA be a PPT adversary who attacks the FGTAC system. The security game is played between A and a simulator ℬ as follows:Initialization: A declares the challenge access policy W∗ and challenge user public key UK∗=gβ1 and sends them to ℬ.Setup: ℬ sets n=N1+3 and randomly selects g,h,v,w∈G, α∈Zp. Then, it selects ri,ui,ti∈Zp and calculates Ri=gri,Ui=gui,Ti=vti,Ti′=gti where i∈n. H:0,1∗⟶ℤp is a hash function. The public key is PK=g,h,v,w,Ri,Ui,Ti,Ti′i∈n,Y,H, and the master secret key is MSK=α,ri,ui,tii∈n. After thatPK is sent to A.Query Phase: Let T be an empty set, c=0 be an integer counter. A launches queries as follows:Generate.SK(S): C sets c=c+1. It runs the UserReg algorithm to generate and . Then, runs the KeyGen algorithm to get the corresponding user secret key SK=K0=UKαw1/r,Ki,1=gxVi⟶/r,Ki,1′=gxZi⟶/r,Ki,2=Ri−ti,Ki,3=Uihriv−xVi⟶+xZi⟶/ri∈n according to the attribute set and . It stores to . Besides, the situation that is not allowed.Corrupt.SK (i): checks whether contains . If it is, sends to . Otherwise, returns .Forgery: output a forged secret key for the challenge access policy .
wins the game if the forged secret key is valid. Since all the secret keys in are randomized by the random number . The advantage for the adversary to forge a valid secret key is ignorable.


## 5. Performance Evaluation

### 5.1. Feature Comparison

The performance evaluation is performed among Ref. [26, 28, 30–32] and our system. We mainly consider the following features in Table 2: hidden access policy, ciphertext search, predecryption, and access structure. Although ABE technology, which provides fine-grained access control, is employed in all the aforementioned schemes, only Ref. [28, 30, 32] and our system support hiding the access policy. Malicious users in Ref. [26, 31] may deduce sensitive information about the ciphertext from the access policy. Compared with Ref. [28, 30, 31], [26, 32], and our system enables users to search specific ciphertexts according to the keyword they provide (ciphertext search). To achieve lightweight computation, predecryption is provided in Ref. [30] and our system. As a result, task performers in both of the two systems can decrypt the ciphertext with their mobile devices efficiently. Moreover, the access structure in Ref. [26, 28] and our system are the same, while the other schemes use “And-Gate” or the “Tree” structure, which explains why we only compare our system with Ref. [26, 28] in Tables 3 and 4.Table 2
Feature comparison.
[26][28][30][31][32]Our systemHidden access policy✗✓✓✗✓✓Ciphertext search✓✗✗✗✓✓Pre-decryption✗✗✓✗✗✓Access structure+,−,∗+,−,∗TreeAnd, OrAnd+,−,∗✓ represents the scheme owns the feature. ✗ represents the scheme does not own the feature.Table 3
Comparison in storage.
PKMSKSKCTTrapdoor[26]9n+1G+GT9n+1ℤp6n+1G+ℤp—6n+1G+2ℤp[28]8n+30G+GTG+8n+28Zp4n+14G4n+14G+GT—Our system4n+20G+GT3n+13Zp4n+17G3n+14G+GT2GG,GT,Zp stand for the size of an element in G,GT,Zp. There are n positive attributes, n negative attributes, and n wildcards in our system, and [28], 3n attributes in Ref. [26].Table 4
Comparison in computation.
KeyGenEncryptSearchPredecryptDecrypt[26]6n+2G+9n+1Zp3n+1G+GT+3nZp3n+3GT+3n+1Ce——[28]34n+103G+2n+6Zp24n+74G+2GT——4n+14G+GTOur system7n+31G+6n+25Zp3n+14G+2GT+3Zp2Ce4n+17GT+Ce2GT+ZpG,GT stand for the exponentiation operation in G and GT. Zp stands for the operation in Zp. Ce stands for the billnear pairing operation. There are n positive attributes, n negative attributes, and n wildcards in our system, and [28], 3n attributes in Ref. [26].


### 5.2. Theoretical Analysis

As mentioned above, Table3 gives the comparison between Ref. [26, 28] and our system. Five objects are selected to be compared. Specifically, the size of the public key in our system is the smallest among all three schemes when . When , Ref. [26] outperforms our system. When, Ref. [28] outperforms Ref. [26]. The size of the master secret key in our system is , which is superior to that in Ref. [26, 28] when . The size of the secret key in Ref. [28] and our system are almost the same. It is less than that in Ref. [26]. For the size of ciphertext , our system is superior to Ref. [28]. We do not list in Ref. [26] for the reason that Ref. [26] only provides an algorithm to generate an encrypted index for a file waiting to be outsourced. The size of the trapdoor in Ref. [26] grows linearly with the number of attributes , while in our system, is constant . To sum up, the storage overhead in our system is significantly reduced compared to Ref. [26, 28].Table4 compares the computation overhead of, and. Note that Ref. [26] only generates a secure index in the encryption algorithm, the function of decryption is not provided. The overhead of in our system is similar to that in Ref. [26], and Ref. [28] contains and which is expensive compare to our system. Both the overhead of in our system and Ref. [26] are less than that in Ref. [28]. In Ref. [26], the computational overhead of grows every time the attribute increases, while it is in our system. We allow the crowdsensing platform to perform the Predecrypt algorithm such that the computational overhead on the user side in our system is only. However, in Ref. [28], the overhead is 4n+4G+GT.


### 5.3. Experimental Analysis

We implement the scheme in Ref. [26, 28] and our system with java pairing-based cryptography 2.0.0 (JPBC) [33] to evaluate their performance. Type A curves predefined in JPBC is used. The experimental environment we used is a MacBook Prolaptop with Intel Core i7 2.7 GHz processor and 16 GB RAM. To provide a fair condition for comparison, the access policies of ciphertexts are defined in the form of , where represent the position of wildcards, positive attributes, and negative attributes, respectively. Each kind of attributes in the access policy increases from 3 to 27, which means the total attributes increase from 9 to 81 in the experiment. To make the experiment results convincing, we repeat all the algorithms 50 times and take the average.Figure3 presents the time cost of algorithms in Ref. [26, 28] and our system. As we can see, the time cost of Setup, KeyGen, and Encrypt, in Figures 3(a), 3(c), and 3(d), of all the three schemes, grow linearly with the number of policy attributes. Although Ref. [26] is 100 ms faster in the beginning, the time cost of KeyGen tends to the same afterward. In Figure 3(b), the time cost of UserReg in FGTAC is 8.5 ms on average, which is independent of the number of attributes. Similarly, the time cost of Trapdoor and Search in Figures 3(e) and 3(f) are both constant (about 16 ms and 9 ms, respectively). However, in Ref. [28], the time cost becomes unacceptable when the number of attributes is large. We give out the time cost of Decrypt in Figure 3(g). The time cost of Predecrypt in our system is the same as the Decrypt in Ref. [28]. However, the time cost for Decrypt on the user side in our system is about 0.56 ms on average, which can be performed efficiently by mobile devices. According to the experimental results, we demonstrate that our system achieves ciphertext search and predecryption without increasing computational overhead comparing to other schemes.Figure 3
Experimental results on Setup, UserReg, KeyGen, Encrypt, Trapdoor, Search, and Decrypt. (a) Setup Time. (b) UserReg Time. (c) KeyGen Time. (d) Encrypt Time. (e) Trapdoor Time. (f) Search Time. (g) Decrypt Time.
(a)(b)(c)(d)(e)(f)(g)


## 5.1. Feature Comparison

The performance evaluation is performed among Ref. [26, 28, 30–32] and our system. We mainly consider the following features in Table 2: hidden access policy, ciphertext search, predecryption, and access structure. Although ABE technology, which provides fine-grained access control, is employed in all the aforementioned schemes, only Ref. [28, 30, 32] and our system support hiding the access policy. Malicious users in Ref. [26, 31] may deduce sensitive information about the ciphertext from the access policy. Compared with Ref. [28, 30, 31], [26, 32], and our system enables users to search specific ciphertexts according to the keyword they provide (ciphertext search). To achieve lightweight computation, predecryption is provided in Ref. [30] and our system. As a result, task performers in both of the two systems can decrypt the ciphertext with their mobile devices efficiently. Moreover, the access structure in Ref. [26, 28] and our system are the same, while the other schemes use “And-Gate” or the “Tree” structure, which explains why we only compare our system with Ref. [26, 28] in Tables 3 and 4.Table 2
Feature comparison.
[26][28][30][31][32]Our systemHidden access policy✗✓✓✗✓✓Ciphertext search✓✗✗✗✓✓Pre-decryption✗✗✓✗✗✓Access structure+,−,∗+,−,∗TreeAnd, OrAnd+,−,∗✓ represents the scheme owns the feature. ✗ represents the scheme does not own the feature.Table 3
Comparison in storage.
PKMSKSKCTTrapdoor[26]9n+1G+GT9n+1ℤp6n+1G+ℤp—6n+1G+2ℤp[28]8n+30G+GTG+8n+28Zp4n+14G4n+14G+GT—Our system4n+20G+GT3n+13Zp4n+17G3n+14G+GT2GG,GT,Zp stand for the size of an element in G,GT,Zp. There are n positive attributes, n negative attributes, and n wildcards in our system, and [28], 3n attributes in Ref. [26].Table 4
Comparison in computation.
KeyGenEncryptSearchPredecryptDecrypt[26]6n+2G+9n+1Zp3n+1G+GT+3nZp3n+3GT+3n+1Ce——[28]34n+103G+2n+6Zp24n+74G+2GT——4n+14G+GTOur system7n+31G+6n+25Zp3n+14G+2GT+3Zp2Ce4n+17GT+Ce2GT+ZpG,GT stand for the exponentiation operation in G and GT. Zp stands for the operation in Zp. Ce stands for the billnear pairing operation. There are n positive attributes, n negative attributes, and n wildcards in our system, and [28], 3n attributes in Ref. [26].


## 5.2. Theoretical Analysis

As mentioned above, Table3 gives the comparison between Ref. [26, 28] and our system. Five objects are selected to be compared. Specifically, the size of the public key in our system is the smallest among all three schemes when . When , Ref. [26] outperforms our system. When, Ref. [28] outperforms Ref. [26]. The size of the master secret key in our system is , which is superior to that in Ref. [26, 28] when . The size of the secret key in Ref. [28] and our system are almost the same. It is less than that in Ref. [26]. For the size of ciphertext , our system is superior to Ref. [28]. We do not list in Ref. [26] for the reason that Ref. [26] only provides an algorithm to generate an encrypted index for a file waiting to be outsourced. The size of the trapdoor in Ref. [26] grows linearly with the number of attributes , while in our system, is constant . To sum up, the storage overhead in our system is significantly reduced compared to Ref. [26, 28].Table4 compares the computation overhead of, and. Note that Ref. [26] only generates a secure index in the encryption algorithm, the function of decryption is not provided. The overhead of in our system is similar to that in Ref. [26], and Ref. [28] contains and which is expensive compare to our system. Both the overhead of in our system and Ref. [26] are less than that in Ref. [28]. In Ref. [26], the computational overhead of grows every time the attribute increases, while it is in our system. We allow the crowdsensing platform to perform the Predecrypt algorithm such that the computational overhead on the user side in our system is only. However, in Ref. [28], the overhead is 4n+4G+GT.


## 5.3. Experimental Analysis

We implement the scheme in Ref. [26, 28] and our system with java pairing-based cryptography 2.0.0 (JPBC) [33] to evaluate their performance. Type A curves predefined in JPBC is used. The experimental environment we used is a MacBook Prolaptop with Intel Core i7 2.7 GHz processor and 16 GB RAM. To provide a fair condition for comparison, the access policies of ciphertexts are defined in the form of , where represent the position of wildcards, positive attributes, and negative attributes, respectively. Each kind of attributes in the access policy increases from 3 to 27, which means the total attributes increase from 9 to 81 in the experiment. To make the experiment results convincing, we repeat all the algorithms 50 times and take the average.Figure3 presents the time cost of algorithms in Ref. [26, 28] and our system. As we can see, the time cost of Setup, KeyGen, and Encrypt, in Figures 3(a), 3(c), and 3(d), of all the three schemes, grow linearly with the number of policy attributes. Although Ref. [26] is 100 ms faster in the beginning, the time cost of KeyGen tends to the same afterward. In Figure 3(b), the time cost of UserReg in FGTAC is 8.5 ms on average, which is independent of the number of attributes. Similarly, the time cost of Trapdoor and Search in Figures 3(e) and 3(f) are both constant (about 16 ms and 9 ms, respectively). However, in Ref. [28], the time cost becomes unacceptable when the number of attributes is large. We give out the time cost of Decrypt in Figure 3(g). The time cost of Predecrypt in our system is the same as the Decrypt in Ref. [28]. However, the time cost for Decrypt on the user side in our system is about 0.56 ms on average, which can be performed efficiently by mobile devices. According to the experimental results, we demonstrate that our system achieves ciphertext search and predecryption without increasing computational overhead comparing to other schemes.Figure 3
Experimental results on Setup, UserReg, KeyGen, Encrypt, Trapdoor, Search, and Decrypt. (a) Setup Time. (b) UserReg Time. (c) KeyGen Time. (d) Encrypt Time. (e) Trapdoor Time. (f) Search Time. (g) Decrypt Time.
(a)(b)(c)(d)(e)(f)(g)


## 6. Conclusions

We have designed a fine-grained access control system called FGTAC in the scenario of mobile crowdsensing with an awareness of protecting the privacy of requesters. Specifically, the content of the task is encrypted by CP-ABE technology and only can be obtained by task performers who have appropriate attributes. In other words, the requester can decide the group of users who can access his task independently. To prevent the semitrusted crowdsensing platform from deducing the privacy of the requester and task performers, the access policy of the encrypted task is fully hidden in our system. For task performers, an efficient task search function, which can be conducted within approximately 9 ms, is provided. Moreover, considering the devices of task performers may be resource-limited, we also developed the function of ciphertext predecryption. According to the analysis in Section4.2, the proposed system is CPA secure, CKA secure, secret key exposure attack secure, and collude attack security. The experiment results demonstrate that the computational overhead of our system is efficient. In our future work, we will design the mobile crowdsensing system supporting audit and user tracking without yielding expensive computational overhead such that a feedback mechanism for the task performers can be achieved.



---

*Source: 6682456-2021-02-04.xml*