# Privacy-Preserving Incentive Mechanism for Mobile Crowdsensing

Authors: Tao Wan; Shixin Yue; Weichuan Liao
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Incentive mechanisms are crucial for motivating adequate users to provide reliable data in mobile crowdsensing (MCS) systems. However, the privacy leakage of most existing incentive mechanisms leads to users unwilling to participate in sensing tasks. In this paper, we propose a privacy-preserving incentive mechanism based on truth discovery. Specifically, we use the secure truth discovery scheme to calculate ground truth and the weight of users’ data while protecting their privacy. Besides, to ensure the accuracy of the MCS results, a data eligibility assessment protocol is proposed to remove the sensing data of unreliable users before performing the truth discovery scheme. Finally, we distribute rewards to users based on their data quality. The analysis shows that our model can protect users’ privacy and prevent the malicious behavior of users and task publishers. In addition, the experimental results demonstrate that our model has high performance, reasonable reward distribution, and robustness to users dropping out.


---

## Body

## 1. Introduction

As more and more sensors are integrated into human-carried mobile devices, such as GPS locators, gyroscopes, environmental sensors, and accelerometers, they can collect various types of data [1]. Therefore, the MCS system [2–4] can utilize the sensors equipped in mobile devices to collect sensing data and complete various sensing tasks [5], such as navigation service [6], traffic monitoring [7], indoor positioning [8], and environmental monitoring [9]. In general, the MCS system consists of three entities: a task requester, a sensing server, and participating users, as shown in Figure 1. The task requester publishes sensing tasks and pays awards for sensing results. The server recruits users according to the sensing task, processes the data from users, and sends the results to the task publisher. Users collect sensing data based on the requirements of the sensing task and get rewards.Figure 1
A general MCS system.In the practical MCS system, the sensing data collected by users are not always reliable [10, 11] due to various factors (such as poor sensor quality, lack of effort, and background noise). Therefore, the final result may be inaccurate if we treat the data provided by each user equally (e.g., averaging). To solve this problem, truth discovery [12–14] has been widely concerned by industry and academia. The main idea of most truth discovery schemes is that the user will be given a higher weight (i.e., reliability) if the user’s data are closer to the ground truth. Also, the data provided by a user will be counted more in the aggregation procedure if this user has a higher weight. Recently, a number of truth discovery methods [15] have been proposed to calculate user’s weight and aggregated results based on this basic idea. But one problem with these methods is that users have to be online to interact with the server. Otherwise, the MCS system may fail and have to restart. Therefore, if we design a truth discovery scheme that allows users to exit, the MCS system can get stronger robustness.The proper functioning of the truth discovery requires enough users and high-quality sensing data. Generally, the MCS system utilizes an incentive mechanism [16–18] to motivate sufficient users to participate in sensing tasks. However, because of monetary incentives, malicious users attempt to earn rewards with little or no effort. Although the truth discovery can assign low weight to malicious users, their continuous input of erroneous data can result in the unavailability of the MCS system [19]. Consequently, the evaluation of data quality is critical to the MCS system. To improve data quality, users who provide incorrect data can be removed before sensing data get aggregated [20]. On the one hand, we can get more accurate aggregation results. On the other hand, users who provide eligible data can get more monetary rewards.Although the incentive mechanism has been improved a lot, users’ privacy protection remains inadequate. When users submit sensing data, their sensitive or private information [21–23] may be leaked, including identity privacy [24], location privacy, and data privacy. Also, privacy disclosure [25] will reduce users’ willingness to participate in sensing tasks. Some incentive mechanism methods only consider the cost of users to collect sensing data but do not consider the potential cost of privacy disclosure. Recently, some researchers have designed privacy-preserving incentive mechanisms [26–28]. In [20], an incentive method is proposed to protect the user’s identity and data privacy. Still, the user’s sensing data will be submitted to the task publisher regardless of the privacy of the sensing data. In [29], the incentive mechanism is designed under the assumption of a trusted platform, which may not hold in practice since the platform itself might be attacked by hackers.To address these issues, we propose a privacy-preserving incentive mechanism based on truth discovery, called PAID. In our PAID, the task publisher sets data constraints, such as time, location [30], budget [31], and sensing data. If the user does not collect the sensing data at the required time and location or sensing data are not in the qualified range, we believe that the user’s sensing data are not credible (i.e., unqualified). After removing the unqualified user’s data, the qualified user’s sensing data will be submitted to the server to calculate the ground truth and weight. We also design a secure truth discovery scheme, which uses secret sharing technology and key agreement protocol and can still work when some users drop out. Moreover, our truth discovery can ensure that other parties cannot obtain users’ sensing data except users themselves. Finally, we calculate every user’s data quality according to the weight and distribute the reward.In summary, the main contributions of this paper are as follows:(i)
We introduce a privacy-preserving interval judgment scheme to remove users who provide unreliable data before performing the truth discovery scheme. Removing unqualified users in advance can greatly improve the quality of the sensing data used in the truth discovery scheme, improve the accuracy of results, and save the reward budget.(ii)
We introduce a secure truth discovery scheme so that our incentive mechanism model can obtain the ground truth and the weight of each user’s data while protecting the user’s privacy. Then, we design a reasonable reward distribution scheme based on the data weight of users. Moreover, our incentive mechanism model can allow users to drop out at any time.(iii)
Analysis shows that our model is secure. Also, experimental results demonstrate that our model has high performance and can achieve reasonable reward distribution.The remainder of this paper is organized as follows. In Section2, we describe the problem statement. In Sections 3 and 4, we introduce cryptography primitives and intuitive technology in our model. Then, we discuss PAID in detail in Section 5. Next, Sections 6 and 7 carry out the analysis and performance evaluation. Finally, we discuss the related work and conclude the paper in Sections 8 and 9.


## 2. Problem Statement

In this section, we introduce the background of truth discovery and our system model. Then, we describe the threat model and our design goals. Table1 summarizes the main notations in this paper.Table 1
Summary of notations.
NotationsDescriptionTA sensing taskTPA task publisherSA serveruiA user who performs a sensing taskUA set of usersUNumber of users in the setUwiThe weight of the useruix∗Ground truth of the sensing objectxiSensing data collected by the useruiτiTime forui to collect sensing dataιi^The longitude forui to collect sensing dataιi˜The latitude forui to collect sensing dataDiThe data submitted by the userui which is denoted by xi,τi,ιi^,ιi˜EEligibility rank forDi is denoted by Ex,Eτ,Eι^,Eι˜BBudget constraint of a sensing taskpkT,skTKey pair of public-key encryptionEncP,pkT(IND-CPA) Public-key encryption functionC=EncP,pkT, where P is a plaintextDecC,skTPublic-key decryption functionP=DecC,skT, where C is a ciphertextSEncP,kiSymmetric encryption functionC=SEncP,ki, where ki is the keySDecC,kiSymmetric encryption functionP=SDecC,kiπA reward control parameterqiThe data quality of the userui, and qi=wi/∑ui∈U6wiq¯Mean of data quality, andq¯=∑ui∈U6qi/U6=1/U6piMonetary reward of the userui, and pi=B/U6+π⋅qi−q¯≥0ciThe cost of the userui performing a sensing taskutiUtility of the userui


### 2.1. Truth Discovery

Truth discovery [32] is widely used in the MCS system to solve the conflicts between sensing data collected from multiple sources. Although the methods of estimating weights and calculating ground truth are different, their general processes are similar. Specifically, truth discovery initializes a random ground truth and then iteratively updates the weight and ground truth until convergence.


#### 2.1.1. Weight Update

Suppose that the ground truth of the object is fixed. If the user’s sensing data are close to the ground truth, a higher weight should be assigned to the user. The weightwi of each user ui can be iteratively updated as follows:(1)wi=log∑i′=1Udistxi′,x∗distxi,x∗,where distxi,x∗ is a distance function and distxi,x∗=xi-x∗2. We use U to represent the set of users, and U is the number of users in the set U. The sensing data collected by the user ui are denoted as xi, in which i is the number of ui, and x∗ is the estimated ground truth.


#### 2.1.2. Truth Update

Similarly, we assume that the weightwi of each user ui is fixed. Then, we can calculate the ground truth x∗ as follows:(2)x∗=∑i=1Uwi⋅xi∑i=1Uwi.The final ground truthx∗ is obtained by iteratively running the weight update and the truth update until the convergence condition is satisfied.


### 2.2. System Model

Similar to the general MCS system, our PAID comprises three entities: a task publisher (TP), a server (S), and users. In our PAID, the TP publishes tasks and requirements to S and gets the ground truth of the object from S. The server S recruits adequate users and removes the users who provide unqualified data. After receiving the sensing data of all users, S performs the truth discovery scheme and gets the ground truth and the weight of each user. To prevent the TP from refusing to pay the reward, we require the TP to prepay the reward to S as a guarantee. After getting the weight of each user, the server S calculates the data quality and distributes the rewards. Users collect sensing data and earn monetary rewards by providing qualified data. Moreover, our PAID can protect users’ privacy of time, location, identity, and sensing data. Unlike general MCS models, in our PAID, the TP and S can only get the aggregated result instead of users’ sensing data. Figure 2 shows the flow of our PAID. The specific process of our model is as follows.(1)
Task Publish. The TP publishes a sensing task to S, including sensing objects, data eligibility requirements, and budget.(2)
User Recruitment. The server S broadcasts the sensing task and recruits participating users.(3)
Eligibility Assessment. The server S judges whether every user’s sensing data meet qualification requirements.(4)
Prepayment. The TP prepays S monetary reward to avoid the denial of payment attack.(5)
Submission Notification. The server S notifies qualified users to submit sensing data.(6)
Data Submission and Eligibility Confirmation. Users submit the masked sensing data to S. And the server S needs to confirm whether the submitted sensing data are qualified to prevent malicious users from tampering with the data.(7)
Deviation Elimination. The server S removes users who tamper with their sensing data and eliminates the deviation of data aggregation caused by these dropped users.(8)
Secure Truth Discovery. The server S calculates the ground truth and weight of each user by performing the security truth discovery scheme.(9)
Reward Distribution. The server S calculates the data quality of each user and distributes the rewards.(10)
Task Completion. The server S sends the ground truth of the sensing object to TP.Figure 2
System model of PAID.


### 2.3. Threat Model

In this section, we mainly consider the potential threats from TP, the serverS, and users.We suppose that TP is dishonest. After getting data fromS, TP may launch a denial of payment attack (DoP) and refuse to pay rewards.The serverS is considered as honest-but-curious [33, 34]. Specifically, the server S follows the agreement execution instructions, but it also attempts to spy on users’ private data. In other words, the server S may launch inference attacks (IAs) on the users’ private data.We assume that users are untrusted. Some malicious users may provide erroneous data and launch adata pollution attack (DPA). Besides, untrusted users may forge multiple identities and initiate a Sybil attack (SA), to earn more monetary rewards.


### 2.4. Design Goals

In this section, we introduce the design goals of our PAID, which are divided into privacy and security goals and property goals.The privacy goals can protect the user’s private data, and the security goals can avoid malicious attacks. The details are as follows.(i)
Privacy Goals. PAID can protect user’s location privacy, data privacy, and identity privacy. Specifically, the location and sensing data of a user cannot be obtained by any other parties except the user himself. And users’ real identities would not be disclosed when performing a sensing task.(ii)
Security Goals. In our PAID, users can avoid the denial of payment attack (DoP) of TP. The server S cannot initiate an inference attack (IA) on users. The server S can resist the data pollution attack (DPA) launched by malicious users. And our PAID guarantees fairness by resisting the Sybil attack (SA).Our PAID also requires the following property goals.(i)
Eligibility. If users’ data do not meet the eligibility requirements, they cannot pass the eligibility assessment. In other words, the sensing data adopted by our PAID must be eligible.(ii)
Zero Knowledge. When the server S assesses whether users’ data meet the eligibility requirements, it cannot obtain the content of users’ private data.(iii)
Payment Rationality. Each user can get non-negative utility as long as the user provides qualified data.(iv)
Budget Rationality. The total monetary reward paid by the TP does not exceed the budget constraint.


## 2.1. Truth Discovery

Truth discovery [32] is widely used in the MCS system to solve the conflicts between sensing data collected from multiple sources. Although the methods of estimating weights and calculating ground truth are different, their general processes are similar. Specifically, truth discovery initializes a random ground truth and then iteratively updates the weight and ground truth until convergence.


