# pMATE: A Privacy-Preserving Map Retrieval Task Assignment Scheme in Spatial Crowdsourcing

Authors: Peicong He; Yang Xin; Zhengwen Li; Yixian Yang
Journal: Security and Communication Networks
 (2023)

---

## Abstract

Spatial crowdsourcing (SC) task assignment is to find the optimal worker for the task from abundant alternative workers based on the information of the task and workers, such as location, time, and ability. This information will undoubtedly reveal the privacy of both the task and workers. The disclosure of private information is a crucial issue constraining the development of SC. To this end, various privacy-preserving task assignments have been proposed to protect privacy by obfuscating or encrypting information. Fuzzy processing will limit matching accuracy, while encrypted information will increase the time cost of data computation. Therefore, this paper proposes a privacy-preserving map retrieval task assignment scheme (pMATE), which can divide the map and accurately retrieve the optimal workers according to this division. In pMATE, relevant information about tasks and workers is encrypted, and neighboring workers are searched based on the task presence partition. The task location can also be hidden in that partition. Partitioned retrieval reduces the amount of encrypted data needed to be matched. Furthermore, to reduce the problem of multiple communications during encrypted data comparison, we propose the Find MinNumber (FMN) algorithm, which can determine the optimal worker or top-k optimal workers need only two communications. Experimental evaluations of real-world data show that pMATE is efficient and accurate.


---

## Body

## 1. Introduction

With the increasingly powerful functions of intelligent mobile terminals as well as the convenience and high speed of network access, spatial crowdsourcing (SC) [1, 2] as a new business cooperation model, becomes more and more popular and is widely used in urban services and data collection [3–5], such as Uber, Didi, OpenStreetMap, etc. There are three characteristics in SC tasks, respectively, the location, the required capabilities, and the deadline. In other words, SC tasks are based on a specific space scope. They need to be completed within a specified time, for example, picking up passengers from Xizhimen subway station at 3 pm on September 5 and taking them to Tiananmen Square, or taking a picture of Tiananmen Square at sunset on September 6 and recording the sunset time. The total revenue of Meituan takeaway and Didi was 96.3 billion yuan and 173.8 billion yuan, respectively, in the Chinese market in 2021. The vast market and broad application prospects have turned SC into a research hotspot.As depicted in Figure1, there are three components in SC, task requesters (TRs), task workers (TWs), and spatial crowdsourcing server (SC-server). TRs are the initiators of SC tasks, searching for a suitable worker or workers to help her/him accomplish the task. TWs are SC task completers looking for a competent task to complete to earn a paycheck. TRs and TWs are SC-server users, an online service platform for matching TRs and TWs with some rules. The typical task assignment strategies are considered ability, distance, and time. That is, whether the ability to complete the task is available, whether it can be completed within the specified time, and the worker’s distance from the task point. Therefore, TRs and TWs must upload their information to the SC-server to accomplish the matches. Although the uploaded pieces of information make task assignments more accessible and accurate, it also increases the risk of leakage of user privacy information because more users' relevant information is uploaded.Figure 1
Tasks assignment model in SC.Unfortunately, in the SC model, there is no wholly trusted party among the three parties. As shown in Figure1, adversaries can disguise themselves as TRs or TWs to participate in SC tasks, listen to service requests sent by TRs or TWs to the SC-server or even hack the SC-server to obtain task requests from TRs and TWs. Adversaries may infer the users’ physical state, living habits, and religion based on the information uploaded by users [6]. For example, Alice accepts the task of delivering medicine to Bob. People who know this information can know that Bob is in poor health and can even infer what disease Alice has according to the medicine. If the address is a residential area and the delivery time is after hours, the address is likely Alice’s residence. It follows that disclosing such task information would pose a potential threat to users.However, data privacy and security are becoming more and more vital in calculating user data [7]. Users would be less likely to participate in SC out of fear of the risk of their privacy being exposed. The loss of users is highly detrimental to SC development, and meager user participation will make assigning SC tasks challenging. Therefore, many privacy-preserving task assignment schemes have been proposed to ensure that task information is not available to anyone other than the TR and TW of that task. They can be broadly classified into two categories based on the protection mechanism. One is to fuzz the information, while the other is to encrypt the information.Blurring processes protect user privacy by constructing a cloak zone where users cannot be precisely distinguished. This indistinguishability leads to finding only TWs without determining whether they are optimal. The distance traveled is the primary condition for determining the optimal TW, that is, the distance from the TW to the task location, provided that the TW can complete the task. TWs are more likely to choose a less distant job than the jobs they can do. In this way, they have a low cost of arriving at the location and can complete more tasks and earn more money. On the other hand, for TRs, the closer TW may arrive at the destination faster. Their wait times are short, so they have a better service experience. In contrast to the fuzzing process, methods of encryption protection can achieve exact matching. However, unfortunately, encryption protection methodsare quite time-consuming due to the need to perform calculations and comparisons of encrypted data.Hence, we would like to construct a privacy-preserving scheme that combines the advantages of fuzzy processing and cryptographic protection. It can protect the privacy of TRs and TWs and assign tasks accurately and efficiently at the same time. Dividing the map and performing encrypted task matching based on the division is a promising solution. However, a task assignment strategy for encrypted information partition retrieval needs to address the following challenges.Challenge 1: How to achieve matching without knowing the specific information of TRs and TWs. It is easy to match TRs with TWs without privacy protection simply by comparing and filtering their information to select TWs who meet the conditions. As mentioned above, information about TRs and TW needs to be processed to protect their privacy. Matching these ambiguous or encrypted messages is the first difficulty that needs to be solved.Challenge 2: How to determine the search area without knowing the exact location of TRs and TWs. In order to reduce the number of encrypted samples to be compared, a subregion search is undoubtedly a better approach. However, two issues need to be addressed to accomplish this. The first one is to determine that the optimal TW exists in the retrieval region if the TWs exist in the retrieval region. The second one is how to expand the retrieval region if no TW satisfies the conditions in the retrieval region. After encrypting the user’s location, information is no longer a visible difference. It is challenging to classify a group of undifferentiated data. Proposing a partitioned retrieval method that can be feasible is another difficulty that needs to be solved.Challenge 3: How to determine the optimal TW among the TWs who satisfy the conditions. The key to this issue is that no additional information is leaked during the determination process. The optimal TW typically is the one that is the closest to the task location and satisfies the task conditions. Identifying the closest TW to the task location is easy without protecting privacy. However, achieving this in the context of privacy protection is not easy. Because to protect users’ privacy, their location information needs to be processed. It is challenging to calculate and compare the distance of the processed locations and not disclose the information in the process.To address the above challenges, we propose a privacy-preserving map retrieval task assignment scheme that can divide the map and accurately retrieve the optimal TWs according to this division, called pMATE. In pMATE, we divide the map with Voronoi and encrypt the task information of TRs and TWs with the Paillier cryptosystem. Our method reduces the candidate TWs’ number to be compared by retrieving from the partition where the task is located. The proposed FindR and Get TWs algorithms can solve the problem that no suitable TWs are available in the search zone, and the search range needs to be expanded. The comparison of encrypted data is achieved using the homomorphic nature of Paillier. Furthermore, we propose the FMN algorithm to find the optimal TW or TWs from candidates.The contributions of this paper are concluded as follows.(1)
We propose a privacy-preserving map retrieval task assignment solution approach that combines fuzzy processing with cryptographic retrieval. The specific location of the user is hidden in the partition. The encrypted search in the partition guarantees exact matches and reduces the number of samples to be compared.(2)
pMATE supports dynamic partition search. The proposed algorithms FindR and Get TWs can dynamically expand the search range according to the number of suitable TWs in the partition and ensure that the optimal TWs are in the search area.(3)
Our method can pick out the optimal TW or top-k TWs from the candidates that require only two communications with Find MinNumber (FMN) and Find Equal (FE) algorithms. In pMATE, we perturb the difference of encrypted distance and pass it to TR. The optimal TW is found with the help of TR and without compromising privacy.The rest of this paper is organized as follows. We introduce the related work and preliminaries in Sections2 and 3. Section 4 describes the system model, threat model, design goals, and problem formulation. Then, we introduce pMATE’s preparation stage, the task request stage, the task assignment stage, and the algorithm involved in these stages in Section 5. We analyze the security of pMATE in Section 6. Section 7 reports and evaluates the experimental results. Finally, we conclude Section 8.


## 2. Related Work

### 2.1. The Privacy-Preserving Task Assignment with Fuzzification Techniques