### 2.1.1. Weight Update

Suppose that the ground truth of the object is fixed. If the user’s sensing data are close to the ground truth, a higher weight should be assigned to the user. The weightwi of each user ui can be iteratively updated as follows:(1)wi=log∑i′=1Udistxi′,x∗distxi,x∗,where distxi,x∗ is a distance function and distxi,x∗=xi-x∗2. We use U to represent the set of users, and U is the number of users in the set U. The sensing data collected by the user ui are denoted as xi, in which i is the number of ui, and x∗ is the estimated ground truth.


### 2.1.2. Truth Update

Similarly, we assume that the weightwi of each user ui is fixed. Then, we can calculate the ground truth x∗ as follows:(2)x∗=∑i=1Uwi⋅xi∑i=1Uwi.The final ground truthx∗ is obtained by iteratively running the weight update and the truth update until the convergence condition is satisfied.


## 2.1.1. Weight Update

Suppose that the ground truth of the object is fixed. If the user’s sensing data are close to the ground truth, a higher weight should be assigned to the user. The weightwi of each user ui can be iteratively updated as follows:(1)wi=log∑i′=1Udistxi′,x∗distxi,x∗,where distxi,x∗ is a distance function and distxi,x∗=xi-x∗2. We use U to represent the set of users, and U is the number of users in the set U. The sensing data collected by the user ui are denoted as xi, in which i is the number of ui, and x∗ is the estimated ground truth.


## 2.1.2. Truth Update

Similarly, we assume that the weightwi of each user ui is fixed. Then, we can calculate the ground truth x∗ as follows:(2)x∗=∑i=1Uwi⋅xi∑i=1Uwi.The final ground truthx∗ is obtained by iteratively running the weight update and the truth update until the convergence condition is satisfied.


## 2.2. System Model

Similar to the general MCS system, our PAID comprises three entities: a task publisher (TP), a server (S), and users. In our PAID, the TP publishes tasks and requirements to S and gets the ground truth of the object from S. The server S recruits adequate users and removes the users who provide unqualified data. After receiving the sensing data of all users, S performs the truth discovery scheme and gets the ground truth and the weight of each user. To prevent the TP from refusing to pay the reward, we require the TP to prepay the reward to S as a guarantee. After getting the weight of each user, the server S calculates the data quality and distributes the rewards. Users collect sensing data and earn monetary rewards by providing qualified data. Moreover, our PAID can protect users’ privacy of time, location, identity, and sensing data. Unlike general MCS models, in our PAID, the TP and S can only get the aggregated result instead of users’ sensing data. Figure 2 shows the flow of our PAID. The specific process of our model is as follows.(1)
Task Publish. The TP publishes a sensing task to S, including sensing objects, data eligibility requirements, and budget.(2)
User Recruitment. The server S broadcasts the sensing task and recruits participating users.(3)
Eligibility Assessment. The server S judges whether every user’s sensing data meet qualification requirements.(4)
Prepayment. The TP prepays S monetary reward to avoid the denial of payment attack.(5)
Submission Notification. The server S notifies qualified users to submit sensing data.(6)
Data Submission and Eligibility Confirmation. Users submit the masked sensing data to S. And the server S needs to confirm whether the submitted sensing data are qualified to prevent malicious users from tampering with the data.(7)
Deviation Elimination. The server S removes users who tamper with their sensing data and eliminates the deviation of data aggregation caused by these dropped users.(8)
Secure Truth Discovery. The server S calculates the ground truth and weight of each user by performing the security truth discovery scheme.(9)
Reward Distribution. The server S calculates the data quality of each user and distributes the rewards.(10)
Task Completion. The server S sends the ground truth of the sensing object to TP.Figure 2
System model of PAID.


## 2.3. Threat Model

In this section, we mainly consider the potential threats from TP, the serverS, and users.We suppose that TP is dishonest. After getting data fromS, TP may launch a denial of payment attack (DoP) and refuse to pay rewards.The serverS is considered as honest-but-curious [33, 34]. Specifically, the server S follows the agreement execution instructions, but it also attempts to spy on users’ private data. In other words, the server S may launch inference attacks (IAs) on the users’ private data.We assume that users are untrusted. Some malicious users may provide erroneous data and launch adata pollution attack (DPA). Besides, untrusted users may forge multiple identities and initiate a Sybil attack (SA), to earn more monetary rewards.


## 2.4. Design Goals

In this section, we introduce the design goals of our PAID, which are divided into privacy and security goals and property goals.The privacy goals can protect the user’s private data, and the security goals can avoid malicious attacks. The details are as follows.(i)
Privacy Goals. PAID can protect user’s location privacy, data privacy, and identity privacy. Specifically, the location and sensing data of a user cannot be obtained by any other parties except the user himself. And users’ real identities would not be disclosed when performing a sensing task.(ii)
Security Goals. In our PAID, users can avoid the denial of payment attack (DoP) of TP. The server S cannot initiate an inference attack (IA) on users. The server S can resist the data pollution attack (DPA) launched by malicious users. And our PAID guarantees fairness by resisting the Sybil attack (SA).Our PAID also requires the following property goals.(i)
Eligibility. If users’ data do not meet the eligibility requirements, they cannot pass the eligibility assessment. In other words, the sensing data adopted by our PAID must be eligible.(ii)
Zero Knowledge. When the server S assesses whether users’ data meet the eligibility requirements, it cannot obtain the content of users’ private data.(iii)
Payment Rationality. Each user can get non-negative utility as long as the user provides qualified data.(iv)
Budget Rationality. The total monetary reward paid by the TP does not exceed the budget constraint.


## 3. Preliminaries

In this section, we review the cryptographic primitives used in our PAID.


### 3.1. Secret Sharing

We use Shamir’st-out-of-N secret sharing protocol [35], which can split each user’s secret s into N shares, where any t shares can be used to reconstruct s. Still, it is impossible to get any information about s if the shares obtained by attackers are less than t.We assume that some integers can be identified with distinct elements in a finite fieldℱ, where ℱ is parameterized with a size of l>2k (in which k is the security parameter). These integers can represent all users’ IDs, and we use a symbol U to denote the set of users’ IDs. Then, Shamir’s secret sharing protocol consists of two steps as below.(i)
Shamir.shares,t,U⟶ui,siui∈U: the inputs of the sharing algorithm are a secret s, a threshold t≤U, and a set U of N field elements denoting the users’ ID, where U=N. It outputs a set of shares si, each of which is associated with its corresponding the user ui.(ii)
Shamir.reconui,siui∈ℳ,t⟶s: the inputs of the reconstruction algorithm are the shares corresponding to a subset ℳ⊆U and a threshold t, where t≤ℳ, and it outputs the secret s.Correctness requires that∀s∈ℱ, ∀t, N with 1≤t≤N. If ui,siui∈U←Shamir.shares,t,U, where ℳ⊆U and t≤ℳ, then Shamir.reconui,siui∈ℳ,t⟶s.Security requires∀s,s′∈ℱ and any ℳ⊆U with t>ℳ. We have(3)ui,siui∈U←Shamir.shares,t,U:ui,siui∈ℳ≡ui,siui∈U←Shamir.shares′,t,U:ui,siui∈ℳ,where “≡” indicates that the two distributions are indistinguishable.


### 3.2. Key Agreement

We utilize the Diffie–Hellman key agreement called SIGMA [36] in our PAID to generate a session key between two users. Typically, SIGMA is described in three parts as follows.(i)
KA.paramk⟶G,g,q,H: the algorithm’s input is a security parameter k. It samples a group G of prime order q, along with a generator g and a hash function H, where H is set as SHA-256 for practicability in our model.(ii)
KA.genG,g,q,H⟶x,gx: the algorithm’s inputs are a group G of prime order q, along with a generator g and a hash function H. It samples a random x←Zq and gx, where x and gx will be marked as the secret key SKi and the public key PKi in the following sections.(iii)
KA.agreesignjgxi,gxj,MACkuj,xi,gxj,i,j⟶si,j: the algorithm’s inputs are the user ui’s secret key xi, the user uj’s public key gxj, signed signature signjgxi,gxj, and MACkvuj from the user uj, where kv is used as the MAC key. It outputs a session key si,j between user ui and user uj. For simplicity, we use KA.agreexi,gxj⟶si,j to represent the above process in the following sections.Correctness requires thatKA.agreeSKi,PKj=KA.agreeSKi,PKj for any private and public key generated by the users ui and uj if two users use the same parameters. Security requires that the shared key si,j is indistinguishable from a uniformly random string for any adversary who is given public keys PKi and PKj (but do not have the corresponding secret keys SKi and SKj).


### 3.3. Paillier Cryptosystem

The Paillier cryptosystem [37] is a probabilistic public key cryptosystem. It consists of three parts as follows.(i)
Paillier.genN,g⟶skp,pkp: the key distribution algorithm inputs are a number N and g←ZN2∗, where N is the product of two large primes p, q. It outputs a secret key skp and a public key pkp, where pkp is computed by N,g, and skp=lcmp−1,q−1.(ii)
Paillier.encm,pkp⟶c: the encryption algorithm inputs are a plaintext m (which m<N) and a public key pkp. It outputs a ciphertext c.(iii)
Paillier.decc,skp⟶m: the decryption algorithm inputs are a ciphertext c (which c<N2) and a secret key skp. It outputs a plaintext m.The Paillier cryptosystem has the property of homomorphic addition.(4)Epka+b=Epka⋅EpkbmodN2.We assume thatE is an encryption function.


## 3.1. Secret Sharing

We use Shamir’st-out-of-N secret sharing protocol [35], which can split each user’s secret s into N shares, where any t shares can be used to reconstruct s. Still, it is impossible to get any information about s if the shares obtained by attackers are less than t.We assume that some integers can be identified with distinct elements in a finite fieldℱ, where ℱ is parameterized with a size of l>2k (in which k is the security parameter). These integers can represent all users’ IDs, and we use a symbol U to denote the set of users’ IDs. Then, Shamir’s secret sharing protocol consists of two steps as below.(i)
Shamir.shares,t,U⟶ui,siui∈U: the inputs of the sharing algorithm are a secret s, a threshold t≤U, and a set U of N field elements denoting the users’ ID, where U=N. It outputs a set of shares si, each of which is associated with its corresponding the user ui.(ii)
Shamir.reconui,siui∈ℳ,t⟶s: the inputs of the reconstruction algorithm are the shares corresponding to a subset ℳ⊆U and a threshold t, where t≤ℳ, and it outputs the secret s.Correctness requires that∀s∈ℱ, ∀t, N with 1≤t≤N. If ui,siui∈U←Shamir.shares,t,U, where ℳ⊆U and t≤ℳ, then Shamir.reconui,siui∈ℳ,t⟶s.Security requires∀s,s′∈ℱ and any ℳ⊆U with t>ℳ. We have(3)ui,siui∈U←Shamir.shares,t,U:ui,siui∈ℳ≡ui,siui∈U←Shamir.shares′,t,U:ui,siui∈ℳ,where “≡” indicates that the two distributions are indistinguishable.


## 3.2. Key Agreement

We utilize the Diffie–Hellman key agreement called SIGMA [36] in our PAID to generate a session key between two users. Typically, SIGMA is described in three parts as follows.(i)
KA.paramk⟶G,g,q,H: the algorithm’s input is a security parameter k. It samples a group G of prime order q, along with a generator g and a hash function H, where H is set as SHA-256 for practicability in our model.(ii)
KA.genG,g,q,H⟶x,gx: the algorithm’s inputs are a group G of prime order q, along with a generator g and a hash function H. It samples a random x←Zq and gx, where x and gx will be marked as the secret key SKi and the public key PKi in the following sections.(iii)
KA.agreesignjgxi,gxj,MACkuj,xi,gxj,i,j⟶si,j: the algorithm’s inputs are the user ui’s secret key xi, the user uj’s public key gxj, signed signature signjgxi,gxj, and MACkvuj from the user uj, where kv is used as the MAC key. It outputs a session key si,j between user ui and user uj. For simplicity, we use KA.agreexi,gxj⟶si,j to represent the above process in the following sections.Correctness requires thatKA.agreeSKi,PKj=KA.agreeSKi,PKj for any private and public key generated by the users ui and uj if two users use the same parameters. Security requires that the shared key si,j is indistinguishable from a uniformly random string for any adversary who is given public keys PKi and PKj (but do not have the corresponding secret keys SKi and SKj).