The primary purpose of this protection method is to construct an indistinguishable region by processing the data. Data belonging to an indistinguishable partition has a standard attribute class but cannot differentiate between them. Anonymous technology is a typical representative of this. It is like seeing a group of people but cannot distinguish between them. Well-known anonymous technologies includek-anonymity [8] and l-diversity [9]. With these techniques, many task assignments have been proposed [10–13]. In [10], Kazemi and Shahabi proposed a PiRi framework to construct a cloaking region before connecting the SC-server. In this mode, instead of each participant raising a separate query, only a representative group of participants raises queries to the SC-server and shares their results with those who did not. Vu et al. [11] partition user location into groups by locality-sensitive hashing (LSH). They assume that users are all credible and hide the user’s location information by establishing the group-satisfied k-anonymity. Pournajaf et al. [12] expanded the TWs’ specific location into a cloaked area and set a limited travel distance. SC-server match TRs and TWs according to them. However, it can only protect the TWs’ location and cannot find the nearest one. Hu et al. [13] extended Pournajaf’s work. They extended the travel budget constraint in [12] to an area of space denoted by a rectangle R that employees are willing to travel. The anonymous techniques aim to protect user privacy by expanding the location range or integrating multiple user locations. These typically only protect one of TW and TR’s private information and do not complete an exact match. Like the anonymous technique, perturbation techniques can protect users’ privacy by differential privacy or perturbation of geographical position [14–17]. All of them use geocasting [18] for search workers. To et al. [14] use differential privacy protection and custom privacy budgets to protect worker location privacy. They need a trusted third party to preprocess the data. Then to expand their research [17], they address the moving TWs challenge by investigating continuously released privacy budget allocation techniques and using a Kalman filter-based post-processing technique to reduce inaccuracies from noise addition. Gong et al. [15] introduced reputation information for quality control based on [14]. Zhang et al. [16] use a similar framework. Instead of [14] using an adaptive grid to publish a cleaned location view to SC-server, they constructed a contour plot to represent the spatial distribution of TWs to introduce less noise than previous techniques. Both the anonymization technique and perturbation technique need to obfuscate the source data. This way protects users’ privacy within that range but makes the accurate matching of task challenging. Compared with the existing solutions, our proposed pMATE protects both TR and TW’s privacy and performs precise task matching.


### 2.2. The Privacy-Preserving Task Assignment with Encryption Techniques

Another way to protect user privacy is to use cryptography to encrypt data. This approach has a stronger theoretical basis for security, but efficiency is its disadvantage. Although Shu et al. [19] achieve bidirectional privacy-preserving task assignment through proxy re-encryption, their proposed solution requires additional servers such as proxy servers or fog nodes. They proposed another scheme [20] called pMatch, a proxy-free task matching via Shamir secret sharing. It can implement a privacy-preserving task distribution scheme without a proxy server. Wang et al. [6] proposed the PWSM to assign tasks by minimizing the travel distance. It only protects the TWs’ privacy by obfuscating information about them. In [21], Ni et al. utilize a random matrix and the grid-encoded location to protect both TRs and TWs. Liu et al. [22] combine the Paillier cryptosystem with Yao’s garbled circuits to find the nearest TWs and use Geohash to find the approximate nearest workers. But it can only perform fuzzy search due to its partitioning mechanism. Zhao et al. [23] propose the iTAM scheme that uses the Paillier cryptosystem to protect the privacy of both TRs and TWs and the corresponding matching protocol. However, it is inefficient because it needs to retrieve all ciphertext information. These solutions either do not match precisely or are less efficient. Therefore, we propose a privacy-preserving map retrieval task assignment scheme (pMATE), which can divide the map and accurately retrieve the optimal workers according to this division. In pMATE, we use the Paillier cryptosystem to match encrypted information exactly and reduce the number of comparisons by the Voronoi diagram.


## 2.1. The Privacy-Preserving Task Assignment with Fuzzification Techniques

The primary purpose of this protection method is to construct an indistinguishable region by processing the data. Data belonging to an indistinguishable partition has a standard attribute class but cannot differentiate between them. Anonymous technology is a typical representative of this. It is like seeing a group of people but cannot distinguish between them. Well-known anonymous technologies includek-anonymity [8] and l-diversity [9]. With these techniques, many task assignments have been proposed [10–13]. In [10], Kazemi and Shahabi proposed a PiRi framework to construct a cloaking region before connecting the SC-server. In this mode, instead of each participant raising a separate query, only a representative group of participants raises queries to the SC-server and shares their results with those who did not. Vu et al. [11] partition user location into groups by locality-sensitive hashing (LSH). They assume that users are all credible and hide the user’s location information by establishing the group-satisfied k-anonymity. Pournajaf et al. [12] expanded the TWs’ specific location into a cloaked area and set a limited travel distance. SC-server match TRs and TWs according to them. However, it can only protect the TWs’ location and cannot find the nearest one. Hu et al. [13] extended Pournajaf’s work. They extended the travel budget constraint in [12] to an area of space denoted by a rectangle R that employees are willing to travel. The anonymous techniques aim to protect user privacy by expanding the location range or integrating multiple user locations. These typically only protect one of TW and TR’s private information and do not complete an exact match. Like the anonymous technique, perturbation techniques can protect users’ privacy by differential privacy or perturbation of geographical position [14–17]. All of them use geocasting [18] for search workers. To et al. [14] use differential privacy protection and custom privacy budgets to protect worker location privacy. They need a trusted third party to preprocess the data. Then to expand their research [17], they address the moving TWs challenge by investigating continuously released privacy budget allocation techniques and using a Kalman filter-based post-processing technique to reduce inaccuracies from noise addition. Gong et al. [15] introduced reputation information for quality control based on [14]. Zhang et al. [16] use a similar framework. Instead of [14] using an adaptive grid to publish a cleaned location view to SC-server, they constructed a contour plot to represent the spatial distribution of TWs to introduce less noise than previous techniques. Both the anonymization technique and perturbation technique need to obfuscate the source data. This way protects users’ privacy within that range but makes the accurate matching of task challenging. Compared with the existing solutions, our proposed pMATE protects both TR and TW’s privacy and performs precise task matching.


## 2.2. The Privacy-Preserving Task Assignment with Encryption Techniques

Another way to protect user privacy is to use cryptography to encrypt data. This approach has a stronger theoretical basis for security, but efficiency is its disadvantage. Although Shu et al. [19] achieve bidirectional privacy-preserving task assignment through proxy re-encryption, their proposed solution requires additional servers such as proxy servers or fog nodes. They proposed another scheme [20] called pMatch, a proxy-free task matching via Shamir secret sharing. It can implement a privacy-preserving task distribution scheme without a proxy server. Wang et al. [6] proposed the PWSM to assign tasks by minimizing the travel distance. It only protects the TWs’ privacy by obfuscating information about them. In [21], Ni et al. utilize a random matrix and the grid-encoded location to protect both TRs and TWs. Liu et al. [22] combine the Paillier cryptosystem with Yao’s garbled circuits to find the nearest TWs and use Geohash to find the approximate nearest workers. But it can only perform fuzzy search due to its partitioning mechanism. Zhao et al. [23] propose the iTAM scheme that uses the Paillier cryptosystem to protect the privacy of both TRs and TWs and the corresponding matching protocol. However, it is inefficient because it needs to retrieve all ciphertext information. These solutions either do not match precisely or are less efficient. Therefore, we propose a privacy-preserving map retrieval task assignment scheme (pMATE), which can divide the map and accurately retrieve the optimal workers according to this division. In pMATE, we use the Paillier cryptosystem to match encrypted information exactly and reduce the number of comparisons by the Voronoi diagram.


## 3. Preliminaries

This section introduces essential concepts for clearly elaborating our model and methods. In our framework, we adopt the Voronoi diagram and Paillier cryptosystem to ensure the efficient and accurate matching of TWs and tasks while protecting their privacy.


### 3.1. Voronoi Diagram

Voronoi diagram (VD) [24, 25] is a way of partitioning a plane into Voronoi cells by electing particular points in this plane. Let VD be the function of the partitioning plane. These elected points are known as generator points denoted by the set G, G=g1,g2,…,gn, and the plane can be viewed as a set U, U=R2. The result of this partition is that all points in its cell have the shortest Euclidean distance from the cell’s generator point than others. We adopt dv,g as the Euclidean distance between v and g. The v and g are the points in the plane. With the G, we can obtain a partition of U denoted as follow.(1)VDU=U1,U2,...,Un,Ui=v|dv,gi≤dv,gothers.


### 3.2. Paillier Cryptosystem

Paillier cryptosystem [26] is a homomorphic public key encryption scheme. Its properties can be used in ciphertext calculations to preserve users’ privacy.Key Generation: We setN=pq where p and q are independent large prime numbers, and they are selected randomly such that gcdN,p−1q−1=1. Let λ=lcmp−1,q−1, and select random integer g where g∈ZN2∗, and then compute μ=LgλmodN2−1modN, where the function L is defined as Lx=x−1/N. The public key and private key are pk=g,N and sk=λ,μ.Encryption: Given a messagem∈ZN to be encrypted, it is encrypted by the public key pk to C=mpk=gm⋅rNmodN2, where r is a selected random integer r∈ZN∗.Decryption: Given a ciphertextC to be decrypted, it is decrypted by the private key sk to m=DskC=LCλmodN2⋅μmodN.Its properties are listed as follows wherex,y∈ZN.(1)
Additive homomorphism:(2)Dskx⋅y=Dskx+y.(2)
Scalar-multiplicative homomorphism:(3)Dskxy=Dskx⋅y.


## 3.1. Voronoi Diagram

Voronoi diagram (VD) [24, 25] is a way of partitioning a plane into Voronoi cells by electing particular points in this plane. Let VD be the function of the partitioning plane. These elected points are known as generator points denoted by the set G, G=g1,g2,…,gn, and the plane can be viewed as a set U, U=R2. The result of this partition is that all points in its cell have the shortest Euclidean distance from the cell’s generator point than others. We adopt dv,g as the Euclidean distance between v and g. The v and g are the points in the plane. With the G, we can obtain a partition of U denoted as follow.(1)VDU=U1,U2,...,Un,Ui=v|dv,gi≤dv,gothers.


## 3.2. Paillier Cryptosystem

Paillier cryptosystem [26] is a homomorphic public key encryption scheme. Its properties can be used in ciphertext calculations to preserve users’ privacy.Key Generation: We setN=pq where p and q are independent large prime numbers, and they are selected randomly such that gcdN,p−1q−1=1. Let λ=lcmp−1,q−1, and select random integer g where g∈ZN2∗, and then compute μ=LgλmodN2−1modN, where the function L is defined as Lx=x−1/N. The public key and private key are pk=g,N and sk=λ,μ.Encryption: Given a messagem∈ZN to be encrypted, it is encrypted by the public key pk to C=mpk=gm⋅rNmodN2, where r is a selected random integer r∈ZN∗.Decryption: Given a ciphertextC to be decrypted, it is decrypted by the private key sk to m=DskC=LCλmodN2⋅μmodN.Its properties are listed as follows wherex,y∈ZN.(1)
Additive homomorphism:(2)Dskx⋅y=Dskx+y.(2)
Scalar-multiplicative homomorphism:(3)Dskxy=Dskx⋅y.


## 4. System Overview and Problem Statement

In this section, we illustrate the system model, threat model, and design goals of pMATE. Then we introduce the problem formulation in SC task allocation.


### 4.1. System Model

As shown in Figure2, our system mainly consists of SC-server, TWs, and TRs. We consider privacy-preserving task assignments in SC, and the main focus is on detecting the closest TWs while satisfying the task capability and time constraints.Figure 2
System model of pMATE.The complete task assignment process has four steps, which are described below.Step 1: Task requirement. TRs submit their task requests to the SC-server. The requested information includes the TR’s task description without private information, encrypted task information, and public key.Step 2: Search for candidate TWs. SC-server broadcasts the task description, encrypted task information, and public key to search for interested TWs based on the partition where the task is located. Interested TWs send task requests encrypted by the public key to SC-server. If SC-server does not receive enough task requests, it will expand the broadcast range and continue searching for alternative TWs until it finds a sufficient number of TWs.Step 3: Encrypted information calculation. SC-server calculates the encrypted information uploaded by TWs and TRs according to the task assignment constraints.Step 4: Search for optimal TW. SC-server disrupts the calculation results and collaborates with the TR, who issued the task to find the optimal TW without compromising privacy.


### 4.2. Threat Model

As mentioned above, the potential threat to the system model comes from three sources: TRs, TWs, and SC-server. We assume SC-server is honest-but-curious, which follows the protocols but wants to pry into users’ private information, and most of TRs and TWs ask for help in the platform. This assumption is reasonable because SC-server needs to be approved and registered before it goes online. It can ensure the trust of SC-Server to a certain extent. Then we assume a strong adversaryα in our model with the following capabilities. The goal of α is to obtain the privacy information of TRs or TWs.(1)
α can eavesdrop on all communication channels to obtain the encrypted message.(2)
α can disguise a TR to issue task request to SC-server and obtain the information returned from SC-server.(3)
α can disguise a TW to compete for a task and obtain the information about the task.(4)
α can compromise SC-server to obtain exchange messages among TRs, TWs, and SC-server.Note thatα is restricted from compromising both the TRs and SC-server simultaneously.Remark 1.
In our framework, ifα compromise both SC-server and TRs simultaneously, it could get the TWs’ location information. However, if α compromise both SC-server and TWs at the same time, it could only get the range of TR’s location information who submits task request. Because only the TR has the private key, only he/she can decrypt the location information. Although location will not be exposed in this situation, there will be a certain amount of information leakage. Furthermore, it is a general assumption that there is no CS/TR or CS/TW collusion attack among the three.


### 4.3. Design Goals

Given these three potential threats, we want to design a scheme that can protect users’ task information from leakage for both TRs and TWs until the task assignment is done.Privacy. In the process of an SC task, for TRs, its task information should be confidential in the task application process. Both SC-server and TWs cannot get the plaintext of task information. Every TR should encrypt his/her task information before sending a task request to SC-server. For TWs, they need to encrypt their task information too. In addition, their ciphertext of location information cannot be obtained by TR, who issues the task. Because TR has the private key, he/she can decrypt the ciphertext.Calculability. The SC-server should have ciphertext computing capability since the task information it receives is encrypted.Efficiency. Comparing and calculating encrypted data is time-consuming. In SC, there is a large number of such operations, and it increases with the number of users. Computational efficiency is an issue to consider. So we devised a method to reduce this time consumption and improve efficiency.


### 4.4. Problem Formulation

To transform the real problem into a mathematical problem, we formulate this problem as follows.Definition 1.
(Task). LetT=T1,T2,...,Tn be a task collection, and each task is represented as Ti=id,lat,lng,tR,capR. id is the task number, lat,lng is the latitude and longitude of the task’s location, tR is the latest start time of the task, capR is the capability required by the task. It indicates the task type or required sensors, such as transportation, photo-taking, temperature acquisition, etc.Definition 2.
(TW). LetWi=W1,W2,…,Wn be a TW collection for Ti, and each TW is represented as Wi=id,lat,lng,tW,capW. id is the TW’s number, lat,lng is the latitude and longitude of TW’s location, tW is the arrival time of the TW, capW is the capability of the TW, like capR.Definition 3.
(Travel Distance). Travel Distance (TD) is the Euclidean distance from the location of a TW to the task position. It can be calculated according to the latitude and longitude of the TR and TW, the TR’s location islatR,lngR, and the TW’s location is latW,lngW. The location information is preprocessed into integers to satisfy the Paillier cryptosystem. Let D=d1,d2,…,dn be a collection of TW’s TD who want to get this task. di is the No. i TW’s TD. The TD’s formula is as follows.(4)dW=latR−latW2+lngR−lngW2.Definition 4.
(Task Assignment). In the SC, it is the fundamental purpose to match TWs for specific tasks. In this paper, we use equation (5) as the matching rule. Supposing a TR and TW are denoted by Ti=i,latR,lngR,tR,capR and Wj=j,latW,lngW,tW,capW. If the following constraints are met(5a)tW≤tR,(5b)dW=minD,(5c)capR=capW.
The TW is considered to be the best match for this task. (5a) means that the TW can arrive at the task location on time. In (5a), tW=tW′+Δt. tW′ is the earliest departure time for TW to go to the destination, and Δt is the estimated time spent on the journey. Due to the unclear destinations, we set Δt as twice the time TW goes to the generator point of the task in the cell. (5b) means that the TW’s TD is minimum. (5c) means that the TW is adequately capable of this task.


## 4.1. System Model

As shown in Figure2, our system mainly consists of SC-server, TWs, and TRs. We consider privacy-preserving task assignments in SC, and the main focus is on detecting the closest TWs while satisfying the task capability and time constraints.Figure 2
System model of pMATE.The complete task assignment process has four steps, which are described below.Step 1: Task requirement. TRs submit their task requests to the SC-server. The requested information includes the TR’s task description without private information, encrypted task information, and public key.Step 2: Search for candidate TWs. SC-server broadcasts the task description, encrypted task information, and public key to search for interested TWs based on the partition where the task is located. Interested TWs send task requests encrypted by the public key to SC-server. If SC-server does not receive enough task requests, it will expand the broadcast range and continue searching for alternative TWs until it finds a sufficient number of TWs.Step 3: Encrypted information calculation. SC-server calculates the encrypted information uploaded by TWs and TRs according to the task assignment constraints.Step 4: Search for optimal TW. SC-server disrupts the calculation results and collaborates with the TR, who issued the task to find the optimal TW without compromising privacy.