## 3.3. Paillier Cryptosystem

The Paillier cryptosystem [37] is a probabilistic public key cryptosystem. It consists of three parts as follows.(i)
Paillier.genN,g⟶skp,pkp: the key distribution algorithm inputs are a number N and g←ZN2∗, where N is the product of two large primes p, q. It outputs a secret key skp and a public key pkp, where pkp is computed by N,g, and skp=lcmp−1,q−1.(ii)
Paillier.encm,pkp⟶c: the encryption algorithm inputs are a plaintext m (which m<N) and a public key pkp. It outputs a ciphertext c.(iii)
Paillier.decc,skp⟶m: the decryption algorithm inputs are a ciphertext c (which c<N2) and a secret key skp. It outputs a plaintext m.The Paillier cryptosystem has the property of homomorphic addition.(4)Epka+b=Epka⋅EpkbmodN2.We assume thatE is an encryption function.


## 4. Technical Intuition

In this section, we first introduce how the interval judgment scheme can judge users’ data eligibility while protecting users’ privacy. Then, we notice that truth discovery mainly involves the aggregation of multiple users’ data in a secure manner. Therefore, we require that the serverS only get the sum of users’ input, not content. And we propose a double-masking scheme to achieve this goal.


### 4.1. Interval Judgment Scheme for Privacy Protection

In our PAID, we use the interval judgment scheme [38] based on the Paillier cryptosystem to determine the sensing data eligibility. Every user ui provides sensing data xi, and the server S provides a continuous integer interval y1,y2 (y1,y2←Z∗). The server S can judge whether the user ui’s sensing data xi meet the interval range y1,y2 without knowing the data xi. The user ui also cannot obtain any information about the integer interval. The scheme is divided into four steps as follows.(i)
The userui gets pkp,skp←Paillier.genN,g and then ui computes Exi using pkp and sends it to S.(ii)
The serverS picks two random numbers k,bk,b←Z∗ to construct a monotone increasing (or decreasing) function fxi=kxi+b. Then, the server S computes fy1,fy2,c=ExikEb=Ekx+b and sends them to ui.(iii)
After receiving the information from the serverS, the user ui gets fxi←Paillier.decc,sk and then compares the size of fy1, fy1, and fxi. Next, the message is sent to the server S.(iv)
After receiving the message fromui, the server S judges whether fy1<fxd<fy2. If so, we can know xi∈y1,y2 because of the monotonicity of the function fxi=kxi+b, i.e., the user ui passes the data eligibility assessment. Otherwise, the user ui fails to pass the eligibility assessment of the server S.It should be noted that since the userui does not know the monotonicity of the function fx=kx+b, it is impossible to infer whether the data xi are in the range of the interval y1,y2 from the size relationship. For simplicity, we formulate the above process as an interval judgment function denoted by insxi,y1,y2. If the user ui passes the eligibility assessment of the server S, insxi,y1,y2=1; otherwise, insxi,y1,y2=0.


### 4.2. One-Masking Scheme

Assume that all users are represented in sequence as integers 1,n. And any pair of users ui,uj, i<j, agrees on a random value ri,j. Let us add ri,j to the user ui’s data xi and subtract ri,j from the user uj’s data xj to mask all users’ raw data. In other words, each user ui computes as follows.(5)yi=xi+∑uj∈U:i<jri,j−∑uj∈U:i>jrj,imodR,where we assume xi and ∑uj∈Uri,j are in ZR with order R for simplicity.Then, each userui submits yi to the server S, and S computes(6)z=∑ui∈Uyi=∑ui∈Uxi+∑uj∈U:i<jri,j−∑uj∈U:i>jrj,i=∑ui∈UximodR.However, this approach has two shortcomings. The first one is that every userui needs to exchange the value ri,j with all other users, which will result in quadratic communication overhead U2 if done naively. The second one is that the protocol will fail if any user ui drops out since the server cannot eliminate the value ri,j associated with ui in the final aggregated results z.


### 4.3. Double-Masking Scheme

To solve these security problems, we introduce a double-masking scheme [39, 40]. In the work [40], the double-masking scheme is used for privacy-preserving data aggregation. And the scheme in [40] can also protect location privacy and verify the aggregation results. In our model, location privacy protection is implemented by the interval judgment scheme, and our secure truth discovery will confirm the data consistency. The details of the double-masking scheme are as follows.Every userui can get a session key ri,j with other user uj by engaging the Diffie–Hellman key agreement after the server S broadcasts all of the Diffie–Hellman public keys. Then, we can utilize a pseudorandom generator (PRG) to reduce the high communication overhead by having the parties agree on a common seed instead of the whole mask ri,j.We use the threshold secret sharing scheme to solve the issue that users are not allowed to drop out. Every userui can send his secret shares to other users. Once some users cannot submit data in time, other users can recover masks associated with these users by submitting shares of these users’ secrets to S, as long as the number of dropped users is less than t (i.e., threshold of Shamir’s secret sharing).However, there is a problem that may lead to users’ data leaked toS. There is a scenario where a user ui is very slow to send data to S. The server S considers that the user ui has dropped and asks for their shares of the user ui’s secret from all other users. Then, the server receives the delayed data yi after recovering ui’s mask. At this time, the server S can remove all the masks ri,j and get the plaintext xi.To improve the scheme, we introduce an additional random seedni to mask the data. Specifically, each user ui selects a random seed ni on the round of generating ri,j and then creates and distributes shares of ni to all other users during the secret sharing round. Now, users calculate yi as follows:(7)yi=xi+PRGni+∑uj∈U:i<jPRGri,j−∑uj∈U:i>jPRGri,jmodR.Note that an honest user will never reveal both kinds of shares of the same user to the serverS. During the recovery round, the server S can request either a share of ri,j or a share of ni from each surviving user uj. After gathering at least t shares of ri,j for all dropped users and t shares of ni for all surviving users, the server S can eliminate the remaining masks to reveal the sum.


## 4.1. Interval Judgment Scheme for Privacy Protection

In our PAID, we use the interval judgment scheme [38] based on the Paillier cryptosystem to determine the sensing data eligibility. Every user ui provides sensing data xi, and the server S provides a continuous integer interval y1,y2 (y1,y2←Z∗). The server S can judge whether the user ui’s sensing data xi meet the interval range y1,y2 without knowing the data xi. The user ui also cannot obtain any information about the integer interval. The scheme is divided into four steps as follows.(i)
The userui gets pkp,skp←Paillier.genN,g and then ui computes Exi using pkp and sends it to S.(ii)
The serverS picks two random numbers k,bk,b←Z∗ to construct a monotone increasing (or decreasing) function fxi=kxi+b. Then, the server S computes fy1,fy2,c=ExikEb=Ekx+b and sends them to ui.(iii)
After receiving the information from the serverS, the user ui gets fxi←Paillier.decc,sk and then compares the size of fy1, fy1, and fxi. Next, the message is sent to the server S.(iv)
After receiving the message fromui, the server S judges whether fy1<fxd<fy2. If so, we can know xi∈y1,y2 because of the monotonicity of the function fxi=kxi+b, i.e., the user ui passes the data eligibility assessment. Otherwise, the user ui fails to pass the eligibility assessment of the server S.It should be noted that since the userui does not know the monotonicity of the function fx=kx+b, it is impossible to infer whether the data xi are in the range of the interval y1,y2 from the size relationship. For simplicity, we formulate the above process as an interval judgment function denoted by insxi,y1,y2. If the user ui passes the eligibility assessment of the server S, insxi,y1,y2=1; otherwise, insxi,y1,y2=0.


## 4.2. One-Masking Scheme

Assume that all users are represented in sequence as integers 1,n. And any pair of users ui,uj, i<j, agrees on a random value ri,j. Let us add ri,j to the user ui’s data xi and subtract ri,j from the user uj’s data xj to mask all users’ raw data. In other words, each user ui computes as follows.(5)yi=xi+∑uj∈U:i<jri,j−∑uj∈U:i>jrj,imodR,where we assume xi and ∑uj∈Uri,j are in ZR with order R for simplicity.Then, each userui submits yi to the server S, and S computes(6)z=∑ui∈Uyi=∑ui∈Uxi+∑uj∈U:i<jri,j−∑uj∈U:i>jrj,i=∑ui∈UximodR.However, this approach has two shortcomings. The first one is that every userui needs to exchange the value ri,j with all other users, which will result in quadratic communication overhead U2 if done naively. The second one is that the protocol will fail if any user ui drops out since the server cannot eliminate the value ri,j associated with ui in the final aggregated results z.


## 4.3. Double-Masking Scheme

To solve these security problems, we introduce a double-masking scheme [39, 40]. In the work [40], the double-masking scheme is used for privacy-preserving data aggregation. And the scheme in [40] can also protect location privacy and verify the aggregation results. In our model, location privacy protection is implemented by the interval judgment scheme, and our secure truth discovery will confirm the data consistency. The details of the double-masking scheme are as follows.Every userui can get a session key ri,j with other user uj by engaging the Diffie–Hellman key agreement after the server S broadcasts all of the Diffie–Hellman public keys. Then, we can utilize a pseudorandom generator (PRG) to reduce the high communication overhead by having the parties agree on a common seed instead of the whole mask ri,j.We use the threshold secret sharing scheme to solve the issue that users are not allowed to drop out. Every userui can send his secret shares to other users. Once some users cannot submit data in time, other users can recover masks associated with these users by submitting shares of these users’ secrets to S, as long as the number of dropped users is less than t (i.e., threshold of Shamir’s secret sharing).However, there is a problem that may lead to users’ data leaked toS. There is a scenario where a user ui is very slow to send data to S. The server S considers that the user ui has dropped and asks for their shares of the user ui’s secret from all other users. Then, the server receives the delayed data yi after recovering ui’s mask. At this time, the server S can remove all the masks ri,j and get the plaintext xi.To improve the scheme, we introduce an additional random seedni to mask the data. Specifically, each user ui selects a random seed ni on the round of generating ri,j and then creates and distributes shares of ni to all other users during the secret sharing round. Now, users calculate yi as follows:(7)yi=xi+PRGni+∑uj∈U:i<jPRGri,j−∑uj∈U:i>jPRGri,jmodR.Note that an honest user will never reveal both kinds of shares of the same user to the serverS. During the recovery round, the server S can request either a share of ri,j or a share of ni from each surviving user uj. After gathering at least t shares of ri,j for all dropped users and t shares of ni for all surviving users, the server S can eliminate the remaining masks to reveal the sum.


## 5. Our Proposed Scheme

In this section, we first provide an overview of our PAID. Then, we show the details of the three critical designs in our PAID, including eligibility assessment, truth discovery, and reward distribution. In the eligibility assessment stage, the serverS judges whether users’ sensing data meet the requirements of a sensing task. In the truth discovery stage, the server S can calculate each user’s weight and the ground truth required by the sensing task without knowing their sensing data. In the reward distribution stage, the server S computes the quality of sensing data by each user’s weight and then pays a reward to users.


### 5.1. Overview