## 4.2. Threat Model

As mentioned above, the potential threat to the system model comes from three sources: TRs, TWs, and SC-server. We assume SC-server is honest-but-curious, which follows the protocols but wants to pry into users’ private information, and most of TRs and TWs ask for help in the platform. This assumption is reasonable because SC-server needs to be approved and registered before it goes online. It can ensure the trust of SC-Server to a certain extent. Then we assume a strong adversaryα in our model with the following capabilities. The goal of α is to obtain the privacy information of TRs or TWs.(1)
α can eavesdrop on all communication channels to obtain the encrypted message.(2)
α can disguise a TR to issue task request to SC-server and obtain the information returned from SC-server.(3)
α can disguise a TW to compete for a task and obtain the information about the task.(4)
α can compromise SC-server to obtain exchange messages among TRs, TWs, and SC-server.Note thatα is restricted from compromising both the TRs and SC-server simultaneously.Remark 1.
In our framework, ifα compromise both SC-server and TRs simultaneously, it could get the TWs’ location information. However, if α compromise both SC-server and TWs at the same time, it could only get the range of TR’s location information who submits task request. Because only the TR has the private key, only he/she can decrypt the location information. Although location will not be exposed in this situation, there will be a certain amount of information leakage. Furthermore, it is a general assumption that there is no CS/TR or CS/TW collusion attack among the three.


## 4.3. Design Goals

Given these three potential threats, we want to design a scheme that can protect users’ task information from leakage for both TRs and TWs until the task assignment is done.Privacy. In the process of an SC task, for TRs, its task information should be confidential in the task application process. Both SC-server and TWs cannot get the plaintext of task information. Every TR should encrypt his/her task information before sending a task request to SC-server. For TWs, they need to encrypt their task information too. In addition, their ciphertext of location information cannot be obtained by TR, who issues the task. Because TR has the private key, he/she can decrypt the ciphertext.Calculability. The SC-server should have ciphertext computing capability since the task information it receives is encrypted.Efficiency. Comparing and calculating encrypted data is time-consuming. In SC, there is a large number of such operations, and it increases with the number of users. Computational efficiency is an issue to consider. So we devised a method to reduce this time consumption and improve efficiency.


## 4.4. Problem Formulation

To transform the real problem into a mathematical problem, we formulate this problem as follows.Definition 1.
(Task). LetT=T1,T2,...,Tn be a task collection, and each task is represented as Ti=id,lat,lng,tR,capR. id is the task number, lat,lng is the latitude and longitude of the task’s location, tR is the latest start time of the task, capR is the capability required by the task. It indicates the task type or required sensors, such as transportation, photo-taking, temperature acquisition, etc.Definition 2.
(TW). LetWi=W1,W2,…,Wn be a TW collection for Ti, and each TW is represented as Wi=id,lat,lng,tW,capW. id is the TW’s number, lat,lng is the latitude and longitude of TW’s location, tW is the arrival time of the TW, capW is the capability of the TW, like capR.Definition 3.
(Travel Distance). Travel Distance (TD) is the Euclidean distance from the location of a TW to the task position. It can be calculated according to the latitude and longitude of the TR and TW, the TR’s location islatR,lngR, and the TW’s location is latW,lngW. The location information is preprocessed into integers to satisfy the Paillier cryptosystem. Let D=d1,d2,…,dn be a collection of TW’s TD who want to get this task. di is the No. i TW’s TD. The TD’s formula is as follows.(4)dW=latR−latW2+lngR−lngW2.Definition 4.
(Task Assignment). In the SC, it is the fundamental purpose to match TWs for specific tasks. In this paper, we use equation (5) as the matching rule. Supposing a TR and TW are denoted by Ti=i,latR,lngR,tR,capR and Wj=j,latW,lngW,tW,capW. If the following constraints are met(5a)tW≤tR,(5b)dW=minD,(5c)capR=capW.
The TW is considered to be the best match for this task. (5a) means that the TW can arrive at the task location on time. In (5a), tW=tW′+Δt. tW′ is the earliest departure time for TW to go to the destination, and Δt is the estimated time spent on the journey. Due to the unclear destinations, we set Δt as twice the time TW goes to the generator point of the task in the cell. (5b) means that the TW’s TD is minimum. (5c) means that the TW is adequately capable of this task.


## 5. Design of pMATE

### 5.1. Framework Workflow

We present the workflow of pMATE. The whole workflow is divided into three stages: the preparation stage, the task request stage, and the task assignment stage.Specifically, as a request task example shown in Figure3, there are seven steps in the workflow without the preparation stage.In ①, a TR sends its encrypted location information, the capability required to complete the task, the cell number obtained during the preparation stage, the public key, and the latest start time of the task to SC-server to initiate a task request. The SC-server numbers the task request and puts it intoT.In ②, the SC-server selects a task request fromT according to the recent start time and broadcasts it to TWs using the Find R and Get TWs algorithm based on the cell number received.In ③, TWs who want to get the task and meet the time and ability constraints reply to a message to SC-server based on the information they received. SC-server catches the response by the TWs Respond function, numbers these TWs, and puts their information intoWi. The i is the task number.In ④, SC-server determines whether the number in the setWi meets the requirements. If it does not, SC-server will expand R and repeat ②.After the number of TWs meets the requirements, SC-server selects the TWs in Wi and calculates the encrypted distance between them and the task point respectively, calculates the difference of ciphertext distance, and forms the difference into a sequence.In ⑤, the SC-server processes and disarranges the sequence and sends it to the TR.In ⑥, the TR decrypts the sequence and returns the relationship of size to SC-server.In ⑦, SC-server finds the nearest TW or TWs based on the relationship and associates the TR with TW or TWs.Figure 3
Workflow of pMATE.


### 5.2. Preparation Stage

In the previous part, we introduced the workflow of pMATE. Before that, there is a preparation stage in which we partition the map with VD. Ciphertext calculation and comparison are time-consuming, especially when many ciphertext calculations and comparisons are required. Because the data is encrypted, the value cannot be confirmed. All ciphertext value differences need to be calculated and compared each time. Moreover, these calculations are very time-consuming. Therefore, we plan to divide the map into regions to reduce the number of comparison samples and the time cost and improve efficiency. SC-server can locate an approximate range and expand its search until it matches the suitable TW or TWs when a TR submits a task request based on her/his partition number. Since the map information is publicly available in advance, it is easy to identify the authenticity.Compared with many other partition methods, the VD algorithm can guarantee a unique result and the shortest distance from the point in the cell to the generator point. With that, we can ensure the uniqueness of the partition and that the points in the cell have the same properties when we choose the intersections as the generator points of VD. For a cell, each point in it is the shortest distance to this intersection which belongs to the traffic road network. This division of the map according to road conditions is more realistic.VD as a fundamental structure has been researched and applied in many fields. In our work, to facilitate the Get TWs algorithm, some information about VD needs to be stored. The left part of Figure4 shows an example of the VD partition, and the right part presents its storage structure. Specifically, C1 is the cell number, V1 is its generator point, and p1,p2,p3,p4,p5 is the set of its vertexes. The Cell Number list records each cell. Each cell links a logic space that contains its generator called Generator Point, the set of its vertexes called Vertex, and the set of neighbor cells’ numbers called Adjacency. Since the map information can be obtained in advance, these calculations can also be completed before the task request stage, so the waiting time for the request will not increase. This stage is called the preparation stage.Figure 4
Voronoi diagram and voronoi diagram storage structure.


### 5.3. Task Request Stage

① to ③ in the workflow is the task request stage. In this stage, a TR submits a task request to SC-server. Then SC-server looks for TWs who want to get the task by the following algorithms. When a user wants to enjoy the services of the SC-server, she has to register with SC-Server and get VD information for the preparation phase. In other words, she needs to know her location’s cell number. When submitting a task request to SC-server, she needs to query her cell number according to the VD information obtained during registration. Furthermore, the map’s information is public, so she can quickly determine its reliability by comparing it with VD.In our framework, Euclidean distance is the key to matching tasks. Expanding equation (4), we can get the following:(6)dRW=latR−latW2+lngR−lngW2=latR2+latW2−2latR⋅latW+lngR2+lngW2−2lngR⋅lngW,dRW2=latR2+latW2−2latR⋅latW+lngR2+lngW2−2lngR⋅lngW.With the properties of Paillier, we can get the following:(7)dRW2=latR2⋅latW2⋅2latR−latW⋅lngR2⋅lngW2⋅2lngR−lngW.Due to thedRW≥0, dRW1≥dRW2⇔dRW12≥dRW22. So, we have to compare dRW2.In this stage, for the TR who wants to submit the task to SC-server, she needs to upload her cell number, the latest start timetR, and latR2, 2latR, lngR2, 2lngR to SC-server. SC-server broadcasts the task description, the task time, cell number, public key, and encrypted location information by the Geo-Broadcast [19] function to find TWs who want to get this job. Due to the cells of VD being irregular convex quadrilateral, it is difficult to determine the broadcast radius. As shown in Figure 4, the R1 is the broadcast radius we want to find for C1 in the first round. R1 is chosen as the broadcast radius to avoid the situation where the nearest TW is in the adjacent cell of C1 and is missed. We can see that the algorithm for finding TWs is divided into two parts. Part of it is to determine the broadcast radius based on the search area and broadcast to find TWs. Another part is expanding the search area when no TWs are found. So, we propose the Find R algorithm to find the suitable broadcast radius for the Get TWs algorithm. Find R’s initialization is finished as part of the Get TWs algorithm.Assuming a TR submits a task request, she uploads her cell number to SC-server, and SC-server can get her cell generator point, cell vertexes, and adjacency cell number according to the information obtained during the preparation stage. Let the cell generator point be the central point calledv, ℂ be the set of hunting cells, ℕ be the vertex sets of ℂ, L be the vertex sets of adjacency cells of ℂ, K be the set of the farthest possible point. K is the subtraction of L and ℕ, K = L–ℕ. In the Algorithm 1, C1.Vertex ∩C2.Vertex ∩⋯∩Cn.Vertex represents all vertexes of the search area. Calculate the distance between all points in K and v. The maximum value is the search radius, R. With R, we can get the Get TWs algorithm described as follows. It is a circular algorithm that collects TWs who want to get task number i into Wi. For simplicity, we adopt W instead of Wi.Algorithm 1: Find R.
Input: the set of hunting cells ℂ, central point v.Output:RL ← C1.Vertex ∩C2.Vertex ∩⋯∩Cn. Vertex; //ℂ = {C1, C2, …, Cn}K ← L–ℕ; //initialization in Get TWs algorithmR ← maxdv,Ki; //i = 1 to n;ℕ ← K;ReturnR;In Algorithm2, we need to initialize those sets: W, L, ℕ, K, ℂnow, ℂbefore, ℂcache. Those sets’ initial values are null. When we run Algorithm 1, we can get the broadcast radius according to the search area. We need to update the search area to get TWs. The TWs who want to get this task need to calculate how long it takes to get from their position to the generator of the task in the cell, and they can get the estimated arrival time tW, and upload tW, latW2, 2latR−latW, lngW2, 2lngR−lngW to SC-server for task matching. The Worker Respond function is a listener that puts received replies into the W. In Algorithm 2, t is the configurable waiting time. After the Geo-Broadcast function is executed, we wait for the specified time. Then we put the information of responded TWs into the set W by the Worker Respond function during this time. If the W does not meet the quantity requirement, we would wait some time and do it again, or expand the search area ℂnow and run again until the W is satisfiedsati. Whether to expand the radius search depends on the urgency that the task needs to be completed. In Algorithm 2, we only give the way to expand the search area ℂnow. The waiting way is just a matter of setting a suspension and wake time.Algorithm 2: Get TWs.
Input: Cell number of TR in the cell x, t;Output:W//W=W1,W2,…,Wn the set of TWsInitializeW, L, ℕ, K, ℂnow, ℂbefore, ℂcache ← ∅;Initialize floatR ← 0;Initializev ← x. Generator Point;Initializeℂnow ← x;WhileW = ∅ doR ← Find R (ℂnow, v);Geo-Broadcast (R);Wait (t);W ← Worker Respond();ℂcache ← ℂnow;ℂnow ← ℂnow.Adjacency − ℂcache − ℂbefore;ℂbefore ← ℂcache;ReturnW;


### 5.4. Task Assignment Stage

④ to ⑦ in the workflow is the task assignment stage. By the task request stage mentioned above, the SC-server gotW. In this stage, its goal is to find the TW who meets the above constraints and is closest to the task location in the W.The TWs can arrive on time at the task’s location based on previous calculations. This record of TWs’ arrival time is only used as proof of later failure to arrive on time. The capability required to complete the task is sensitive information that exposes the information of the task and TW. It can be protected by encrypting the task capabilities. An additional ciphertext comparison is required in the encrypted task capability mode to confirm that the task requirements are met. The ciphertext comparison operation is the same as the encrypted location distance comparison. For the convenience of description, the plaintext task capability description is chosen in this paper. SC-server broadcasts this task information to find the suitable TW or TWs. Next, we need to solve another critical problem: to figure out the nearest TW or TWs.We can determine how far each TW is from the task according to the information they uploaded with Paillier’s properties. In mathematics, it is recorded asD=d1,d2,…,dn, di representing the encrypted distance from the TW labelled i to the task location. Let M be the matrix for recording the difference of encrypted distance, mij=di−djxij. In this equation, xij is randomly either 1 or −1 to perturb. Notes that mij=di−dj1=dj−di−1=mji−1. The value of mij represents the size relationship between di and dj. mij also records the relation between them. So we transmit one of them to the TR. Let the transmitted collection be the M. However, if we transmit M to the TR directly, the TR can deduce all distance magnitude relationships. To avoid such information leakage, we need to disrupt the order of M. As shown in Figure 5, the disrupting order of M is A, A=a1,a2,…,ann−1/2. SC-server selects the value of mij in M orderly, puts it into A randomly, and transmits A to the TR.Figure 5
Process of transmit between TR and SC-server.Since the value of elements inA is encrypted with the TR’s public key, she can decrypt the processed collection with her private key, get the relationship, and record them in ℝ, ℝ=R1,R2,...,Rnn−1/2. For an=〚A−B〛, if A−B>0, Rn = 1, if A−B<0, Rn = −1, if A−B=0, Rn = 0. The TR can easily judge the relationship between A and B but can not judge which is A and which is B. Because, when xij = 1, an=di−dj; when xij = -1, an=dj−di. In other words, getting the R-value is easy for the TR, but the relationship between A and B is difficult. She only has the value of an, sets the value of Rn by an, and returns the ℝ to the SC-server.Nowadays, for SC-server, getting the TW closest to the task locationℝ is a problem. To efficiently retrieve the information of the same element in A, ℝ, and M, we introduce 𝕄’. As shown in Figure 6, it stores the id of the matrix element in M and links the subscript table that stores the subscript of the element in A and the x table that stores the value of xij. Obviously, in a task, A, ℝ, 𝕄′, and M have the same sequence length. The TR got the ℝ according to the A. So, there is a one-to-one correspondence between ℝ and A. With the Subscript table, we can get the logic relationship represented by dotted arrows between 𝕄′ and ℝ. To facilitate calculations, we open a space R to record the value of ℝ in the linked table. It can help us to find the corresponding relation quickly.Figure 6
Storage structure and relationship of tables.With the relation, the following analysis can be obtained. Assumingan=di−djxij, when xij=1, an=di−dj. If the Rn=1, we can get di−dj>0. If Rn=−1, di−dj<0. When xij=−1, an=dj−di. If the Rn=1, we can get dj−di>0. If Rn=−1, dj−di<0. So we can obtain the relationship shown in the following equation.(8a)xij∗Rn=1⇒di>dj,(8b)xij∗Rn=−1⇒di<dj,(8c)xij∗Rn=0⇒di=dj,with this relationship and storage structure of tables, we can judge the size relationship between dn − 1 and dn by the value of x(n − 1)n times Rb. The value of x(n − 1)n and Rb can obtain by M′, x(n − 1)n = m(n − 1)n.x, Rb = m(n − 1)n.R. if we traverse the whole M′, we will get the number of TW closest to the task location. However, sometimes, when a task requires multiple TWs to complete, SC-server should find the top-k nearest TWs for it. If we find the nearest TW and do not make any changes, we will get the same TW every time we run the program. For the algorithm to be used multiple times, we inverted the value of its x after getting the nearest TW’s number. With this change, if SC-server wants to find the top-k nearest TWs, it just needs to perform k times. However, in the particular case of equality, the transitivity of the relationship is broken, causing the algorithm to fail. So we propose Algorithm 3 to find an equality relation. When Algorithm 4 finds the nearest TW number, it passes that number to Algorithm 3, which finds all equal distant numbers and returns them. After finding enough TWs to meet the requirements, SC-server establishes the link between the TR and TW or TWs by the number.Algorithm 3: FE.
Input: int i;Output: int x[];   //the queue of the nearest TWs’ numberInitialize intx[];Initialize intn, k;puti into x[];forj = 1 to ndoif (mij.R = 0)put thej into x[];whilex[n = 0] ! = null do;fork = 1 to int x[n]−1 domkx[n].x ← mkx[n].x∗ − 1;fork = int x[n] + 1 to ndomx[n]k.x ← mx[n]k.x∗ − 1;n++;returnx[];Algorithm 4: FMN.
Input: 𝕄’;Output: int x[];   //an array of the nearest TWs’ numbersInitialize intk, p, i ← n − 1, j ← n;   //n = D.lengthWhilei≠1dop ← mij.R∗mij.xifp = −1  //di<djj ← i, i ← i − 1;else  //di≥dji ← i − 1;p ← mij.R∗mij.xifp = 1  //return j, set j maxx[] = FE (j);returnx[];else  //return 1, set 1 maxx[] = FE (1);returnx[];In Algorithm3, we look for an equal value based on the number of the minimum value already found. According to the number of the minimum value, locate its row in the matrix M. Equal numbers can be found by traversing the value of R of this row. We put these equal minimums into a queue and modify their x values item by item.