For convenience, we introduce a simple case. We set up a sensing taskT to collect the temperature of urban roads in the evening. There are range requirements for time, location, and sensing data (i.e., temperature). To be more precise, the time range is required to be 5–8 pm on February 3rd, the location range is required to be 12.45–12.55 E and 41.79–41.99 N, and the temperature requirement is 10–15°C. In our PAID, we consider the range requirement as the data eligibility requirement E. The data Di (Di=xi,τi,ιi^,ιi˜) collected by a user ui meet the eligibility requirements E, meaning that 10≤xi≤15,5≤τi≤8,12.45≤ιi^≤12.55,41.79≤ιi˜≤41.99. Since the data collected by mobile devices are usually rational numbers, in our PAID, we transform the eligible interval into an integer interval by moving the decimal point right. The sensing task T consists of three entities: a task publisher (TP), a server (S), and users. And the specific steps are as follows.Step 1 (Task Publish). The task publisher TP initializes a public key pkT and a private key skT, a reward control parameter π (π is a decimal number), a task budget B, the number of users N, and eligibility requirements E for a sensing task T. The public key pkT is used to encrypt the information that the server S needs to send to the TP, and the TP decrypts the ciphertext using the private key skT. Then, the TP sends the information T,pkT,π,N,B,Ε to S as a task request.Step 2 (User Recruitment). The server S broadcasts the sensing task information T,π,N,B and recruits N users who request to participate in the sensing task. Then, S generates a key pair PKSi,SKSi using the key agreement scheme for every user ui and sends PKSi to ui.Step 3 (Eligibility Assessment). Each user ui confirms whether ci≤B−π/N, where ci denotes the sensing cost of ui, and the posted lowest reward is denoted as B−π/N. If ci≤B−π/N, and ui starts the sensing task and collects the data Di. The user ui then generates a key pair PKi,SKi using the key agreement scheme and computes a session key ki←KA.agreeSKi,PKSi as ui’s anonymous identity information. Then, the user ui performs the interval judgment scheme insDi,E and sends the public key PKi to S. Specifically, insDi,E is divided into insxi,E, insτi,E, insιi^,E, insιi˜,E.Step 4 (Prepayment). After recruiting N eligible users, the server S requests TP to prepay a budget reward B for the sensing task T to prevent the denial of payment attack. And the server S calculates the session key ki←KA.agreeSKSi,PKi with the eligible user ui.Step 5 (Submission Notification). After getting the budget reward B, the server S informs the eligible user ui1≤i≤N to submit data.Step 6 (Data Submission and Eligibility Confirmation). After receiving the submission notification, each user ui performs double-masking scheme to mask the sensing data xi and get yi and , at the same time, executes eligibility confirmation insDi,E to prevent malicious users from modifying data. Then, ui encrypts the data yi using the symmetric encryption algorithm and sends the ciphertext SEncyi,ki to S. The session key ki is the key of symmetric encryption.Step 7 (Deviation Elimination). For users who tamper with data during data submission, the server S regards them as dropped users and discards their data. Then, S gets plaintext SDecSEncyi,ki,ki and requests seed ni and the noise ri,j between the dropped user ui and the surviving user uj to eliminate the impact on the aggregate result.Step 8 (Secure Truth Discovery). The server S computes the surviving user ui’s weight wi and the ground truth x∗ of the sensing object utilizing the truth discovery algorithm. The detailed algorithm process will be introduced later.Step 9 (Reward Distribution). The server S calculates the sensing data quality qi=wi/∑i=1mwi of ui, where ∑i=1mqi=1, m is the number of online users. Then, S pays a monetary reward pi=B/m+π⋅qi−q¯ for ui, where π⋅qi−q¯ denotes the payment parameter, m≤N, and 1≤i≤m.Step 10 (Task Completion). The server S encrypts the ground truth x∗ using pkT and sends Encx∗,pkT to TP. And the TP can decrypt the data using skT, i.e., x∗=DecEncx∗,pkT,skT.In our PAID, only users who passed the eligibility assessment and eligibility confirmation can obtain the monetary reward. Thus, users cannot cheatS to get a reward with unreliable data. We can also ensure the quality of the sensing data used by the truth discovery algorithm and obtain more accurate ground truth x∗. Moreover, since the TP pays the task reward to S in advance and S will pay a reward to ui according to the quality of ui’s sensing data after the task is accomplished, the TP cannot refuse to pay the reward. Besides, S cannot get users’ raw sensing data, time, and location information, which can protect the users’ privacy. The anonymous identity of each user is determined by both the user and S. S only assigns one random identity token to each user, so malicious users cannot forge multiple identities.


### 5.2. Eligibility Assessment

In our PAID, there are three benefits to the design of the eligibility assessment. First, it can prevent users who provide unreliable or erroneous sensing data from receiving monetary rewards, which avoids wasting budgets. Secondly, filtering out unqualified sensing data can improve the accuracy of the sensing task result. Thirdly, the data qualityqi of each user ui is related to the sensing object’s ground truth x∗, and inaccurate ground truth will lead to unfair incentives.The process of eligibility assessment and eligibility confirmation is similar. The purpose of the eligibility assessment is to filter out unqualified users preliminarily. Thus, the unqualified users do not need to communicate with other users to perform the double-masking scheme, by which the communication overhead can be reduced. The eligibility confirmation is designed to prevent malicious users from altering the original qualified data. The detailed process of eligibility assessment and eligibility confirmation is as follows.Step 1. Each user ui initializes a key pair pkpi,skpi←Paillier.genN,g. Then, ui encrypts the sensing data Di using pkpi and sends the ciphertext EDi to S. Generally, EDi consists of four parts: Exi, Eτi, Eιi^, and Eιi˜.Step 2. After receiving EDi, the server S picks different random k,bk,b←Z∗ and constructs a monotone increasing (or decreasing) function fDi=kDi+b for each value in the quadruples xi,τi,ιi^,ιi˜. The monotonicity of the four functions is inconsistent. For eligibility requirement interval E (E=Ex,Eτ,Eι^,Eι˜,Ex=xl,xr,Eτ=τl,τr,Eι^=ι^l,ι^r,Eι˜=ι˜l,ι˜r), the server S calculates(8)fxl,fxr,c1=Exik1,Eb1=Ek1xi+b1,fτl,fτr,c2=Eτik2,Eb2=Ek2τi+b2,fι^l,fι^r,c3=Eι^ik3,Eb3=Ek3ι^i+b3,fι˜l,fι˜r,c4=Eι˜ik4,Eb4=Ek4ι˜i+b4.Then,S sends fEl,fEr,c (c=c1,c2,c3,c4) to ui. For convenience, we will not describe Di and E separately in the following text.Step 3. After receiving fEl,fEr,c from S, each user ui gets fDi←Paillier.decc,skpi and then compares the size of fEl,fEr,fDi. Next, the size relationship is sent to S.Step 4. After the server S receives the information from ui, if fEl≤fDi≤fEr, then Di∈El,Er because of the monotonicity of the functions. And S determines whether ui passes the eligibility assessment. Otherwise, it fails.Because users do not know the function’s monotonicity, they cannot infer the size relationship between the qualified data and eligibility requirement. Therefore, we can think that malicious users have a very low probability of passing the eligibility assessment. Moreover, during the eligibility assessment,ui cannot know the specific qualified interval. S also cannot get ui’s sensing data, which can protect ui’s privacy. The above process is represented by insDi,E. If ui passes the eligibility assessment, then insDi,E=1. If not, insDi,E=0.


### 5.3. Secure Truth Discovery

In the secure truth discovery scheme [15], data exchange is between users and the server S. The user ui needs to collect sensing data xi, perform the double-masking scheme to mask the raw input data yi (yi=distxi−x∗), and then send the masked input data zi to S. The server S receives masked input data zi from each user ui and aggregates the input data of online users. Each user ui can drop out at any time. As long as the number of surviving users is not less than the threshold t, S can eliminate the deviation caused by dropped users and restore the aggregation results. The detailed process is as follows.Step 0 (Key Generation). Assume N users submit sensing data in the data submission phase. Given the security parameter k and threshold value t, a trusted third party creates three key pairs for each user ui as follows.(9)PKis,SKis,PKia,SKia,PKir,SKir←KA.genk,wherePKis,SKis are used for signature, PKia,SKia are used to generate a session key with other users for symmetric encryption, and PKir,SKir are used to generate a session key with other users uj as the noise ri,j. Then, each user ui signs two public keys using SKis as ρi←sign⋅SKis,PKis‖PKir and sends ρi‖PKia‖PKir to S.When receiving messages from at leastt users (which denotes the surviving users as a set U1⊆U), S broadcasts uj,ρj,PKja,PKjruj∈U1 to all users. Otherwise, abort.Step 1 (Key Sharing). After receiving the information from S, each user ui confirms whether U1≥t; then, ui verifies whether the signature ρj is valid using the public key PKjs for other user uj. If not, abort. Next, ui selects a random parameter ni←ℱ and generates shares of ni and SKir as follows.(10)uj,nj,iuj∈U1←Shamir.shareni,t,U1,uj,SKj,iruj∈U1←Shamir.shareSKir,t,U1.Then, each userui generates a session key with other users uj∈U1\ui and uses the symmetric authenticated encryption to encrypt two types of shares as follows.(11)Tj,i←AE.encKA.agreeSKia,PKja,uiujnj,iSKj,ir,where the symmetric authenticated encryption is indistinguishable under ciphertext integrity attack and chosen plaintext attack. It can ensure the confidentiality and integrity of messages, which are exchanged between two parties. We do not repeat the details here. If any of the above processes fails, abort. Otherwise, each userui sends Tj,i to S.When receiving messages from at leastt users (which denotes the surviving users as a set U2), S randomly initializes the ground truth x∗ and then broadcasts Tj,iuj∈U2 and x∗ to all users. Otherwise, abort.Step 2 (Masking Input Data). After receiving x∗ and Tj,iuj∈U2 from S, each user ui confirms whether U2≥t, then computes ri,j←KA.agreeSKir,PKjr for every user uj∈U2\ui, and gets masked input data zi2 as follows.(12)zi2=yi2+∑j∈U2:i<jPRGri,j−∑j∈U2:i>jPRGri,j+PRGnimodR=distxi,x∗+∑j∈U2:i<jPRGri,j−∑j∈U2:i>jPRGri,j+PRGnimodR,wheredistxi,x∗ is the input data in the second round, represented by yi2 for convenience, and zi2 indicates the masked input data. If any of the above processes fails, abort. Otherwise, each user ui sends zi2ui∈U2 to S.When receivingzi2 from at least t users (which denotes the surviving users as a set U3), S sends the list of U3 to all users. Otherwise, abort.Step 3 (Consistency Check). After receiving the list of U3 from S, each user ui confirms whether U3≥t. Then, ui calculates the signature ρi′←sign⋅SKis,U3 and sends it to S.When receivingρi′ from at least t users (which denotes the surviving users as a set U4), S sends uj,ρj′uj∈U4 to all users. Otherwise, abort.Step 4 (Unmasking). After receiving the list of U4 from S, each user ui confirms whether U4⊆U3, U4≥t, and the signature ρj′ is valid using the public key PKjs. Then, ui decrypts Tj,i for users uj∈U2\ui as follows.(13)ui′uj′nj,iSKj,ir←AE.decKA.agreeSKia,PKja,Tj,i.Then,nj,iuj∈U3 and SKj,iruj∈U2\U3 will be sent to S if ui=ui′ and uj=uj′. If any of the above processes fails, abort.After receiving messages from users,S performs the deviation elimination and regards users who modify the data as dropped users, and S discards dropped users’ data. The surviving users are then denoted as a set U5⊆U4. If U5≥t, the secret key SKir and masks PRGri,j,ui∈U2\U3 can be reconstructed as follows.(14)SKir←Shamir.reconSKj,iruj∈U5,t,PRGri,j←PRGKA.agreeSKir,PKjruj∈U3.Furthermore, thePRGni,ui∈U3 can be reconstructed as follows.(15)PRGni←PRGShamir.reconnj,i,tuj∈U5.Next, the aggregated results ofyi2 can be calculated as follows.(16)∑ui∈U3yi2=∑ui∈U3yi2−∑uj∈U3PRGni−∑ui∈U3,uj∈U2\U3:i<jPRGri,j+∑ui∈U3,uj∈U2\U3:i<jPRGri,jmodR=∑ui∈U3distxi,x∗.Then,S selects a random positive noise value m to mask the raw aggregation results to prevent users from obtaining weight information.(17)Wresult=Log∑ui∈U3distxi,x∗+m.Next,S sends Wresult to all users.Step 5 (Masked Input Generation). After receiving Wresult from S, each user ui computes ri,j←KA.agreeSKir,PKjr for every surviving user uj∈U5\ui. Then, each user ui calculates the masked weight information as follows.(18)zi5′=Wresult−Logdistxi,x∗+PRGni+∑uj∈U5:i>jPRGri,j−∑uj∈U5:i<jPRGri,jmodR=wi+m+PRGni+∑uj∈U5:i>jPRGri,j−∑uj∈U5:i<jPRGri,jmodR,zi5″=Wresult−Logdistxi,x∗⋅xi+PRGni+∑uj∈U5:i>jPRGri,j−∑uj∈U5:i<jPRGri,jmodR=wi+m⋅xi+PRGni+∑uj∈U5:i>jPRGri,j−∑uj∈U5:i<jPRGri,jmodR.So, the masked input data are denoted aszi5′,zi5″, where the raw input data are yi5′=wi+m,yi5″=wi+m⋅xi. If any of the above processes fails, abort. Otherwise, each user ui sends zi5′,zi5″ to S.Step 6 (Unmasking). After receiving zi5′,zi5″ from at least t users (which denotes the surviving users as a set U6), S sends the list of U6 to all users. Otherwise, abort. Then, each user uj∈U6\ui decrypts Tj,i as follows.(19)ui′uj′nj,iSKj,ir←AE.decKA.agreeSKia,PKja,Tj,i.Then,nj,iuj∈U6 and SKj,iruj∈U5\U6 will be sent to S if ui=ui′ and uj=uj′. If any of the above processes fails, abort.After receiving the information from at leastt users (which denotes the surviving users as a set U7), S restores the secret key SKir, uj=uj′ for each user uj∈U5\U6 and PRGniui∈U6 as follows.(20)SKir←Shamir.reconSKj,iruj∈U7,t,PRGri,j←PRGKA.agreeSKir,PKjruj∈U6,PRGni←PRGShamir.reconnj,i,tuj∈U7.Then,S can calculate the aggregation results as follows.(21)∑ui∈U6yi5′=∑ui∈U6zi5′−∑ui∈U6PRGni−∑ui∈U6,uj∈U5∖U6:i<jPRGri,j+∑ui∈U6,uj∈U5∖U6:i>jPRGrj,imodR=∑ui∈U6wi+m,∑ui∈U6yi5″=∑ui∈U6zi5″−∑ui∈U6PRGni−∑ui∈U6,uj∈U5∖U6:i<jPRGri,j+∑ui∈U6,uj∈U5∖U6:i>jPRGrj,imodR=∑ui∈U6wi+m⋅xi.Next,S eliminates the random noise value m as follows.(22)Wresult′=∑ui∈U6yi5′mod∑ui∈U6m=∑ui∈U6wi+∑ui∈U6mmod∑ui∈U6m=∑ui∈U6wi,Wresult″=∑ui∈U6yi5″mod∑ui∈U6m=∑ui∈U6wi+m⋅ximod∑ui∈U6m=∑ui∈U6wi⋅xi.Therefore, the current ground truthx∗ and the weight wi of every user ui∈U6 can be calculated using formulas (1) and (2) as follows.(23)x∗=∑ui∈U6wi⋅xi∑ui∈U6wi=Wresult″Wresult′,wi=Log∑ui∈U6distxi,x∗distxi,x∗.Thus,S can get the final ground truth x∗ and the weight wi of every user ui by repeating steps 0 to 6 until the convergence conditions are met. And the weight wi will be used to calculate the data quality qi of each user ui.