## 5.1. Framework Workflow

We present the workflow of pMATE. The whole workflow is divided into three stages: the preparation stage, the task request stage, and the task assignment stage.Specifically, as a request task example shown in Figure3, there are seven steps in the workflow without the preparation stage.In ①, a TR sends its encrypted location information, the capability required to complete the task, the cell number obtained during the preparation stage, the public key, and the latest start time of the task to SC-server to initiate a task request. The SC-server numbers the task request and puts it intoT.In ②, the SC-server selects a task request fromT according to the recent start time and broadcasts it to TWs using the Find R and Get TWs algorithm based on the cell number received.In ③, TWs who want to get the task and meet the time and ability constraints reply to a message to SC-server based on the information they received. SC-server catches the response by the TWs Respond function, numbers these TWs, and puts their information intoWi. The i is the task number.In ④, SC-server determines whether the number in the setWi meets the requirements. If it does not, SC-server will expand R and repeat ②.After the number of TWs meets the requirements, SC-server selects the TWs in Wi and calculates the encrypted distance between them and the task point respectively, calculates the difference of ciphertext distance, and forms the difference into a sequence.In ⑤, the SC-server processes and disarranges the sequence and sends it to the TR.In ⑥, the TR decrypts the sequence and returns the relationship of size to SC-server.In ⑦, SC-server finds the nearest TW or TWs based on the relationship and associates the TR with TW or TWs.Figure 3
Workflow of pMATE.


## 5.2. Preparation Stage

In the previous part, we introduced the workflow of pMATE. Before that, there is a preparation stage in which we partition the map with VD. Ciphertext calculation and comparison are time-consuming, especially when many ciphertext calculations and comparisons are required. Because the data is encrypted, the value cannot be confirmed. All ciphertext value differences need to be calculated and compared each time. Moreover, these calculations are very time-consuming. Therefore, we plan to divide the map into regions to reduce the number of comparison samples and the time cost and improve efficiency. SC-server can locate an approximate range and expand its search until it matches the suitable TW or TWs when a TR submits a task request based on her/his partition number. Since the map information is publicly available in advance, it is easy to identify the authenticity.Compared with many other partition methods, the VD algorithm can guarantee a unique result and the shortest distance from the point in the cell to the generator point. With that, we can ensure the uniqueness of the partition and that the points in the cell have the same properties when we choose the intersections as the generator points of VD. For a cell, each point in it is the shortest distance to this intersection which belongs to the traffic road network. This division of the map according to road conditions is more realistic.VD as a fundamental structure has been researched and applied in many fields. In our work, to facilitate the Get TWs algorithm, some information about VD needs to be stored. The left part of Figure4 shows an example of the VD partition, and the right part presents its storage structure. Specifically, C1 is the cell number, V1 is its generator point, and p1,p2,p3,p4,p5 is the set of its vertexes. The Cell Number list records each cell. Each cell links a logic space that contains its generator called Generator Point, the set of its vertexes called Vertex, and the set of neighbor cells’ numbers called Adjacency. Since the map information can be obtained in advance, these calculations can also be completed before the task request stage, so the waiting time for the request will not increase. This stage is called the preparation stage.Figure 4
Voronoi diagram and voronoi diagram storage structure.


## 5.3. Task Request Stage

① to ③ in the workflow is the task request stage. In this stage, a TR submits a task request to SC-server. Then SC-server looks for TWs who want to get the task by the following algorithms. When a user wants to enjoy the services of the SC-server, she has to register with SC-Server and get VD information for the preparation phase. In other words, she needs to know her location’s cell number. When submitting a task request to SC-server, she needs to query her cell number according to the VD information obtained during registration. Furthermore, the map’s information is public, so she can quickly determine its reliability by comparing it with VD.In our framework, Euclidean distance is the key to matching tasks. Expanding equation (4), we can get the following:(6)dRW=latR−latW2+lngR−lngW2=latR2+latW2−2latR⋅latW+lngR2+lngW2−2lngR⋅lngW,dRW2=latR2+latW2−2latR⋅latW+lngR2+lngW2−2lngR⋅lngW.With the properties of Paillier, we can get the following:(7)dRW2=latR2⋅latW2⋅2latR−latW⋅lngR2⋅lngW2⋅2lngR−lngW.Due to thedRW≥0, dRW1≥dRW2⇔dRW12≥dRW22. So, we have to compare dRW2.In this stage, for the TR who wants to submit the task to SC-server, she needs to upload her cell number, the latest start timetR, and latR2, 2latR, lngR2, 2lngR to SC-server. SC-server broadcasts the task description, the task time, cell number, public key, and encrypted location information by the Geo-Broadcast [19] function to find TWs who want to get this job. Due to the cells of VD being irregular convex quadrilateral, it is difficult to determine the broadcast radius. As shown in Figure 4, the R1 is the broadcast radius we want to find for C1 in the first round. R1 is chosen as the broadcast radius to avoid the situation where the nearest TW is in the adjacent cell of C1 and is missed. We can see that the algorithm for finding TWs is divided into two parts. Part of it is to determine the broadcast radius based on the search area and broadcast to find TWs. Another part is expanding the search area when no TWs are found. So, we propose the Find R algorithm to find the suitable broadcast radius for the Get TWs algorithm. Find R’s initialization is finished as part of the Get TWs algorithm.Assuming a TR submits a task request, she uploads her cell number to SC-server, and SC-server can get her cell generator point, cell vertexes, and adjacency cell number according to the information obtained during the preparation stage. Let the cell generator point be the central point calledv, ℂ be the set of hunting cells, ℕ be the vertex sets of ℂ, L be the vertex sets of adjacency cells of ℂ, K be the set of the farthest possible point. K is the subtraction of L and ℕ, K = L–ℕ. In the Algorithm 1, C1.Vertex ∩C2.Vertex ∩⋯∩Cn.Vertex represents all vertexes of the search area. Calculate the distance between all points in K and v. The maximum value is the search radius, R. With R, we can get the Get TWs algorithm described as follows. It is a circular algorithm that collects TWs who want to get task number i into Wi. For simplicity, we adopt W instead of Wi.Algorithm 1: Find R.
Input: the set of hunting cells ℂ, central point v.Output:RL ← C1.Vertex ∩C2.Vertex ∩⋯∩Cn. Vertex; //ℂ = {C1, C2, …, Cn}K ← L–ℕ; //initialization in Get TWs algorithmR ← maxdv,Ki; //i = 1 to n;ℕ ← K;ReturnR;In Algorithm2, we need to initialize those sets: W, L, ℕ, K, ℂnow, ℂbefore, ℂcache. Those sets’ initial values are null. When we run Algorithm 1, we can get the broadcast radius according to the search area. We need to update the search area to get TWs. The TWs who want to get this task need to calculate how long it takes to get from their position to the generator of the task in the cell, and they can get the estimated arrival time tW, and upload tW, latW2, 2latR−latW, lngW2, 2lngR−lngW to SC-server for task matching. The Worker Respond function is a listener that puts received replies into the W. In Algorithm 2, t is the configurable waiting time. After the Geo-Broadcast function is executed, we wait for the specified time. Then we put the information of responded TWs into the set W by the Worker Respond function during this time. If the W does not meet the quantity requirement, we would wait some time and do it again, or expand the search area ℂnow and run again until the W is satisfiedsati. Whether to expand the radius search depends on the urgency that the task needs to be completed. In Algorithm 2, we only give the way to expand the search area ℂnow. The waiting way is just a matter of setting a suspension and wake time.Algorithm 2: Get TWs.
Input: Cell number of TR in the cell x, t;Output:W//W=W1,W2,…,Wn the set of TWsInitializeW, L, ℕ, K, ℂnow, ℂbefore, ℂcache ← ∅;Initialize floatR ← 0;Initializev ← x. Generator Point;Initializeℂnow ← x;WhileW = ∅ doR ← Find R (ℂnow, v);Geo-Broadcast (R);Wait (t);W ← Worker Respond();ℂcache ← ℂnow;ℂnow ← ℂnow.Adjacency − ℂcache − ℂbefore;ℂbefore ← ℂcache;ReturnW;


## 5.4. Task Assignment Stage

④ to ⑦ in the workflow is the task assignment stage. By the task request stage mentioned above, the SC-server gotW. In this stage, its goal is to find the TW who meets the above constraints and is closest to the task location in the W.The TWs can arrive on time at the task’s location based on previous calculations. This record of TWs’ arrival time is only used as proof of later failure to arrive on time. The capability required to complete the task is sensitive information that exposes the information of the task and TW. It can be protected by encrypting the task capabilities. An additional ciphertext comparison is required in the encrypted task capability mode to confirm that the task requirements are met. The ciphertext comparison operation is the same as the encrypted location distance comparison. For the convenience of description, the plaintext task capability description is chosen in this paper. SC-server broadcasts this task information to find the suitable TW or TWs. Next, we need to solve another critical problem: to figure out the nearest TW or TWs.We can determine how far each TW is from the task according to the information they uploaded with Paillier’s properties. In mathematics, it is recorded asD=d1,d2,…,dn, di representing the encrypted distance from the TW labelled i to the task location. Let M be the matrix for recording the difference of encrypted distance, mij=di−djxij. In this equation, xij is randomly either 1 or −1 to perturb. Notes that mij=di−dj1=dj−di−1=mji−1. The value of mij represents the size relationship between di and dj. mij also records the relation between them. So we transmit one of them to the TR. Let the transmitted collection be the M. However, if we transmit M to the TR directly, the TR can deduce all distance magnitude relationships. To avoid such information leakage, we need to disrupt the order of M. As shown in Figure 5, the disrupting order of M is A, A=a1,a2,…,ann−1/2. SC-server selects the value of mij in M orderly, puts it into A randomly, and transmits A to the TR.Figure 5
Process of transmit between TR and SC-server.Since the value of elements inA is encrypted with the TR’s public key, she can decrypt the processed collection with her private key, get the relationship, and record them in ℝ, ℝ=R1,R2,...,Rnn−1/2. For an=〚A−B〛, if A−B>0, Rn = 1, if A−B<0, Rn = −1, if A−B=0, Rn = 0. The TR can easily judge the relationship between A and B but can not judge which is A and which is B. Because, when xij = 1, an=di−dj; when xij = -1, an=dj−di. In other words, getting the R-value is easy for the TR, but the relationship between A and B is difficult. She only has the value of an, sets the value of Rn by an, and returns the ℝ to the SC-server.Nowadays, for SC-server, getting the TW closest to the task locationℝ is a problem. To efficiently retrieve the information of the same element in A, ℝ, and M, we introduce 𝕄’. As shown in Figure 6, it stores the id of the matrix element in M and links the subscript table that stores the subscript of the element in A and the x table that stores the value of xij. Obviously, in a task, A, ℝ, 𝕄′, and M have the same sequence length. The TR got the ℝ according to the A. So, there is a one-to-one correspondence between ℝ and A. With the Subscript table, we can get the logic relationship represented by dotted arrows between 𝕄′ and ℝ. To facilitate calculations, we open a space R to record the value of ℝ in the linked table. It can help us to find the corresponding relation quickly.Figure 6
Storage structure and relationship of tables.With the relation, the following analysis can be obtained. Assumingan=di−djxij, when xij=1, an=di−dj. If the Rn=1, we can get di−dj>0. If Rn=−1, di−dj<0. When xij=−1, an=dj−di. If the Rn=1, we can get dj−di>0. If Rn=−1, dj−di<0. So we can obtain the relationship shown in the following equation.(8a)xij∗Rn=1⇒di>dj,(8b)xij∗Rn=−1⇒di<dj,(8c)xij∗Rn=0⇒di=dj,with this relationship and storage structure of tables, we can judge the size relationship between dn − 1 and dn by the value of x(n − 1)n times Rb. The value of x(n − 1)n and Rb can obtain by M′, x(n − 1)n = m(n − 1)n.x, Rb = m(n − 1)n.R. if we traverse the whole M′, we will get the number of TW closest to the task location. However, sometimes, when a task requires multiple TWs to complete, SC-server should find the top-k nearest TWs for it. If we find the nearest TW and do not make any changes, we will get the same TW every time we run the program. For the algorithm to be used multiple times, we inverted the value of its x after getting the nearest TW’s number. With this change, if SC-server wants to find the top-k nearest TWs, it just needs to perform k times. However, in the particular case of equality, the transitivity of the relationship is broken, causing the algorithm to fail. So we propose Algorithm 3 to find an equality relation. When Algorithm 4 finds the nearest TW number, it passes that number to Algorithm 3, which finds all equal distant numbers and returns them. After finding enough TWs to meet the requirements, SC-server establishes the link between the TR and TW or TWs by the number.Algorithm 3: FE.
Input: int i;Output: int x[];   //the queue of the nearest TWs’ numberInitialize intx[];Initialize intn, k;puti into x[];forj = 1 to ndoif (mij.R = 0)put thej into x[];whilex[n = 0] ! = null do;fork = 1 to int x[n]−1 domkx[n].x ← mkx[n].x∗ − 1;fork = int x[n] + 1 to ndomx[n]k.x ← mx[n]k.x∗ − 1;n++;returnx[];Algorithm 4: FMN.
Input: 𝕄’;Output: int x[];   //an array of the nearest TWs’ numbersInitialize intk, p, i ← n − 1, j ← n;   //n = D.lengthWhilei≠1dop ← mij.R∗mij.xifp = −1  //di<djj ← i, i ← i − 1;else  //di≥dji ← i − 1;p ← mij.R∗mij.xifp = 1  //return j, set j maxx[] = FE (j);returnx[];else  //return 1, set 1 maxx[] = FE (1);returnx[];In Algorithm3, we look for an equal value based on the number of the minimum value already found. According to the number of the minimum value, locate its row in the matrix M. Equal numbers can be found by traversing the value of R of this row. We put these equal minimums into a queue and modify their x values item by item.


## 6. Security Analyses

In this section, we analyze the security of the pMATE scheme from the perspective of potential risks that existed in the task request and task assignment stage.Theorem 1.
pMATE can protect TR’s task location privacy during the task request stage if the Paillier cryptosystem is secure.Proof.
In pMATE, a TR encrypts his/her task location before he/she uploads them to SC-server, as mentioned above, likelatR2, 2latR, lngR2, 2lngR. SC-server will send them to TWs. Since only the TR has the private key, SC-server, TWs, and even no matter who gets this information, it will not be able to decrypt if the Pailier cryptosystem is secure. It makes sure the privacy of TR location information.Theorem 2.
pMATE can protect TWs' location privacy during the task request stage if the Paillier cryptosystem is secure.Proof.
In pMATE, TWs need to upload their encrypted location to SC-server based on the TR’s encrypted location received, as mentioned above, likelatW2, 2latR−latW, lngW2, 2lngR−lngW. SC-server owns encrypted information but not the private key. Conversely, the TR has the private key but no encrypted information. So both of them cannot get the location information of TWs if the Pailier cryptosystem works and there is no collusion between them.Theorem 3.
pMATE does not reveal location privacy during the task assignment stage. In other words, pMATE can protect the location privacy of both TR and TWs during the TD comparison process.Proof.
In the TD comparison process, the SC-server can figure out encrypted TDs, as mentioned above, likeD=d1,d2,…,dn. And it figures out M, which sequence consisted of the difference of TDs, and gets A by disrupting the order of M randomly. Since SC-server does not have the private key, it sends A to the TR to determine the size relationship of TD. Now the TR can know the value of each element in A by the private key. However, since A is perturbed twice, TR cannot obtain any information to infer the location information of TW. Specifically, the first perturbation is to shuffle the positions of elements in M. It makes it impossible for the TR to determine which two TDs are compared based on the element’s position. The second perturbation is the addition of a random number xij. As mentioned above, an=di−djxij, when xij=1, an=di−dj, when xij=−1, an=dj−di. The TR only knows the value of an, but cannot get the size relationship of di and dj. Because the TR has no additional information to infer, it is similar to the one-time pad. For example, if you get the number 5, you cannot speculate which two numbers this number is calculated from. Further, suppose an=A−B, if you get the value of an, you cannot infer the size relationship between A and B. All in all, the TR cannot get the location information of TWs. The TR returns the relation ℝ to SC-server, which cannot get the location information of TWs too.