### 5.4. Reward Distribution

The weightui calculated by truth discovery can represent the effective contribution of users. Still, to facilitate reward distribution, we need to quantify the data quality qi of every user ui further. Then, S can compute the monetary reward pi according to the data quality qi of ui.To achieve the rationality of reward distribution, we set∑ui∈U6qi=1, so the data quality qi of each user ui can be calculated as follows.(24)qi=wi∑ui∈U6wi.Next, we calculate the monetary rewardpi of each user ui as follows. And the higher the quality qi of ui’s data, the more reward ui can get.(25)pi=BU6+π⋅qi−q¯,where q¯q¯=∑ui∈U6qi/U6=1/U6 is the average quality of all surviving users. π0<π<B/N represents the reward control parameter, which is a small rational number. The function of π is to ensure that the reward pi is non-negative. And U6 is the number of surviving users.SinceU6≤N, we can know that the lowest reward pi which a user can get is B−π/N. When the number of final online users U6=N, each user ui’s reward is pi=B/N+π⋅qi−q¯. If some users dropped out and U6<N, S will distribute the task budget to each surviving user ui∈U6, and each user ‘s reward is pi=B/U6+π⋅qi−q¯. Therefore, our reward distribution formula is applicable regardless of whether there are users offline.


## 5.1. Overview

For convenience, we introduce a simple case. We set up a sensing taskT to collect the temperature of urban roads in the evening. There are range requirements for time, location, and sensing data (i.e., temperature). To be more precise, the time range is required to be 5–8 pm on February 3rd, the location range is required to be 12.45–12.55 E and 41.79–41.99 N, and the temperature requirement is 10–15°C. In our PAID, we consider the range requirement as the data eligibility requirement E. The data Di (Di=xi,τi,ιi^,ιi˜) collected by a user ui meet the eligibility requirements E, meaning that 10≤xi≤15,5≤τi≤8,12.45≤ιi^≤12.55,41.79≤ιi˜≤41.99. Since the data collected by mobile devices are usually rational numbers, in our PAID, we transform the eligible interval into an integer interval by moving the decimal point right. The sensing task T consists of three entities: a task publisher (TP), a server (S), and users. And the specific steps are as follows.Step 1 (Task Publish). The task publisher TP initializes a public key pkT and a private key skT, a reward control parameter π (π is a decimal number), a task budget B, the number of users N, and eligibility requirements E for a sensing task T. The public key pkT is used to encrypt the information that the server S needs to send to the TP, and the TP decrypts the ciphertext using the private key skT. Then, the TP sends the information T,pkT,π,N,B,Ε to S as a task request.Step 2 (User Recruitment). The server S broadcasts the sensing task information T,π,N,B and recruits N users who request to participate in the sensing task. Then, S generates a key pair PKSi,SKSi using the key agreement scheme for every user ui and sends PKSi to ui.Step 3 (Eligibility Assessment). Each user ui confirms whether ci≤B−π/N, where ci denotes the sensing cost of ui, and the posted lowest reward is denoted as B−π/N. If ci≤B−π/N, and ui starts the sensing task and collects the data Di. The user ui then generates a key pair PKi,SKi using the key agreement scheme and computes a session key ki←KA.agreeSKi,PKSi as ui’s anonymous identity information. Then, the user ui performs the interval judgment scheme insDi,E and sends the public key PKi to S. Specifically, insDi,E is divided into insxi,E, insτi,E, insιi^,E, insιi˜,E.Step 4 (Prepayment). After recruiting N eligible users, the server S requests TP to prepay a budget reward B for the sensing task T to prevent the denial of payment attack. And the server S calculates the session key ki←KA.agreeSKSi,PKi with the eligible user ui.Step 5 (Submission Notification). After getting the budget reward B, the server S informs the eligible user ui1≤i≤N to submit data.Step 6 (Data Submission and Eligibility Confirmation). After receiving the submission notification, each user ui performs double-masking scheme to mask the sensing data xi and get yi and , at the same time, executes eligibility confirmation insDi,E to prevent malicious users from modifying data. Then, ui encrypts the data yi using the symmetric encryption algorithm and sends the ciphertext SEncyi,ki to S. The session key ki is the key of symmetric encryption.Step 7 (Deviation Elimination). For users who tamper with data during data submission, the server S regards them as dropped users and discards their data. Then, S gets plaintext SDecSEncyi,ki,ki and requests seed ni and the noise ri,j between the dropped user ui and the surviving user uj to eliminate the impact on the aggregate result.Step 8 (Secure Truth Discovery). The server S computes the surviving user ui’s weight wi and the ground truth x∗ of the sensing object utilizing the truth discovery algorithm. The detailed algorithm process will be introduced later.Step 9 (Reward Distribution). The server S calculates the sensing data quality qi=wi/∑i=1mwi of ui, where ∑i=1mqi=1, m is the number of online users. Then, S pays a monetary reward pi=B/m+π⋅qi−q¯ for ui, where π⋅qi−q¯ denotes the payment parameter, m≤N, and 1≤i≤m.Step 10 (Task Completion). The server S encrypts the ground truth x∗ using pkT and sends Encx∗,pkT to TP. And the TP can decrypt the data using skT, i.e., x∗=DecEncx∗,pkT,skT.In our PAID, only users who passed the eligibility assessment and eligibility confirmation can obtain the monetary reward. Thus, users cannot cheatS to get a reward with unreliable data. We can also ensure the quality of the sensing data used by the truth discovery algorithm and obtain more accurate ground truth x∗. Moreover, since the TP pays the task reward to S in advance and S will pay a reward to ui according to the quality of ui’s sensing data after the task is accomplished, the TP cannot refuse to pay the reward. Besides, S cannot get users’ raw sensing data, time, and location information, which can protect the users’ privacy. The anonymous identity of each user is determined by both the user and S. S only assigns one random identity token to each user, so malicious users cannot forge multiple identities.


## 5.2. Eligibility Assessment

In our PAID, there are three benefits to the design of the eligibility assessment. First, it can prevent users who provide unreliable or erroneous sensing data from receiving monetary rewards, which avoids wasting budgets. Secondly, filtering out unqualified sensing data can improve the accuracy of the sensing task result. Thirdly, the data qualityqi of each user ui is related to the sensing object’s ground truth x∗, and inaccurate ground truth will lead to unfair incentives.The process of eligibility assessment and eligibility confirmation is similar. The purpose of the eligibility assessment is to filter out unqualified users preliminarily. Thus, the unqualified users do not need to communicate with other users to perform the double-masking scheme, by which the communication overhead can be reduced. The eligibility confirmation is designed to prevent malicious users from altering the original qualified data. The detailed process of eligibility assessment and eligibility confirmation is as follows.Step 1. Each user ui initializes a key pair pkpi,skpi←Paillier.genN,g. Then, ui encrypts the sensing data Di using pkpi and sends the ciphertext EDi to S. Generally, EDi consists of four parts: Exi, Eτi, Eιi^, and Eιi˜.Step 2. After receiving EDi, the server S picks different random k,bk,b←Z∗ and constructs a monotone increasing (or decreasing) function fDi=kDi+b for each value in the quadruples xi,τi,ιi^,ιi˜. The monotonicity of the four functions is inconsistent. For eligibility requirement interval E (E=Ex,Eτ,Eι^,Eι˜,Ex=xl,xr,Eτ=τl,τr,Eι^=ι^l,ι^r,Eι˜=ι˜l,ι˜r), the server S calculates(8)fxl,fxr,c1=Exik1,Eb1=Ek1xi+b1,fτl,fτr,c2=Eτik2,Eb2=Ek2τi+b2,fι^l,fι^r,c3=Eι^ik3,Eb3=Ek3ι^i+b3,fι˜l,fι˜r,c4=Eι˜ik4,Eb4=Ek4ι˜i+b4.Then,S sends fEl,fEr,c (c=c1,c2,c3,c4) to ui. For convenience, we will not describe Di and E separately in the following text.Step 3. After receiving fEl,fEr,c from S, each user ui gets fDi←Paillier.decc,skpi and then compares the size of fEl,fEr,fDi. Next, the size relationship is sent to S.Step 4. After the server S receives the information from ui, if fEl≤fDi≤fEr, then Di∈El,Er because of the monotonicity of the functions. And S determines whether ui passes the eligibility assessment. Otherwise, it fails.Because users do not know the function’s monotonicity, they cannot infer the size relationship between the qualified data and eligibility requirement. Therefore, we can think that malicious users have a very low probability of passing the eligibility assessment. Moreover, during the eligibility assessment,ui cannot know the specific qualified interval. S also cannot get ui’s sensing data, which can protect ui’s privacy. The above process is represented by insDi,E. If ui passes the eligibility assessment, then insDi,E=1. If not, insDi,E=0.


## 5.3. Secure Truth Discovery

In the secure truth discovery scheme [15], data exchange is between users and the server S. The user ui needs to collect sensing data xi, perform the double-masking scheme to mask the raw input data yi (yi=distxi−x∗), and then send the masked input data zi to S. The server S receives masked input data zi from each user ui and aggregates the input data of online users. Each user ui can drop out at any time. As long as the number of surviving users is not less than the threshold t, S can eliminate the deviation caused by dropped users and restore the aggregation results. The detailed process is as follows.Step 0 (Key Generation). Assume N users submit sensing data in the data submission phase. Given the security parameter k and threshold value t, a trusted third party creates three key pairs for each user ui as follows.(9)PKis,SKis,PKia,SKia,PKir,SKir←KA.genk,wherePKis,SKis are used for signature, PKia,SKia are used to generate a session key with other users for symmetric encryption, and PKir,SKir are used to generate a session key with other users uj as the noise ri,j. Then, each user ui signs two public keys using SKis as ρi←sign⋅SKis,PKis‖PKir and sends ρi‖PKia‖PKir to S.When receiving messages from at leastt users (which denotes the surviving users as a set U1⊆U), S broadcasts uj,ρj,PKja,PKjruj∈U1 to all users. Otherwise, abort.Step 1 (Key Sharing). After receiving the information from S, each user ui confirms whether U1≥t; then, ui verifies whether the signature ρj is valid using the public key PKjs for other user uj. If not, abort. Next, ui selects a random parameter ni←ℱ and generates shares of ni and SKir as follows.(10)uj,nj,iuj∈U1←Shamir.shareni,t,U1,uj,SKj,iruj∈U1←Shamir.shareSKir,t,U1.Then, each userui generates a session key with other users uj∈U1\ui and uses the symmetric authenticated encryption to encrypt two types of shares as follows.(11)Tj,i←AE.encKA.agreeSKia,PKja,uiujnj,iSKj,ir,where the symmetric authenticated encryption is indistinguishable under ciphertext integrity attack and chosen plaintext attack. It can ensure the confidentiality and integrity of messages, which are exchanged between two parties. We do not repeat the details here. If any of the above processes fails, abort. Otherwise, each userui sends Tj,i to S.When receiving messages from at leastt users (which denotes the surviving users as a set U2), S randomly initializes the ground truth x∗ and then broadcasts Tj,iuj∈U2 and x∗ to all users. Otherwise, abort.Step 2 (Masking Input Data). After receiving x∗ and Tj,iuj∈U2 from S, each user ui confirms whether U2≥t, then computes ri,j←KA.agreeSKir,PKjr for every user uj∈U2\ui, and gets masked input data zi2 as follows.(12)zi2=yi2+∑j∈U2:i<jPRGri,j−∑j∈U2:i>jPRGri,j+PRGnimodR=distxi,x∗+∑j∈U2:i<jPRGri,j−∑j∈U2:i>jPRGri,j+PRGnimodR,wheredistxi,x∗ is the input data in the second round, represented by yi2 for convenience, and zi2 indicates the masked input data. If any of the above processes fails, abort. Otherwise, each user ui sends zi2ui∈U2 to S.When receivingzi2 from at least t users (which denotes the surviving users as a set U3), S sends the list of U3 to all users. Otherwise, abort.Step 3 (Consistency Check). After receiving the list of U3 from S, each user ui confirms whether U3≥t. Then, ui calculates the signature ρi′←sign⋅SKis,U3 and sends it to S.When receivingρi′ from at least t users (which denotes the surviving users as a set U4), S sends uj,ρj′uj∈U4 to all users. Otherwise, abort.Step 4 (Unmasking). After receiving the list of U4 from S, each user ui confirms whether U4⊆U3, U4≥t, and the signature ρj′ is valid using the public key PKjs. Then, ui decrypts Tj,i for users uj∈U2\ui as follows.(13)ui′uj′nj,iSKj,ir←AE.decKA.agreeSKia,PKja,Tj,i.Then,nj,iuj∈U3 and SKj,iruj∈U2\U3 will be sent to S if ui=ui′ and uj=uj′. If any of the above processes fails, abort.After receiving messages from users,S performs the deviation elimination and regards users who modify the data as dropped users, and S discards dropped users’ data. The surviving users are then denoted as a set U5⊆U4. If U5≥t, the secret key SKir and masks PRGri,j,ui∈U2\U3 can be reconstructed as follows.(14)SKir←Shamir.reconSKj,iruj∈U5,t,PRGri,j←PRGKA.agreeSKir,PKjruj∈U3.Furthermore, thePRGni,ui∈U3 can be reconstructed as follows.(15)PRGni←PRGShamir.reconnj,i,tuj∈U5.Next, the aggregated results ofyi2 can be calculated as follows.(16)∑ui∈U3yi2=∑ui∈U3yi2−∑uj∈U3PRGni−∑ui∈U3,uj∈U2\U3:i<jPRGri,j+∑ui∈U3,uj∈U2\U3:i<jPRGri,jmodR=∑ui∈U3distxi,x∗.Then,S selects a random positive noise value m to mask the raw aggregation results to prevent users from obtaining weight information.(17)Wresult=Log∑ui∈U3distxi,x∗+m.Next,S sends Wresult to all users.Step 5 (Masked Input Generation). After receiving Wresult from S, each user ui computes ri,j←KA.agreeSKir,PKjr for every surviving user uj∈U5\ui. Then, each user ui calculates the masked weight information as follows.(18)zi5′=Wresult−Logdistxi,x∗+PRGni+∑uj∈U5:i>jPRGri,j−∑uj∈U5:i<jPRGri,jmodR=wi+m+PRGni+∑uj∈U5:i>jPRGri,j−∑uj∈U5:i<jPRGri,jmodR,zi5″=Wresult−Logdistxi,x∗⋅xi+PRGni+∑uj∈U5:i>jPRGri,j−∑uj∈U5:i<jPRGri,jmodR=wi+m⋅xi+PRGni+∑uj∈U5:i>jPRGri,j−∑uj∈U5:i<jPRGri,jmodR.So, the masked input data are denoted aszi5′,zi5″, where the raw input data are yi5′=wi+m,yi5″=wi+m⋅xi. If any of the above processes fails, abort. Otherwise, each user ui sends zi5′,zi5″ to S.Step 6 (Unmasking). After receiving zi5′,zi5″ from at least t users (which denotes the surviving users as a set U6), S sends the list of U6 to all users. Otherwise, abort. Then, each user uj∈U6\ui decrypts Tj,i as follows.(19)ui′uj′nj,iSKj,ir←AE.decKA.agreeSKia,PKja,Tj,i.Then,nj,iuj∈U6 and SKj,iruj∈U5\U6 will be sent to S if ui=ui′ and uj=uj′. If any of the above processes fails, abort.After receiving the information from at leastt users (which denotes the surviving users as a set U7), S restores the secret key SKir, uj=uj′ for each user uj∈U5\U6 and PRGniui∈U6 as follows.(20)SKir←Shamir.reconSKj,iruj∈U7,t,PRGri,j←PRGKA.agreeSKir,PKjruj∈U6,PRGni←PRGShamir.reconnj,i,tuj∈U7.Then,S can calculate the aggregation results as follows.(21)∑ui∈U6yi5′=∑ui∈U6zi5′−∑ui∈U6PRGni−∑ui∈U6,uj∈U5∖U6:i<jPRGri,j+∑ui∈U6,uj∈U5∖U6:i>jPRGrj,imodR=∑ui∈U6wi+m,∑ui∈U6yi5″=∑ui∈U6zi5″−∑ui∈U6PRGni−∑ui∈U6,uj∈U5∖U6:i<jPRGri,j+∑ui∈U6,uj∈U5∖U6:i>jPRGrj,imodR=∑ui∈U6wi+m⋅xi.Next,S eliminates the random noise value m as follows.(22)Wresult′=∑ui∈U6yi5′mod∑ui∈U6m=∑ui∈U6wi+∑ui∈U6mmod∑ui∈U6m=∑ui∈U6wi,Wresult″=∑ui∈U6yi5″mod∑ui∈U6m=∑ui∈U6wi+m⋅ximod∑ui∈U6m=∑ui∈U6wi⋅xi.Therefore, the current ground truthx∗ and the weight wi of every user ui∈U6 can be calculated using formulas (1) and (2) as follows.(23)x∗=∑ui∈U6wi⋅xi∑ui∈U6wi=Wresult″Wresult′,wi=Log∑ui∈U6distxi,x∗distxi,x∗.Thus,S can get the final ground truth x∗ and the weight wi of every user ui by repeating steps 0 to 6 until the convergence conditions are met. And the weight wi will be used to calculate the data quality qi of each user ui.


## 5.4. Reward Distribution

The weightui calculated by truth discovery can represent the effective contribution of users. Still, to facilitate reward distribution, we need to quantify the data quality qi of every user ui further. Then, S can compute the monetary reward pi according to the data quality qi of ui.To achieve the rationality of reward distribution, we set∑ui∈U6qi=1, so the data quality qi of each user ui can be calculated as follows.(24)qi=wi∑ui∈U6wi.Next, we calculate the monetary rewardpi of each user ui as follows. And the higher the quality qi of ui’s data, the more reward ui can get.(25)pi=BU6+π⋅qi−q¯,where q¯q¯=∑ui∈U6qi/U6=1/U6 is the average quality of all surviving users. π0<π<B/N represents the reward control parameter, which is a small rational number. The function of π is to ensure that the reward pi is non-negative. And U6 is the number of surviving users.SinceU6≤N, we can know that the lowest reward pi which a user can get is B−π/N. When the number of final online users U6=N, each user ui’s reward is pi=B/N+π⋅qi−q¯. If some users dropped out and U6<N, S will distribute the task budget to each surviving user ui∈U6, and each user ‘s reward is pi=B/U6+π⋅qi−q¯. Therefore, our reward distribution formula is applicable regardless of whether there are users offline.


## 6. Analysis

In this section, we introduce property analysis, privacy analysis, and security analysis to illustrate the feasibility of our PAID.


### 6.1. Property Analysis

In this section, we introduce eligibility, zero knowledge, payment rationality, and budget rationality of our PAID.Theorem 1.
(eligibility)If the dataDi (Di=xi,τi,ιi^,ιi˜) collected by users do not meet the eligibility requirement E, these users cannot pass the eligibility assessment.Proof.
We assume that the user’s data are denoted ass, and the eligibility requirement interval is a,b. The user gets ciphertext Es using homomorphic encryption. Then, S picks different random k,b and constructs a monotone increasing (or decreasing) function fx=kx+b. Then, S computes fa, fb, and c=EskEb=Eks+b. When receiving fa, fb, c from S, the user decrypts c to get fs and compares the sizes of fa, fb, fs. Because the user does not know the monotonicity of the function, it is impossible to determine the size relationship among the three numbers. Therefore, if the user’s data are not qualified, then it cannot pass the qualification judgment.Theorem 2.
(zero knowledge)The serverS can determine whether the user’s data meet the eligibility requirements, but it cannot know the user’s specific data content.Proof.
Similar to the description in Theorem1, we assume that the user’s data are s, and the server S can receive the user’s homomorphic encrypted ciphertext Es. Since the Paillier cryptosystem is indistinguishable under the chosen plaintext attack, a malicious user has no way to recover the plaintext s. The server S may be curious about each user’s data, but it cannot obtain each user’s data s without knowing the secret key.Theorem 3.
(payment rationality)If an honest userui provides qualified data, ui can obtain a non-negative utility.Proof.
The utilityuti of each user ui is determined by the cost of ui and the real reward from task publisher TP, i.e., uti=pi−ci.
If the data provided by an untrusted userui are not qualified, ui cannot pass the eligibility assessment, so the untrusted user’s utility uti=0. However, when ci>B−π/N (B−π/N is the posted lowest pricing), an honest user ui will refuse to participate in the sensing task, so the trusted user’s utility uti=0. When ci≤B−π/N, an honest user ui will participate in the sensing task and earn a reward pi=B/m+π⋅qi−q¯. Since q¯=∑i=1mqi/m=1/m, 0<qi<1, and m≤N, we have(26)pi=Bm+π⋅qi−q¯=B−πm+π⋅qi>B−πN.
Therefore, we can know thatpi−ci>0. To summarize, a user’s real reward is always non-negative.Theorem 4.
(budget rationality)The total payment of the task publisher TP is no larger than budgetB in our PAID.Proof.
The total rewards for all users are calculated as follows.(27)∑i=0mpi=∑i=0mBm+π⋅qi−q¯=B+π⋅∑i=0mqi−∑i=1mqim=B+π⋅∑i=0mqi−1=B.
Hence,∑i=0mpi≤B, i.e., our PAID is budget rational.


### 6.2. Privacy Analysis