## 7. Performance Analysis

### 7.1. Experiment Setting

In this section, we will evaluate the performance of our proposed pMATE through some experiments. Similar to the work [22], we experimental data through a real-world dataset, Gowalla. Gowalla is a historical record set which records the social network users' check-in location information on social networks. We choose 110 check-in data in San Francisco with a latitude from 37.75431 to 37.80062 and a longitude from −122.42691 to −122.39382. We choose 100 check-in data as the TWs. The remaining ten pieces of data are used as the TRs. And TRs all satisfy the task conditions.The experimental machine is a personal computer (PC) with a Core i7 CPU and 16 GB RAM and a smartphone with Kirin 990 CPU and 8 GB RAM. We use the smartphone to simulate TW or TR encryption of a task and test its time consumption. We use the PC to simulate task allocation in SC-server. We use Baidu Map to find the longitude and latitude of the crossroads in the experimental area, San Francisco, and generate VD according to it. Instead of CSP’s broadcast function, we look for TWs within the radius. We evaluate the scheme’s performance using encryption time, task allocation time, and task TD.


### 7.2. Evaluation Results

All methods, including ours, need to encrypt the task information before TRs and TWs apply for services to SC-server. In pMatch [20], TRs and TWs mainly perform exponential operations in the bilinear map. Assume that their number of sensors is three. They do not need to perform decryption operations. SC-server can compare the encrypted information. As same as [22, 23], we choose the Paillier cryptosystem to encrypt the task information. So we experiment with the encryption time of TRs and TWs between pMATE and pMatch. As shown in Figure 7, we record the encryption time of all TRs and their corresponding TW, respectively.Figure 7
The comparison of encryption time between pMATE and pMatch.After comparing the time of encryption, we mainly conduct comparative experiments on task allocation time. We randomly select 10 TWs from all TWs for task allocation for each TR and record the time to complete the task allocation in Figure8. Similar to previous schemes [22, 23], pMATE is to find the nearest TW according to TD. But in ETA [22], they try to find an approximation to the nearest TW. As shown in Figure 8, the pMATE’s consume-time is usually less than others because it uses the VD to shrink the set of matching TWs. The ETA [22] also wants to reduce the number of samples. However, its effect fluctuates wildly due to it being without an extension algorithm. Its time consumption depends entirely on the number of TWs randomly appearing in its partitioned area. In ETA [22], there is no specific rule for its division. However, if it is too large, it will contain too many TWs; if it is too small, there may be no TWs. In the experiment of this paper, if there are no TWs, the area will be doubled and re-divided until there are TWs. However, we can see that they have reduced the time consumption because they all use the method of reducing the number of samples. The record shows that the pMATE and ETA still have a similar time consumption on 2, 4, 5, and 8. Analyzing the experimental data, we found that the number of TWs in their search area is almost the same. But for the rest, pMATE can significantly improve the matching efficiency. A possible explanation is that the pMATE places the TR near the center of the search area. In iTAM [23], it is more time consuming than both ETA and pMATE due to the need to retrieve all tasks. In pMatch [20], its primary operations are bilinear map operations resulting in a high time overhead.Figure 8
The comparison of task allocation time among iTAM, ETA, pMATE.Another important indicator is the accuracy of the match. In other words, whether the matching TW is the nearest one from the task location. ETA, iTAM, and ours are all trying to find the nearest TW. So, we calculate the TD of the selected TW to the task location in each group. To compare obviously, we introduced a set of matching results in No-privacy. As shown in Figure9, pMATE and iTAM can find the nearest TW, except for the ETA method. However, iTAM found the nearest TW by searching for all TWs. So although it can find the nearest TW, it takes a high time consumption. ETA reduces the search range but does not provide the corresponding search algorithm. So there is only a high chance of finding the nearest TW. Analysis of the incorrect situation of the ETA shows that the selected TW is only closest within the search area and not globally closest. It also verifies the deviation due to the lack of search algorithms.Figure 9
The comparison of task TD among No-privacy, iTAM, ETA, pMATE.


## 7.1. Experiment Setting

In this section, we will evaluate the performance of our proposed pMATE through some experiments. Similar to the work [22], we experimental data through a real-world dataset, Gowalla. Gowalla is a historical record set which records the social network users' check-in location information on social networks. We choose 110 check-in data in San Francisco with a latitude from 37.75431 to 37.80062 and a longitude from −122.42691 to −122.39382. We choose 100 check-in data as the TWs. The remaining ten pieces of data are used as the TRs. And TRs all satisfy the task conditions.The experimental machine is a personal computer (PC) with a Core i7 CPU and 16 GB RAM and a smartphone with Kirin 990 CPU and 8 GB RAM. We use the smartphone to simulate TW or TR encryption of a task and test its time consumption. We use the PC to simulate task allocation in SC-server. We use Baidu Map to find the longitude and latitude of the crossroads in the experimental area, San Francisco, and generate VD according to it. Instead of CSP’s broadcast function, we look for TWs within the radius. We evaluate the scheme’s performance using encryption time, task allocation time, and task TD.


## 7.2. Evaluation Results

All methods, including ours, need to encrypt the task information before TRs and TWs apply for services to SC-server. In pMatch [20], TRs and TWs mainly perform exponential operations in the bilinear map. Assume that their number of sensors is three. They do not need to perform decryption operations. SC-server can compare the encrypted information. As same as [22, 23], we choose the Paillier cryptosystem to encrypt the task information. So we experiment with the encryption time of TRs and TWs between pMATE and pMatch. As shown in Figure 7, we record the encryption time of all TRs and their corresponding TW, respectively.Figure 7
The comparison of encryption time between pMATE and pMatch.After comparing the time of encryption, we mainly conduct comparative experiments on task allocation time. We randomly select 10 TWs from all TWs for task allocation for each TR and record the time to complete the task allocation in Figure8. Similar to previous schemes [22, 23], pMATE is to find the nearest TW according to TD. But in ETA [22], they try to find an approximation to the nearest TW. As shown in Figure 8, the pMATE’s consume-time is usually less than others because it uses the VD to shrink the set of matching TWs. The ETA [22] also wants to reduce the number of samples. However, its effect fluctuates wildly due to it being without an extension algorithm. Its time consumption depends entirely on the number of TWs randomly appearing in its partitioned area. In ETA [22], there is no specific rule for its division. However, if it is too large, it will contain too many TWs; if it is too small, there may be no TWs. In the experiment of this paper, if there are no TWs, the area will be doubled and re-divided until there are TWs. However, we can see that they have reduced the time consumption because they all use the method of reducing the number of samples. The record shows that the pMATE and ETA still have a similar time consumption on 2, 4, 5, and 8. Analyzing the experimental data, we found that the number of TWs in their search area is almost the same. But for the rest, pMATE can significantly improve the matching efficiency. A possible explanation is that the pMATE places the TR near the center of the search area. In iTAM [23], it is more time consuming than both ETA and pMATE due to the need to retrieve all tasks. In pMatch [20], its primary operations are bilinear map operations resulting in a high time overhead.Figure 8
The comparison of task allocation time among iTAM, ETA, pMATE.Another important indicator is the accuracy of the match. In other words, whether the matching TW is the nearest one from the task location. ETA, iTAM, and ours are all trying to find the nearest TW. So, we calculate the TD of the selected TW to the task location in each group. To compare obviously, we introduced a set of matching results in No-privacy. As shown in Figure9, pMATE and iTAM can find the nearest TW, except for the ETA method. However, iTAM found the nearest TW by searching for all TWs. So although it can find the nearest TW, it takes a high time consumption. ETA reduces the search range but does not provide the corresponding search algorithm. So there is only a high chance of finding the nearest TW. Analysis of the incorrect situation of the ETA shows that the selected TW is only closest within the search area and not globally closest. It also verifies the deviation due to the lack of search algorithms.Figure 9
The comparison of task TD among No-privacy, iTAM, ETA, pMATE.


## 8. Conclusion

In this paper, we proposed pMATE, a privacy-preserving task assignment scheme to solve the optimization problems for minimum travel distance. We use the Paillier cryptosystem to encrypt the task information of both TRs and TWs to protect their privacy. To improve the retrieval efficiency, we use VD to divide the map and propose FindR and Get TWs algorithms to search for the candidate TWs. For these encrypted data of candidates and the structures of Voronoi storage, we propose FMN and FE algorithms that can efficiently complete the data comparison to find the TW who is the minimum travel distance to the task location. Finally, we verified the effectiveness and superiority of the scheme from three aspects: encryption time, task assignment time, and accuracy through experiments. In future work, we will focus on packaging multiple tasks and assigning them to a single worker to increase efficiency.



---

*Source: 9477320-2023-01-30.xml*