In this section, we demonstrate the protection of user’s sensing data, location, and identity privacy in our PAID.Theorem 5.
(data and location privacy protection)Except for the user himself, other parties cannot obtain the user’s sensing data and location data.Proof.
In PAID, the objects that steal users’ data and location privacy are mainly the serverS and external attackers. Specifically, the server S may obtain users’ sensing data and location privacy in eligibility assessment and truth discovery. External attackers steal data and location privacy by eavesdropping on the communication between the server S and users.
According to Theorem2, we can know that our PAID has the property of zero knowledge, so the server S cannot learn users’ sensing data and location data in the eligibility assessment. In truth discovery, users’ sensing data are sent to S after performing the double-masking scheme. However, the server S cannot recover users’ raw sensing data by double-masking sensing data. Furthermore, before the communication between the user ui and S, the data are encrypted by AES symmetric encryption function SEncyi,ki. Therefore, as long as SEncyi,ki is secure, external attackers cannot steal the data yi by eavesdropping communication.Theorem 6.
(identity privacy protection)When users participate in a sensing task, they use an anonymous identity rather than their real identity. Therefore, any PPT adversary cannot distinguish the users’ identities.Proof.
In PAID, the anonymous identity of a userui is represented by ki←KA.agreeSKi,PKSi, and the real identity of ui is SKi where SKi=xi←Zq, and PKSi=gxSi (PKSi is a token assigned by S). The user ui uses an anonymous identity ki rather than a real identity SKi to participate in a sensing task. Because of the DDH problem, the PPT adversary cannot get the real identity SKi of the user ui by the anonymous identity ki. We omit the detailed proof, and interested readers can learn more details in the literature [36].


### 6.3. Security Analysis

In this section, we describe the attacks our PAID can resist, including denial of payment attack (DoP), inference attack (IA), data pollution attack (DPA), and Sybil attack (SA).(1)
Resistance to Denial of Payment Attack (DoP). We use the prepayment mechanism in our PAID. At the beginning of a sensing task, the task publisher TP pays the monetary rewards of users to S in advance. If a malicious TP refuses to pay the monetary reward after receiving the data, S can pay the reward to users according to the reward distribution formula. Therefore, the TP cannot refuse to pay users the reward.(2)
Resistance to Inference Attack (IA). The server S cannot initiate an inference attack on users’ data due to the zero-knowledge property of our PAID.(3)
Resistance to Data Pollution Attack (DPA). Our PAID introduces eligibility assessment, and the unqualified data submitted by users are not used in the truth discovery algorithm. Therefore, our PAID can resist the data pollution attack (DPA).(4)
Resistance to Sybil Attack (SA). The anonymous identity ki of a user ui needs the information PKi provided by the user and the token PKSi assigned by S. Each user can only obtain one token from S and then get the anonymous identity ki using the key agreement algorithm. Hence, untrusted users cannot forge vast fake identities to launch the Sybil attack (SA).


## 6.1. Property Analysis

In this section, we introduce eligibility, zero knowledge, payment rationality, and budget rationality of our PAID.Theorem 1.
(eligibility)If the dataDi (Di=xi,τi,ιi^,ιi˜) collected by users do not meet the eligibility requirement E, these users cannot pass the eligibility assessment.Proof.
We assume that the user’s data are denoted ass, and the eligibility requirement interval is a,b. The user gets ciphertext Es using homomorphic encryption. Then, S picks different random k,b and constructs a monotone increasing (or decreasing) function fx=kx+b. Then, S computes fa, fb, and c=EskEb=Eks+b. When receiving fa, fb, c from S, the user decrypts c to get fs and compares the sizes of fa, fb, fs. Because the user does not know the monotonicity of the function, it is impossible to determine the size relationship among the three numbers. Therefore, if the user’s data are not qualified, then it cannot pass the qualification judgment.Theorem 2.
(zero knowledge)The serverS can determine whether the user’s data meet the eligibility requirements, but it cannot know the user’s specific data content.Proof.
Similar to the description in Theorem1, we assume that the user’s data are s, and the server S can receive the user’s homomorphic encrypted ciphertext Es. Since the Paillier cryptosystem is indistinguishable under the chosen plaintext attack, a malicious user has no way to recover the plaintext s. The server S may be curious about each user’s data, but it cannot obtain each user’s data s without knowing the secret key.Theorem 3.
(payment rationality)If an honest userui provides qualified data, ui can obtain a non-negative utility.Proof.
The utilityuti of each user ui is determined by the cost of ui and the real reward from task publisher TP, i.e., uti=pi−ci.
If the data provided by an untrusted userui are not qualified, ui cannot pass the eligibility assessment, so the untrusted user’s utility uti=0. However, when ci>B−π/N (B−π/N is the posted lowest pricing), an honest user ui will refuse to participate in the sensing task, so the trusted user’s utility uti=0. When ci≤B−π/N, an honest user ui will participate in the sensing task and earn a reward pi=B/m+π⋅qi−q¯. Since q¯=∑i=1mqi/m=1/m, 0<qi<1, and m≤N, we have(26)pi=Bm+π⋅qi−q¯=B−πm+π⋅qi>B−πN.
Therefore, we can know thatpi−ci>0. To summarize, a user’s real reward is always non-negative.Theorem 4.
(budget rationality)The total payment of the task publisher TP is no larger than budgetB in our PAID.Proof.
The total rewards for all users are calculated as follows.(27)∑i=0mpi=∑i=0mBm+π⋅qi−q¯=B+π⋅∑i=0mqi−∑i=1mqim=B+π⋅∑i=0mqi−1=B.
Hence,∑i=0mpi≤B, i.e., our PAID is budget rational.


## 6.2. Privacy Analysis

In this section, we demonstrate the protection of user’s sensing data, location, and identity privacy in our PAID.Theorem 5.
(data and location privacy protection)Except for the user himself, other parties cannot obtain the user’s sensing data and location data.Proof.
In PAID, the objects that steal users’ data and location privacy are mainly the serverS and external attackers. Specifically, the server S may obtain users’ sensing data and location privacy in eligibility assessment and truth discovery. External attackers steal data and location privacy by eavesdropping on the communication between the server S and users.
According to Theorem2, we can know that our PAID has the property of zero knowledge, so the server S cannot learn users’ sensing data and location data in the eligibility assessment. In truth discovery, users’ sensing data are sent to S after performing the double-masking scheme. However, the server S cannot recover users’ raw sensing data by double-masking sensing data. Furthermore, before the communication between the user ui and S, the data are encrypted by AES symmetric encryption function SEncyi,ki. Therefore, as long as SEncyi,ki is secure, external attackers cannot steal the data yi by eavesdropping communication.Theorem 6.
(identity privacy protection)When users participate in a sensing task, they use an anonymous identity rather than their real identity. Therefore, any PPT adversary cannot distinguish the users’ identities.Proof.
In PAID, the anonymous identity of a userui is represented by ki←KA.agreeSKi,PKSi, and the real identity of ui is SKi where SKi=xi←Zq, and PKSi=gxSi (PKSi is a token assigned by S). The user ui uses an anonymous identity ki rather than a real identity SKi to participate in a sensing task. Because of the DDH problem, the PPT adversary cannot get the real identity SKi of the user ui by the anonymous identity ki. We omit the detailed proof, and interested readers can learn more details in the literature [36].


## 6.3. Security Analysis

In this section, we describe the attacks our PAID can resist, including denial of payment attack (DoP), inference attack (IA), data pollution attack (DPA), and Sybil attack (SA).(1)
Resistance to Denial of Payment Attack (DoP). We use the prepayment mechanism in our PAID. At the beginning of a sensing task, the task publisher TP pays the monetary rewards of users to S in advance. If a malicious TP refuses to pay the monetary reward after receiving the data, S can pay the reward to users according to the reward distribution formula. Therefore, the TP cannot refuse to pay users the reward.(2)
Resistance to Inference Attack (IA). The server S cannot initiate an inference attack on users’ data due to the zero-knowledge property of our PAID.(3)
Resistance to Data Pollution Attack (DPA). Our PAID introduces eligibility assessment, and the unqualified data submitted by users are not used in the truth discovery algorithm. Therefore, our PAID can resist the data pollution attack (DPA).(4)
Resistance to Sybil Attack (SA). The anonymous identity ki of a user ui needs the information PKi provided by the user and the token PKSi assigned by S. Each user can only obtain one token from S and then get the anonymous identity ki using the key agreement algorithm. Hence, untrusted users cannot forge vast fake identities to launch the Sybil attack (SA).


## 7. Performance Evaluation

In this section, we use a temperature dataset from Roma for performance evaluation. First, we describe the computational and communication overhead of the eligibility assessment. Then, we show the performance of the truth discovery algorithm. Finally, the comparison with the related work shows that the quality quantification and incentive mechanism are effective.In our experiment, the server has Intel(R) Xeon(R) E3-1231v3 3.4 GHz CPU, 16 GB RAM, 256 GB SSD, and 1 TB mechanical hard disk and runs on Ubuntu 18.04 operating system. These mobile devices are equipped with Android system with 2.2 GHz CPU and 4 GB RAM. The Roma temperature dataset includes users’ ID, date, time, longitude, latitude, and temperature. In particular, the range accuracy of location, time, and sensing data (temperature) is 1 meter, 1 second, and 0.01°C, respectively. Before performing the eligibility assessment, we convert the decimal interval to the corresponding integer interval by moving the decimal point to the right. Figure3 shows the statistical results of 232 qualified users. And we select 100 data from all qualified data for performance evaluation.Figure 3
Statistics of dataset. (a) Space-time statistics of users. (b) Temperature statistics of users.
(a)(b)


### 7.1. Evaluation of Eligibility Assessment

In this section, we analyze the computational and communication overhead in the eligibility assessment. Table2 shows the performance comparison between our PAID and related work.Table 2
Performance comparison between PAID and related work.
ProtocolComputational overheadCommunication overhead (bits)PAIDn⋅7⋅exp+3⋅mul+3⋅div+5⋅modN2+c[20]n⋅10⋅exp+5⋅mul+5⋅comp+5⋅mod3p+2cNote. p is a large prime. And exp, mul, div, comp, and mod represent one exponent arithmetic, one multiplication, one division, one comparison operation, and one modular arithmetic.


#### 7.1.1. Computational Overhead

The Paillier homomorphic encryption requires two exponentsexp, one multiplication mul, and one modular operation mod. One decryption operation needs to perform two exponents exp, three divisions div, and two modular operations mod. And in our interval judgment scheme, the user ui needs to perform one encryption and one decryption, so the computational cost of the user is 4n⋅exp+n⋅mul+3n⋅div+3n⋅mod, where n is the number of users. The server needs to perform one encryption Eb and calculates c=ExikEb, so the computational overhead of the server is 3n⋅exp+2n⋅mul+2n⋅mod. Consequently, the total computational overhead is n⋅7⋅exp+3⋅mul+3⋅div+5⋅mod and the computation complexity of the interval judgment scheme is On.


#### 7.1.2. Communication Overhead

According to our interval judgment scheme, users need to send encrypted dataExi to the server S, and the communication overhead is N2 bits, where N is the product of two large primes p,q. After receiving the encrypted data Exi, the server S calculates c=ExikEb and sends it to the user. The communication overhead is c bits, where c denotes the bit length of ciphertext. So, we can conclude that the total communication overhead is N2+c bits.


### 7.2. Evaluation of Truth Discovery

In this section, we select 100 users to participate in the performance comparison of truth discovery. We compare the truth discovery of our PAID with the related word from five aspects, including accuracy, convergence, robustness to users dropping out, computational overhead, and communication overhead. The evaluation results show that our truth discovery algorithm has good accuracy, quick convergence, and high robustness to users dropping out. Besides, the computational overhead and communication overhead of our algorithm are better than those of the related work. Therefore, our truth discovery algorithm is reasonable.


#### 7.2.1. Accuracy

We utilize the root of mean squared error (RMSE) to measure the resulting accuracy between PAID and CRH [32]. Figure 4 shows that the accuracy rates of PAID and CRH are similar when different numbers of users participate in a sensing task.Figure 4
Accuracy evaluation.


#### 7.2.2. Convergence

To prove the convergence ability of our truth discovery algorithm in PAID, we choose four different initial values to calculate the error rate of ground truth. As shown in Figure5, our PAID can converge quickly in a few iterations when choosing different initial values.Figure 5
Convergence evaluation.


#### 7.2.3. Robustness to Users Dropping Out

To analyze the robustness of our PAID to dropped users, we count the number of PAID failures and compare with related work PPTD [41]. Failure means that the model cannot continue to run and have to restart because of users’ exit. In the PPTD, it is considered as a failure once a user quits in the whole truth discovery process. In our PAID, it is deemed to be a failure only when the number of online users is less than the threshold t (t=25 in our experiment). And we repeat the experiment 50 times to count the failure times of the two models. Figure 6 shows the failure times of the two models when different users participate in a sensing task. We can know that the number of PPTD failures increases as the number of users increases. However, as long as online users’ number is greater than the threshold, our PAID is robust to dropped users.Figure 6
Robustness evaluation.


#### 7.2.4. Computational Overhead

We compare the computational overhead of PAID and PPTD [41]. Figure 7 shows the running time of the two schemes for different users. It is evident that the running time of our PAID is far less than that of PPTD.Figure 7
Running time for different number of users.


#### 7.2.5. Communication Overhead

We count the communication overhead of users in a complete iterative process and compare our scheme with PPTD [41]. And we do not count the server’s communication overhead because we can regard the total communication overhead of all users as the communication cost of the server. Table 3 shows that the communication overhead of our PAID is far less than that of PPTD, although the number of users is different.Table 3
Communication overhead of users (kB).
Number of usersPAIDPPTD500.161.38600.241.78700.321.86800.452.31900.582.631000.762.97


### 7.3. Evaluation of Incentive Mechanism

In this section, we compare the monetary rewards of our PAID and related work. In the experiment, we select 100 users, including 80 qualified users and 20 unqualified users. And the budgetB=100, π=0.3. DQTE [42] is a scheme that includes unqualified users in reward distribution, while DQTE+ removes unqualified users before reward distribution. As Figure 8 shows, users in DQTE get almost the same rewards. Although DQTE+ removes unqualified users, there is no obvious difference for users’ rewards except for the increase in each user’s monetary rewards. However, our scheme can provide higher monetary rewards for users who submit higher quality data. Therefore, our scheme can effectively motivate users to provide high-quality sensing data.Figure 8
The reward evaluation of users.


## 7.1. Evaluation of Eligibility Assessment

In this section, we analyze the computational and communication overhead in the eligibility assessment. Table2 shows the performance comparison between our PAID and related work.Table 2
Performance comparison between PAID and related work.
ProtocolComputational overheadCommunication overhead (bits)PAIDn⋅7⋅exp+3⋅mul+3⋅div+5⋅modN2+c[20]n⋅10⋅exp+5⋅mul+5⋅comp+5⋅mod3p+2cNote. p is a large prime. And exp, mul, div, comp, and mod represent one exponent arithmetic, one multiplication, one division, one comparison operation, and one modular arithmetic.


### 7.1.1. Computational Overhead

The Paillier homomorphic encryption requires two exponentsexp, one multiplication mul, and one modular operation mod. One decryption operation needs to perform two exponents exp, three divisions div, and two modular operations mod. And in our interval judgment scheme, the user ui needs to perform one encryption and one decryption, so the computational cost of the user is 4n⋅exp+n⋅mul+3n⋅div+3n⋅mod, where n is the number of users. The server needs to perform one encryption Eb and calculates c=ExikEb, so the computational overhead of the server is 3n⋅exp+2n⋅mul+2n⋅mod. Consequently, the total computational overhead is n⋅7⋅exp+3⋅mul+3⋅div+5⋅mod and the computation complexity of the interval judgment scheme is On.


### 7.1.2. Communication Overhead

According to our interval judgment scheme, users need to send encrypted dataExi to the server S, and the communication overhead is N2 bits, where N is the product of two large primes p,q. After receiving the encrypted data Exi, the server S calculates c=ExikEb and sends it to the user. The communication overhead is c bits, where c denotes the bit length of ciphertext. So, we can conclude that the total communication overhead is N2+c bits.


## 7.1.1. Computational Overhead

The Paillier homomorphic encryption requires two exponentsexp, one multiplication mul, and one modular operation mod. One decryption operation needs to perform two exponents exp, three divisions div, and two modular operations mod. And in our interval judgment scheme, the user ui needs to perform one encryption and one decryption, so the computational cost of the user is 4n⋅exp+n⋅mul+3n⋅div+3n⋅mod, where n is the number of users. The server needs to perform one encryption Eb and calculates c=ExikEb, so the computational overhead of the server is 3n⋅exp+2n⋅mul+2n⋅mod. Consequently, the total computational overhead is n⋅7⋅exp+3⋅mul+3⋅div+5⋅mod and the computation complexity of the interval judgment scheme is On.


## 7.1.2. Communication Overhead

According to our interval judgment scheme, users need to send encrypted dataExi to the server S, and the communication overhead is N2 bits, where N is the product of two large primes p,q. After receiving the encrypted data Exi, the server S calculates c=ExikEb and sends it to the user. The communication overhead is c bits, where c denotes the bit length of ciphertext. So, we can conclude that the total communication overhead is N2+c bits.


## 7.2. Evaluation of Truth Discovery

In this section, we select 100 users to participate in the performance comparison of truth discovery. We compare the truth discovery of our PAID with the related word from five aspects, including accuracy, convergence, robustness to users dropping out, computational overhead, and communication overhead. The evaluation results show that our truth discovery algorithm has good accuracy, quick convergence, and high robustness to users dropping out. Besides, the computational overhead and communication overhead of our algorithm are better than those of the related work. Therefore, our truth discovery algorithm is reasonable.


### 7.2.1. Accuracy

We utilize the root of mean squared error (RMSE) to measure the resulting accuracy between PAID and CRH [32]. Figure 4 shows that the accuracy rates of PAID and CRH are similar when different numbers of users participate in a sensing task.Figure 4
Accuracy evaluation.


### 7.2.2. Convergence

To prove the convergence ability of our truth discovery algorithm in PAID, we choose four different initial values to calculate the error rate of ground truth. As shown in Figure5, our PAID can converge quickly in a few iterations when choosing different initial values.Figure 5
Convergence evaluation.


### 7.2.3. Robustness to Users Dropping Out

To analyze the robustness of our PAID to dropped users, we count the number of PAID failures and compare with related work PPTD [41]. Failure means that the model cannot continue to run and have to restart because of users’ exit. In the PPTD, it is considered as a failure once a user quits in the whole truth discovery process. In our PAID, it is deemed to be a failure only when the number of online users is less than the threshold t (t=25 in our experiment). And we repeat the experiment 50 times to count the failure times of the two models. Figure 6 shows the failure times of the two models when different users participate in a sensing task. We can know that the number of PPTD failures increases as the number of users increases. However, as long as online users’ number is greater than the threshold, our PAID is robust to dropped users.Figure 6
Robustness evaluation.


### 7.2.4. Computational Overhead

We compare the computational overhead of PAID and PPTD [41]. Figure 7 shows the running time of the two schemes for different users. It is evident that the running time of our PAID is far less than that of PPTD.Figure 7
Running time for different number of users.


### 7.2.5. Communication Overhead

We count the communication overhead of users in a complete iterative process and compare our scheme with PPTD [41]. And we do not count the server’s communication overhead because we can regard the total communication overhead of all users as the communication cost of the server. Table 3 shows that the communication overhead of our PAID is far less than that of PPTD, although the number of users is different.Table 3
Communication overhead of users (kB).
Number of usersPAIDPPTD500.161.38600.241.78700.321.86800.452.31900.582.631000.762.97


## 7.2.1. Accuracy

We utilize the root of mean squared error (RMSE) to measure the resulting accuracy between PAID and CRH [32]. Figure 4 shows that the accuracy rates of PAID and CRH are similar when different numbers of users participate in a sensing task.Figure 4
Accuracy evaluation.


## 7.2.2. Convergence

To prove the convergence ability of our truth discovery algorithm in PAID, we choose four different initial values to calculate the error rate of ground truth. As shown in Figure5, our PAID can converge quickly in a few iterations when choosing different initial values.Figure 5
Convergence evaluation.


## 7.2.3. Robustness to Users Dropping Out

To analyze the robustness of our PAID to dropped users, we count the number of PAID failures and compare with related work PPTD [41]. Failure means that the model cannot continue to run and have to restart because of users’ exit. In the PPTD, it is considered as a failure once a user quits in the whole truth discovery process. In our PAID, it is deemed to be a failure only when the number of online users is less than the threshold t (t=25 in our experiment). And we repeat the experiment 50 times to count the failure times of the two models. Figure 6 shows the failure times of the two models when different users participate in a sensing task. We can know that the number of PPTD failures increases as the number of users increases. However, as long as online users’ number is greater than the threshold, our PAID is robust to dropped users.Figure 6
Robustness evaluation.


## 7.2.4. Computational Overhead

We compare the computational overhead of PAID and PPTD [41]. Figure 7 shows the running time of the two schemes for different users. It is evident that the running time of our PAID is far less than that of PPTD.Figure 7
Running time for different number of users.


## 7.2.5. Communication Overhead

We count the communication overhead of users in a complete iterative process and compare our scheme with PPTD [41]. And we do not count the server’s communication overhead because we can regard the total communication overhead of all users as the communication cost of the server. Table 3 shows that the communication overhead of our PAID is far less than that of PPTD, although the number of users is different.Table 3
Communication overhead of users (kB).
Number of usersPAIDPPTD500.161.38600.241.78700.321.86800.452.31900.582.631000.762.97


## 7.3. Evaluation of Incentive Mechanism

In this section, we compare the monetary rewards of our PAID and related work. In the experiment, we select 100 users, including 80 qualified users and 20 unqualified users. And the budgetB=100, π=0.3. DQTE [42] is a scheme that includes unqualified users in reward distribution, while DQTE+ removes unqualified users before reward distribution. As Figure 8 shows, users in DQTE get almost the same rewards. Although DQTE+ removes unqualified users, there is no obvious difference for users’ rewards except for the increase in each user’s monetary rewards. However, our scheme can provide higher monetary rewards for users who submit higher quality data. Therefore, our scheme can effectively motivate users to provide high-quality sensing data.Figure 8
The reward evaluation of users.


## 8. Related Work

Truth discovery is an effective technology that can calculate the ground truth and users’ data quality from conflicting sensing data. Li et al. [32] proposed a general truth discovery scheme, but privacy protection is not in their work scope. To protect users’ privacy data, Miao et al. [41] proposed the first privacy-preserving truth discovery scheme using the Paillier cryptosystem, but the computational and communication costs are huge. Zheng et al. [43] designed a privacy-aware truth discovery, which greatly reduced the computational and communication overhead through a secure sum protocol. Zhang et al. [44] designed a truth discovery scheme using a one-way hash chain to ensure privacy security, and all truth discovery operations are completed by fog and cloud platforms. Tang et al. [45] used two servers to complete the calculation process of truth discovery, which can effectively protect users’ sensing data privacy. However, these works do not take into account the failure of the MCS system caused by users’ exit. Bonawitz et al. [39] proposed a double-masking scheme for secure data aggregation, and this scheme allows users to exit. After that, Xu et al. [15] designed a privacy-preserving truth discovery scheme based on the double-masking scheme. However, these truth discovery schemes do not incorporate incentive mechanisms. If malicious users constantly input erroneous data, it will affect the reliability of the results in the MCS system.Another previous work [42, 46] related to this paper is the incentive mechanism in the MCS system. Zhang et al. [47] presented a reverse auction model which can motivate online users to participate in sensing tasks. Jin et al. [16] designed an incentive mechanism model based on reverse combinatorial auctions, which can maximize social welfare and effectively motivate users. Yang et al. [42] introduced a quality-aware incentive mechanism, which can distribute rewards to users after calculating the data quality. However, these works do not consider the privacy of users. In [27], the authors designed a privacy-preserving incentive mechanism model. Nevertheless, these solutions can not eliminate users who provide error data. Zhao et al. [20] presented an incentive mechanism model to evaluate the reliability of users’ data while protecting data privacy. Still, the user’s sensing data need to be submitted to the task publisher, so the privacy protection of sensing data is still insufficient. Later, Zhao et al. [48] proposed a privacy-preserving incentive mechanism based on truth discovery. This model uses two servers to achieve real-time reward distribution while protecting users’ privacy. However, most existing works do not take users’ exit into account.


## 9. Conclusion

In this paper, we propose a privacy-preserving incentive mechanism based on truth discovery in the MCS system. Specifically, we introduce an eligibility assessment scheme to estimate whether the data submitted by users are qualified. Next, the truth discovery scheme calculates the ground truth and the weight of each user. Then, we quantify the data quality of users by the weight and distribute the rewards. Besides, we also demonstrate that PAID meets eligibility, zero knowledge, payment rationality, and budget rationality. And the analysis shows that our PAID can resist the denial of payment attack, inference attack, data pollution attack, and Sybil attack. Finally, experiments illustrate that PAID is effective, efficient, and robust to dropped users. In future work, we will design an incentive mechanism model for the application of multidimensional sensing data collection.



---

*Source: 4804758-2021-08-15.xml*