# User Sensitive Information Protection Scheme Based on Blockchain Technology

Authors: Sheng Luo
Journal: Mobile Information Systems
 (2022)

---

## Abstract

With the continuous development of mobile applications and location technology,k-anonymity technology is usually used to protect the privacy and security of users in location-based services that are used by mobile users. Due to the self-interest of users, in the cooperative construction of a k-anonymity privacy protection scheme, it is difficult to guarantee the honest cooperation behavior of the requesting and cooperating users. To solve the above problems, this paper proposes a distributed k-anonymous location privacy protection scheme based on blockchain. In this paper, we record the requesting users, cooperative users, and their location information as evidence, and we punish the users with location leakage and deception. An anonymous zone cannot be constructed when the user is a requesting user. An interactive record mechanism is designed to constrain the self-interest behavior of the requesting and cooperating users in the process of anonymous region construction. Security analysis and experiments show that this scheme can effectively protect the user’s location privacy, promote the honest cooperation between the requesting user and the cooperative user, and encourage more users to participate in the construction of an anonymous zone.


---

## Body

## 1. Introduction

In recent years, with the rapid development of GPS equipment and mobile information technology, location-based services (LBS) have become one of the most developed potential services for mobile users [1]. LBS means that mobile services are more colorful according to the geographic location. LBS provides consumers with a series of location-based services and convenient experiences from social networks, navigation, takeout platforms, and so on. However, when people obtain location services through the network, they also expose their location information to LBS providers, which threatens the disclosure of the private information of users.To prevent the leakage of privacy information, scholars have proposed many location privacy protection methods, includingk-anonymity, differential privacies, location coordinate transformation, and cryptography-based methods [2–4]. Among them, k-anonymity is the most common method in LBS location privacy protection [5]. The basic idea of this method is that when sending an LBS query request, the user first obtains at least the real location of other k-1 cooperative users, then constructs an anonymous area, and then submits the anonymous area to a location-based services platform (LSP) instead of his real location, to effectively protect his personal location privacy. However, there are still two problems in k-anonymous location privacy protection. On the one hand, after the requesting user receives the real location provided by the cooperative user, the self-interested requesting user will disclose the location information to the third party to obtain additional benefits. Alternatively, the malicious attacker will disguise himself as a requesting user to obtain the real location of the collaborative user, which will lead to the disclosure of the location privacy of the collaborative user. On the other hand, after the cooperative user receives the collaboration request sent by the requesting user, even if some cooperative users are located in sensitive areas, they will still provide false locations to the requesting users to improve their activity (or reputation) due to their self-interest, to enable them to construct anonymous regions efficiently when they are requesters. It can be seen that the existing distributed K anonymous location privacy protection scheme cannot completely protect the user’s location privacy. Because blockchain technology has great advantages in information security protection, it has been widely used in AI and medical fields [6, 7]. To solve the above problems, this paper proposes a distributed k-anonymity location privacy protection scheme based on blockchain from the user’s self-interested behavior. According to the data, this scheme is the first to use blockchain to study LBS location privacy protection. The research results have certain practical significance and applications value.


## 2. Related Work

In recent years, there have been many research studies on the privacy protection of user location information, and some achievements have been made. This method was first proposed by Chow et al. and its basic idea is to make requests of users to obtain the real locations of at leastk−1 other cooperative users by point-to-point communication to construct an anonymous area, for the purpose of making the LSP guess the real location of the requesting user from the anonymous area with a probability of no more than 1/K [8]. Ghinita et al. used the hibernate curve to map the location information of the requesting users and cooperative users from two-dimensional space to one-dimensional space, and they stored the one-dimensional location information of each user in the data node of a B+tree, which enables the requesting user to quickly obtain the real locations of the adjacent cooperative users in the constructed anonymous area [9, 10]. However, when there are many cooperative users, the requesting users must retrieve from the root node of the B+tree, which increases the computational cost of the requesting users. To solve this problem, reference [11] uses a ring structure instead of a B+tree structure to store the one-dimensional locations of all of the users, which means that the requesting user can quickly find the adjacent users and construct the anonymous area. Chen et al. pointed out that the requesting user should combine with the actual road traffic network when constructing the anonymous area; otherwise, the LSP could identify the real location of some cooperative users from the anonymous area submitted by the requesting user according to the road traffic network and could even directly identify the real location of the requesting user [12]. They make LBS queries on each road for the requesting users and set different quality of service. On the premise of ensuring the quality of service, the generated anonymous area contains as many intersections as possible to improve the location privacy protection level of the requesting user.In research on the location acquisition method of the collaborative users in a distributed environment, Chow et al. proposed to use the real location of historical cooperative users to construct an anonymous area for the requesting users [13, 14]. In their scheme, the requesting user stored the location information of the cooperative user after each LBS query. If the number of collaborative users obtained in the next LBS query did not meet the requirements of the location privacy protection, then the location information provided by the historical cooperative users could be directly used to construct the anonymous region. To reduce the storage cost of the requesting user, Kim et al. used the Hibert curve to reduce the dimension of the location information of the historical cooperative users, and they used the information entropy of the constructed anonymous area to measure the location privacy protection level of the requesting user; in addition, they proposed a distributed K anonymous location privacy protection scheme based on a grid [15]. In addition to using the location information of historical cooperative users, some scholars have proposed two distributed k-anonymity location privacy protection schemes based on region awareness, combining them with the existing mobile communication infrastructure [16, 17]. In addition, Che et al. proposed a two-way active distributed k-anonymity privacy protection scheme by letting all of the users in the network send information tables of their real locations and the locations of their neighbors [18–20].In research on incentive mechanisms in distributedk-anonymity, Yang et al. pointed out that the original distributed k-anonymity privacy protection schemes assume that the cooperative users are honest. They will provide their real location to the requesting user after receiving a request from the anonymous zone collaborative construction [21]. However, in the real world, users are self-interested. If the requesting users directly use these schemes to protect their location privacy in an LBS query, it will be difficult to obtain enough real locations of cooperative users to construct an anonymous area. They use a single round sealed double auction mechanism to allow multiple users to obtain the real location of the cooperative users by auction, thus encouraging all users in the network to participate in the construction of the anonymous area. In addition, Gong et al. pointed out that to better protect the location privacy of the requesting user, the requesting user and the cooperating user must use pseudonyms when participating in the anonymous region construction [22, 23]. Therefore, to encourage cooperative users to change their pseudonyms, they regard the requesting users and cooperative users as a special social group. Based on the social relationships among the group users, they use the maximum group income to encourage cooperative users to change their pseudonyms when they participate in the anonymous region construction.To summarize, the existing distributedk-anonymity location privacy protection schemes do not consider the privacy disclosure and deception behavior in the process of constructing the anonymous region. Therefore, this paper proposes a distributed k-anonymous location privacy protection scheme based on blockchain. In this paper, we record the requesting users, cooperative users, and their location information as evidence, and we punish the users who have location leakage and deception. The anonymous zone cannot be constructed when one of these users is the requesting user. An interactive record mechanism is designed to constrain the self-interest behavior of the requesting and cooperating users in the process of anonymous region construction. Second, this paper uses the blockchain technology to effectively prevent the requesting users from disclosing the location information of the cooperative users, and at the same time, it can encourage the cooperative users to provide the real location to participate in the construction of the anonymous area. Finally, experiments show that when the requesting user uses this scheme to construct the anonymous area, the computational cost, communication cost, and storage cost of the cooperative user are less, and the anonymous area can be constructed efficiently. This finding shows that the scheme has good practicability.


## 3. Research Model

### 3.1. Blockchain Technology

The concept of blockchain was first proposed by a scholar whose pseudonym is “Nakamoto cong;” blockchain was described as a distributed ledger based on a chain structure. In the ledger, data blocks are linked in the order of being generated over time. Cryptography and consensus algorithms are used to ensure the distribution consistency, tamper proof nature, and unforgeability of the account book data [24, 25]. The basic framework of blockchain can be divided into six layers: data layer, network layer, consensus layer, incentive layer, contract layer, and application layer [26].


#### 3.1.1. Data Layer

The main function of the data layer is to record and store the information on the chain and to ensure the unforgeability and traceability of the data through a Merkle tree, asymmetric encryption algorithm, hash function, time stamp, and other technologies.


#### 3.1.2. Network Layer

The main function of the network layer is to transfer and verify the data through a point-to-point network.


#### 3.1.3. Consensus Layer

The consensus layer mainly uses a consensus algorithm to achieve a stable consensus among the distributed nodes, to ensure the consistency and authenticity of the data.


#### 3.1.4. Incentive Layer

In a blockchain, the data set is maintained by all of the nodes. To encourage nodes to actively participate in the maintenance of the blockchain, the incentive layer encapsulates the allocation rules and payment rules that are compatible with the incentive, to maximize the profits of each node while participating in the maintenance of the blockchain.


#### 3.1.5. Contract Layer

The contract layer mainly provides the development environment of the smart contracts, including the sandbox environment of the blockchain platform and the corresponding programming language.


#### 3.1.6. Application Layer

The application layer is used to realize the application of blockchain technology in various applications scenarios. According to the different applications scenarios, the development of blockchain technology is divided into three stages: programmable currency, programmable finance, and programmable society [27].


### 3.2. Model Description

In this paper, a point-to-point equality structure is adopted. It is composed of a requesting user, cooperative user, and LSP, and no third party is required. It is assumed that there are secure communications links between the requesting user and the cooperating user and between the requesting user and the LSP [22]. When the requesting user P0 sends a query request to the LSP, the requesting user first sends a collaboration request to the surrounding users to obtain their real locations. After receiving the locations Loc1real,Loc2real,⋯,LocK−1real provided by cooperative users P1,P2,⋯,PK−1, the requesting user constructs the anonymous area ACR and submits it to the LSP together with the query content.After the LSP authenticates the identity of the requesting userP0, it searches the database according to the anonymous area and query content submitted by the requesting user, and it returns all of the results to the requesting user P0. After receiving the query results sent by the LSP, the requesting user P0 filters them according to their real location Loc0real to obtain accurate query results. Among them, Locireal represents the true location of the i1⩽i⩽K−1−th collaborative user Pi. For the anonymous zone, we have ACR=AreaLoc0real,Loc1real,Loc2real,⋯,LocK−1real. Area• is the anonymous area constructor, and K represents the privacy protection requirements of the requesting user P0.In addition, this paper assumes that both the requesting user and the cooperative user are rational; in other words, in the process of constructing the anonymous area, they always choose according to maximizing their own interests. For the rational requesting userP0, he first expects to obtain the real location provided by the cooperative user to generate the anonymous area ACR. Second, when the anonymous area is constructed successfully, it will disclose the real location of the cooperative users to obtain more additional benefits. Therefore, in the process of constructing the anonymous area, the rational requesting user’s preference satisfaction is the following: Among them, U+−>U−>U−−>U−−−,where(1)
U+− represents the profit when the user P0 successfully constructs the anonymous area and discloses the real location of the cooperative user Pi(2)
U− represents the profit when the user P0 successfully constructs the anonymous area without disclosing the real location of the cooperative user Pi(3)
U−− represents the profit when the user P0 fails to successfully construct the anonymous area and discloses the real location of the cooperative user Pi(4)
U−−− represents the profit when the user P0 fails to successfully construct the anonymous area and does not disclose the real location of the cooperative user PiFor the rational cooperative userPi, he first hopes to protect his location privacy; second, he can effectively protect his location privacy and, at the same time, provide collaborative help for the requesting user. Therefore, in the process of constructing the anonymous region, the preference of the rational cooperative user Pi satisfies the following requirements: W+−>W−>W−−>Wf−>W−−−.
(1)
W+− is the profit when the cooperative user Pi provides the false location Locifake to the requesting user P0, and the requesting user P0 uses the false location to construct the anonymous area(2)
W− is the profit when the cooperative user Pi provides the real location Locireal to the requesting user P0, and the requesting user P0 did not disclose the location(3)
W−− is the profit when the cooperative user Pi does not provide the location information to cooperate with user P0 to construct the anonymous area(4)
Wf− is the profit when the cooperative user Pi provides the false location Locifake to the requesting user P0, but the requesting user identifies it correctly and does not use the location to construct the anonymous area(5)
W−−− represents the profit when the cooperative user Pi provides his/her real location Locireal to the requesting user P0 but requests that user P0 disclose his/her real location


### 3.3. Model Security Definition

In this paper, the requesting user and the surrounding cooperative user are regarded as attackers. In the process of constructing a distributed anonymous area, self-interest request-users are to disclose the location information provided by cooperative users to a third party to obtain additional benefits. However, after receiving the anonymous region construction request sent by the requesting user, the self-interest cooperative user might provide false location information to the requesting user, which makes the anonymous area constructed by the requesting user unable to meet the privacy protection requirements, and it even enables the LSP to directly infer the personal privacy of the requesting user.To clearly define the security of the distributed anonymous zone construction, this paper regards the cooperative construction of the anonymous zone as a two-party game between the requesting userP0 and the cooperative user Pi. First, the cooperative construction game of the anonymous zone is formally described.Definition 1 (Anonymous zone cooperative construction game).
The anonymous region cooperative construction game is a five-tupleGACR=P,A,H,F,U. Among them are the following:
(i)
P=P0,Pi is the rational user set; P0 is the requesting user; Pi is the cooperative user(ii)
A=A0,Ai is the policy set of participants, where A0=a01,a02 is the policy set of the requesting user P0 . Here, a01 means that the requesting user P0 will not disclose the location Loci to the third party after receiving it, and a02 means that the requesting user P0 will disclose the location Loci provided by cooperative user Pi to a third party after receiving it. Ai=ai1,ai2,ai3 is the policy set of the cooperative user Pi; ai1 means that the cooperative user Pi provides its own real location Locireal to the requesting user P0 after receiving the collaboration request, ai2 means that the collaborative user Pi does not provide location information to the requesting user P0 after receiving the collaboration request, and ai3 indicates that the cooperative user Pi provides a false location Locifake to the requesting user P0 after receiving the cooperation request. Moreover, in the anonymous zone cooperative construction game GACR, the requesting user and the cooperative user each choose a strategy form vector a=a0,ai as the rational user’s strategy combination. Among them, a0∈A0;ai∈Ai(iii)
H is the set of histories. Any history h∈H represents the combination of policies selected by rational users at the corresponding time. Obviously, the null character τ∈H represents the beginning of the cooperative construction game of the anonymous area. For any history h∈H, all policy combinations that can appear after it are recorded as Ah=ah,a∈H .If there is h′∈H such that Ah′=∅, then the history h′ is said to be terminated. The set Z represents the set of all termination histories(iv)
F:H/Z⟶P is the user assignment function, which specifies the user who will make the next policy selection for the history h∈H\Z without termination. In the anonymous area cooperative construction game, rational cooperative user Pi takes the lead in policy selection, and thus, Fτ=Pi(v)
U=u0,ui is the revenue set of rational users. Among them, u0∈U+−,U−,U−−,U−−− is the revenue function of the rational requesting user P0, and ui∈W+−,W−,W−−,Wf−,W−−− is the revenue function of the rational cooperative user Pi
Based on the formal description of the anonymity zone cooperative construction game model, the security definition of distributedk-anonymity is given below.Definition 2 (Security of distributedk-anonymous location privacy protection).
Suppose thatP0 is a rational requesting user and P1,P2,⋯,PK−1 is K−1 rational cooperative users. When the rational user P0 uses the distributed k-anonymous privacy protection scheme to send a cooperative anonymous area request to P1,P2,⋯,PK−1, and there is successful construction of the anonymous area ACR, the following conditions are true:
(1)u0=U−,ui=W,−PrLSPLoc0real∣ACR⩽1K.Then, the distributedk-anonymous location privacy protection scheme is called secure. Here, K represents the location privacy protection requirement of the requesting user P0 when sending the current LBS query. Here, 1⩽i⩽k−1. PrLSPLoc0realACR represents the probability that LSP can correctly identify its real location Loc0real from the anonymous area ACR submitted by the requesting userP0.In the above definitions, formula (1) defines the security of the distributed k-anonymous location privacy protection from the perspective of anonymous region construction. Formula (1) indicates that the requesting user P0 will not disclose the location of the cooperative user during the construction of the anonymous area. Formula (1) indicates that during the construction of the anonymous area, cooperative user Pi provides its own real location Loc0real to the requesting user P0. Formula (1) defines the security of the distributed k-anonymous location privacy protection from the perspective of the LBS query.


## 3.1. Blockchain Technology

The concept of blockchain was first proposed by a scholar whose pseudonym is “Nakamoto cong;” blockchain was described as a distributed ledger based on a chain structure. In the ledger, data blocks are linked in the order of being generated over time. Cryptography and consensus algorithms are used to ensure the distribution consistency, tamper proof nature, and unforgeability of the account book data [24, 25]. The basic framework of blockchain can be divided into six layers: data layer, network layer, consensus layer, incentive layer, contract layer, and application layer [26].


### 3.1.1. Data Layer

The main function of the data layer is to record and store the information on the chain and to ensure the unforgeability and traceability of the data through a Merkle tree, asymmetric encryption algorithm, hash function, time stamp, and other technologies.


### 3.1.2. Network Layer

The main function of the network layer is to transfer and verify the data through a point-to-point network.


### 3.1.3. Consensus Layer

The consensus layer mainly uses a consensus algorithm to achieve a stable consensus among the distributed nodes, to ensure the consistency and authenticity of the data.


### 3.1.4. Incentive Layer

In a blockchain, the data set is maintained by all of the nodes. To encourage nodes to actively participate in the maintenance of the blockchain, the incentive layer encapsulates the allocation rules and payment rules that are compatible with the incentive, to maximize the profits of each node while participating in the maintenance of the blockchain.


### 3.1.5. Contract Layer

The contract layer mainly provides the development environment of the smart contracts, including the sandbox environment of the blockchain platform and the corresponding programming language.


### 3.1.6. Application Layer

The application layer is used to realize the application of blockchain technology in various applications scenarios. According to the different applications scenarios, the development of blockchain technology is divided into three stages: programmable currency, programmable finance, and programmable society [27].


## 3.1.1. Data Layer

The main function of the data layer is to record and store the information on the chain and to ensure the unforgeability and traceability of the data through a Merkle tree, asymmetric encryption algorithm, hash function, time stamp, and other technologies.


## 3.1.2. Network Layer

The main function of the network layer is to transfer and verify the data through a point-to-point network.


## 3.1.3. Consensus Layer

The consensus layer mainly uses a consensus algorithm to achieve a stable consensus among the distributed nodes, to ensure the consistency and authenticity of the data.


## 3.1.4. Incentive Layer

In a blockchain, the data set is maintained by all of the nodes. To encourage nodes to actively participate in the maintenance of the blockchain, the incentive layer encapsulates the allocation rules and payment rules that are compatible with the incentive, to maximize the profits of each node while participating in the maintenance of the blockchain.


## 3.1.5. Contract Layer

The contract layer mainly provides the development environment of the smart contracts, including the sandbox environment of the blockchain platform and the corresponding programming language.


## 3.1.6. Application Layer

The application layer is used to realize the application of blockchain technology in various applications scenarios. According to the different applications scenarios, the development of blockchain technology is divided into three stages: programmable currency, programmable finance, and programmable society [27].


## 3.2. Model Description

In this paper, a point-to-point equality structure is adopted. It is composed of a requesting user, cooperative user, and LSP, and no third party is required. It is assumed that there are secure communications links between the requesting user and the cooperating user and between the requesting user and the LSP [22]. When the requesting user P0 sends a query request to the LSP, the requesting user first sends a collaboration request to the surrounding users to obtain their real locations. After receiving the locations Loc1real,Loc2real,⋯,LocK−1real provided by cooperative users P1,P2,⋯,PK−1, the requesting user constructs the anonymous area ACR and submits it to the LSP together with the query content.After the LSP authenticates the identity of the requesting userP0, it searches the database according to the anonymous area and query content submitted by the requesting user, and it returns all of the results to the requesting user P0. After receiving the query results sent by the LSP, the requesting user P0 filters them according to their real location Loc0real to obtain accurate query results. Among them, Locireal represents the true location of the i1⩽i⩽K−1−th collaborative user Pi. For the anonymous zone, we have ACR=AreaLoc0real,Loc1real,Loc2real,⋯,LocK−1real. Area• is the anonymous area constructor, and K represents the privacy protection requirements of the requesting user P0.In addition, this paper assumes that both the requesting user and the cooperative user are rational; in other words, in the process of constructing the anonymous area, they always choose according to maximizing their own interests. For the rational requesting userP0, he first expects to obtain the real location provided by the cooperative user to generate the anonymous area ACR. Second, when the anonymous area is constructed successfully, it will disclose the real location of the cooperative users to obtain more additional benefits. Therefore, in the process of constructing the anonymous area, the rational requesting user’s preference satisfaction is the following: Among them, U+−>U−>U−−>U−−−,where(1)
U+− represents the profit when the user P0 successfully constructs the anonymous area and discloses the real location of the cooperative user Pi(2)
U− represents the profit when the user P0 successfully constructs the anonymous area without disclosing the real location of the cooperative user Pi(3)
U−− represents the profit when the user P0 fails to successfully construct the anonymous area and discloses the real location of the cooperative user Pi(4)
U−−− represents the profit when the user P0 fails to successfully construct the anonymous area and does not disclose the real location of the cooperative user PiFor the rational cooperative userPi, he first hopes to protect his location privacy; second, he can effectively protect his location privacy and, at the same time, provide collaborative help for the requesting user. Therefore, in the process of constructing the anonymous region, the preference of the rational cooperative user Pi satisfies the following requirements: W+−>W−>W−−>Wf−>W−−−.
(1)
W+− is the profit when the cooperative user Pi provides the false location Locifake to the requesting user P0, and the requesting user P0 uses the false location to construct the anonymous area(2)
W− is the profit when the cooperative user Pi provides the real location Locireal to the requesting user P0, and the requesting user P0 did not disclose the location(3)
W−− is the profit when the cooperative user Pi does not provide the location information to cooperate with user P0 to construct the anonymous area(4)
Wf− is the profit when the cooperative user Pi provides the false location Locifake to the requesting user P0, but the requesting user identifies it correctly and does not use the location to construct the anonymous area(5)
W−−− represents the profit when the cooperative user Pi provides his/her real location Locireal to the requesting user P0 but requests that user P0 disclose his/her real location


## 3.3. Model Security Definition

In this paper, the requesting user and the surrounding cooperative user are regarded as attackers. In the process of constructing a distributed anonymous area, self-interest request-users are to disclose the location information provided by cooperative users to a third party to obtain additional benefits. However, after receiving the anonymous region construction request sent by the requesting user, the self-interest cooperative user might provide false location information to the requesting user, which makes the anonymous area constructed by the requesting user unable to meet the privacy protection requirements, and it even enables the LSP to directly infer the personal privacy of the requesting user.To clearly define the security of the distributed anonymous zone construction, this paper regards the cooperative construction of the anonymous zone as a two-party game between the requesting userP0 and the cooperative user Pi. First, the cooperative construction game of the anonymous zone is formally described.Definition 1 (Anonymous zone cooperative construction game).
The anonymous region cooperative construction game is a five-tupleGACR=P,A,H,F,U. Among them are the following:
(i)
P=P0,Pi is the rational user set; P0 is the requesting user; Pi is the cooperative user(ii)
A=A0,Ai is the policy set of participants, where A0=a01,a02 is the policy set of the requesting user P0 . Here, a01 means that the requesting user P0 will not disclose the location Loci to the third party after receiving it, and a02 means that the requesting user P0 will disclose the location Loci provided by cooperative user Pi to a third party after receiving it. Ai=ai1,ai2,ai3 is the policy set of the cooperative user Pi; ai1 means that the cooperative user Pi provides its own real location Locireal to the requesting user P0 after receiving the collaboration request, ai2 means that the collaborative user Pi does not provide location information to the requesting user P0 after receiving the collaboration request, and ai3 indicates that the cooperative user Pi provides a false location Locifake to the requesting user P0 after receiving the cooperation request. Moreover, in the anonymous zone cooperative construction game GACR, the requesting user and the cooperative user each choose a strategy form vector a=a0,ai as the rational user’s strategy combination. Among them, a0∈A0;ai∈Ai(iii)
H is the set of histories. Any history h∈H represents the combination of policies selected by rational users at the corresponding time. Obviously, the null character τ∈H represents the beginning of the cooperative construction game of the anonymous area. For any history h∈H, all policy combinations that can appear after it are recorded as Ah=ah,a∈H .If there is h′∈H such that Ah′=∅, then the history h′ is said to be terminated. The set Z represents the set of all termination histories(iv)
F:H/Z⟶P is the user assignment function, which specifies the user who will make the next policy selection for the history h∈H\Z without termination. In the anonymous area cooperative construction game, rational cooperative user Pi takes the lead in policy selection, and thus, Fτ=Pi(v)
U=u0,ui is the revenue set of rational users. Among them, u0∈U+−,U−,U−−,U−−− is the revenue function of the rational requesting user P0, and ui∈W+−,W−,W−−,Wf−,W−−− is the revenue function of the rational cooperative user Pi
Based on the formal description of the anonymity zone cooperative construction game model, the security definition of distributedk-anonymity is given below.Definition 2 (Security of distributedk-anonymous location privacy protection).
Suppose thatP0 is a rational requesting user and P1,P2,⋯,PK−1 is K−1 rational cooperative users. When the rational user P0 uses the distributed k-anonymous privacy protection scheme to send a cooperative anonymous area request to P1,P2,⋯,PK−1, and there is successful construction of the anonymous area ACR, the following conditions are true:
(1)u0=U−,ui=W,−PrLSPLoc0real∣ACR⩽1K.Then, the distributedk-anonymous location privacy protection scheme is called secure. Here, K represents the location privacy protection requirement of the requesting user P0 when sending the current LBS query. Here, 1⩽i⩽k−1. PrLSPLoc0realACR represents the probability that LSP can correctly identify its real location Loc0real from the anonymous area ACR submitted by the requesting userP0.In the above definitions, formula (1) defines the security of the distributed k-anonymous location privacy protection from the perspective of anonymous region construction. Formula (1) indicates that the requesting user P0 will not disclose the location of the cooperative user during the construction of the anonymous area. Formula (1) indicates that during the construction of the anonymous area, cooperative user Pi provides its own real location Loc0real to the requesting user P0. Formula (1) defines the security of the distributed k-anonymous location privacy protection from the perspective of the LBS query.


## 4. Research Design

To prevent the requesting users from divulging the locations of cooperative users and providing false locations to cheat the requesting users during the construction of a distributed anonymous area, in this paper, encryption and signature techniques are used to prevent other users from illegally obtaining the location information provided by cooperative users and from participating in anonymous area construction that deny users who have location deception or disclosure behavior. Blockchain is used for distributed storage, and both sides of the game involved in the construction of the anonymity zone and the location information provided by them are used as evidence; hence, a distributedk-anonymous location privacy protection scheme is designed.


### 4.1. Consensus Mechanism

To prevent the requesting users from divulging the location information of cooperative users and providing false locations to cheat the requesting users during the construction of a distributed anonymous area, this section first designs a collaboration request recording mechanism to constrain the self-interest behavior of the requesting user and the collaborative user and also proposes a blockchain accounting competition mechanism to encourage all users in the network to participate in the maintenance of the blockchain.Suppose that in anyq-th anonymous region cooperative construction game, policy a0q_1 means that the requesting user P0 will not disclose the location Lociq provided by cooperative user Pi to the third party after receiving it. Policy a0q_2 means that the requesting user P0 will disclose the location Lociq provided by the cooperative user Pi to the third party after receiving it.Policyaiq_1 means that the cooperative user Pi provides the real location Locireal to the requesting user P0 after receiving the collaboration request. Policy aiq_2 means that the cooperative user Pi does not provide any location information to the requesting user P0 after receiving the collaboration request. Policy aiq_3 indicates that the cooperative user Pi provides a false location Locifake to the requesting user P0 after receiving the cooperation request. Let u0q and uiq represent the profits of the requesting user P0 and the cooperating user Pi at the end of the q-th anonymous region cooperative construction game, respectively. Moreover, the strategy a0⟶0q+j represents the strategy chosen by the requester P0 of the q-th anonymous zone cooperative construction game when he is still the requester in the j-th game. The strategy ai⟶0q+j represents the strategy chosen by the cooperative user Pi, who participates in the q-th anonymous zone cooperative construction game as the requester in the j-th game. Then, the collaboration request recording mechanism proposed in this paper is as follows:Definition 3 (Consensus mechanism I-interactive recording mechanism).
The interactive record mechanismMR=aq,pq−+m is a two-tuple. Among them, we have the following:
(i)
aq=a0q,aiq is a combination of strategies (a0q and aiq) selected by the requesting user P0 and the cooperating user Pi in the q-th anonymous region cooperative construction game(ii)
pq−+m=p0q−+m,piq−+m is the interactive record mechanism MR, according to the strategy chosen by the requesting user P0 and the cooperative user Pi in the q-th anonymous area collaborative construction game, and it gives them the payment income from the q-th anonymous area collaborative construction game to the q+m-th anonymous area collaborative construction game GACRq−+m.For any j∈q−,q−+m, it satisfies the following:(2)p0j=u0ja0⟶0j,ai′j_1,a0q=a0q_1,u0ja0⟶0j,ai′j_2,a0q=a0q_2,pij=ui⟶0jai⟶0j,ai′j_1,aiq=aiq_1,ui⟶0jai⟶0j,ai′jλi⟶0,δi′,aiq=aiq_2,ui⟶0jai⟶0j,ai′j_2,aiq=aiq_3.Among them,m is the number of penalty rounds, ai′j represents the cooperative user Pi′ selection strategy in the anonymous zone cooperative construction game GACRj, λi⟶0 is the number of times that the cooperative users Pi who participate in the anonymous zone cooperative construction game GACRq assist other users in constructing the anonymous area when they participate in game GACRj, and δi′ is the judgment threshold of cooperative users Pi′ in the anonymous zone cooperative construction game GACRj. When λi⟶0<δi′, ai′jλi⟶0,δi′=ai′j_2; otherwise, ai′jλi⟶0,δi′=ai′j_1. Interactive recording mechanism MR refers to using the requesting users, cooperative users, and location information provided by them to restrict their self-interest behavior. In other words, in the anonymous region collaborative construction game GACRq, once it is found that the requesting user P0 divulges the location information of the cooperative user, and then there will be no user to help him construct an anonymous area in the subsequent m-times service queries. Similarly, in the anonymous region collaborative construction game GACRq, if the cooperative user Pi provides a false location, then the cooperative user will not have other users to help him construct the anonymous area in the subsequent m-times of service queries.In the scheme proposed in this paper, the researcher uses blockchain distributed storage, with the requesting user, collaborative user, and location information, as evidence. Therefore, to encourage all users in the network to participate in the maintenance of the blockchain, this paper also proposes a block chain accounting rights competition mechanism.Definition 4 (Consensus mechanism II-accounting rights competition mechanism).
Accounting rights competition mechanismMC=λ−,p− is a two-tuple. Among them, we have the following:
(i)
λ−=λ1−,λ2−,⋯,λn− is the set of times λ1−,λ2−,⋯,λn− that users p1−,p2−,⋯,pn− who participate in the competition to obtain accounting rights help other users to construct an anonymous area in the competitive production of the new block blockM.Here, λi− is the number of times that the i−-th users pi− history, which participates in the generation of accounting rights in the new block, and helps other users to construct anonymous zones(ii)
p−=p1−−,p2−−,⋯,pn−− is the revenue when the new block is generated (users p1−,p2−,⋯,pn− who participate in the competition of the new block generation bookkeeping rights help other users to construct anonymous areas in history). For any pi−∈p−, the following conditions are satisfied:(3)P¯i¯=0,otherλi¯+1,λi¯=argmaxλi′¯modλmaxM−1.Among them,λmaxM−1 represents the number of times i′−∈1−,2−,⋯,n− that the user who has obtained the accounting rights of the generated block blockM−1 has helped other users to construct an anonymous zone at that time.In short, the basic idea of the new block accounting rights competition mechanismMC proposed in this paper is to allow the users who participate in the anonymous zone construction for the largest number of times obtain the accounting rights. However, to prevent the users who participate in the anonymous zone construction for the largest number of times from always obtaining the accounting permission, and thus have the opportunity to forge the distributed anonymous area collaborative construction blockchain, this paper uses λi−=argmaxλi′−modλmaxM−1 to make the accounting rights of the blockchain disperse to each user in the network. In addition, to encourage all users in the network to participate in the updating of the blockchain, this paper regards the accounting rights of generating new blocks as a special way to participate in the construction of an anonymous area. Obviously, for any user pi− in the network, the larger that λi− is, the more help to other users in constructing anonymous areas. Then, when pi− as a requester sends an anonymous area collaborative construction request, the larger the number of users who provide their location information to him is, and the greater the probability that RR can successfully construct an anonymous area. This approach can also prevent users from using new cID frequently in the blockchain system to a certain extent.It is worthwhile to note that in the accounting rights, competition mechanism proposed in this paper, any user in the network, including the requesting user who sends the anonymous zone collaborative construction request, the collaborative user who provides the location information, and the other users who receive the anonymous zone collaborative construction request without providing the location information, can participate in the competition of generating the new block accounting rights.


### 4.2. Specific Scheme

In this paper, the process of requesting users to obtain the real location of collaborative users is regarded as a special kind of transaction. TheIDs of both parties and the location information provided by cooperative users are recorded in the transaction bill, and the bill is stored in the public chain. When the requesting user indicates that the cooperative user provides a false location or the cooperative user indicates that the requesting user discloses his location, the transaction bill can be used as a voucher for arbitration. Once the location disclosure or spoofing behavior is confirmed, the user who has the above behavior will not be helped by other users when they are the requester, which makes them unable to construct an anonymous area successfully. In addition, to encourage network users to participate in the maintenance of the blockchain, users who generate blocks each time are regarded as helping users to construct anonymous zones. The specific scheme is as follows:Step 1.
The requesting user sends an anonymous zone construction collaboration request to the cooperative user.(4)Req=T0−i,cID0,λ0,NTranl1,NTranl2,⋯,NTranλ0,signSK−cID0λ0T0−i.Among them,T0⟶i represents the timestamp when the requesting user P0 sends an anonymous zone construction collaboration request. Additionally, cID0 is the pseudonym used by the requesting user P0 in the blockchain system, and λ0 represents the number of times that the requesting user has participated in the anonymous zone construction when he is a cooperative user. NTranlk represents the bill number of the transaction bill Tranlk, which stores the request of user P0 to cooperate with other users to construct the anonymous zone. Here, 1⩽k⩽λ0, SK−cID0, is the private key of the requesting user in the blockchain system. signSK−cID0λ0T0−i means signing λ0T0−i with private key SK−cID0 and “‖” is the connection symbol.Step 2.
After receiving the anonymous area construction request sent by the requesting user, the cooperative userPii≠0 first counts the number of times λ0′ that the requesting user has participated in the anonymous area construction in the distributed anonymous area collaborative construction blockchain Blockchain=Block1,Block2,⋯,BlockM−1 and determines whether there is a penalty transaction bill recording the cheating behavior of the requesting user P0 in the blockchain.
(1)
Whenλ0′=λ0 and no penalty transaction bill is found to record the cheating behavior of the current requesting user P0, the cooperative user Pi decides whether to send his real location Locireal to the requesting user according to the threshold value δi(i)
Ifλ0<δi, the collaboration user Pi does not respond to the collaboration request of the requesting user P0(ii)
Ifλ0⩽δi, the cooperative user Pi sends the transaction bill to the requesting user P0(5)Tran=Ti−0,cID0,EncPK−cID0LocirealTi−0,signSK−cIDiEncPK−cID0LocirealTi−0.(2)
Whenλ0′=λ0, but the penalty transaction bill recording the cheating behavior of the current requesting user P0 is found in the block Blockl′, the cooperative user Pi judges whether the requesting user P0 is still in the penalty period according to the number of current blocks(i)
IfM−1−l′⩽m, in other words, the requesting user P0 is still in the penalty period, the cooperative user Pi does not respond to the request of the requesting user P0, and the penalty transaction bill is broadcast:(6)Tranpun=Ti−0,cID0,cIDi,Punishment,signSK−cIDipunishmentTi−0.(ii)
IfM−1−l′>m, in other words, the requesting user P0 has been punished, and the cooperative user Pi will send the transaction bill Tran to the requesting user P0(3)
Whenλ0′≠λ0, the cooperative user Pi does not respond to the request of the requesting user P0, and the penalty transaction bill is broadcast:(7)Tranpun=Ti−0,cID0,cIDi,Punishment,signSK−cIDipunishmentTi−0,T0−i,λ0,signSK−cID0λ0T0−i.M represents the number of blocks in the distributed anonymous zone collaborative construction blockchain when the requesting user P0 sends the cooperation request. Here, l′ represents the block number of the recorded requesting user P0′s spoofing behavior, which satisfies 1⩽l′⩽M−1. Ti−0 represents the timestamp that generated the transaction bill and is the penalty threshold. PK−cID0 is the public key of the requesting user P0 in the blockchain system. SK−cIDi is the private key of the cooperative users Pi in the blockchain system. Punish−ment is the identifier of the penalty transaction bill. EncPK−cID0LocirealTi−0 represents the ciphertext obtained by encrypting LocirealTi−0 with the public key PK−cID0 of the requesting user P0 in the blockchain system.Step 3.
After receiving the transaction billTran sent by the cooperative user Pi, requesting user P0 uses the public key PK−cIDi of the cooperative user Pi in the blockchain system to verify the correctness of the signature information.
(8)signSK−cIDiEncPK−cID0LocirealTi−0.(1)
If the verification is successful, then requesting userP0 decrypts EncPK−cID0LocirealTi−0 with his private key SK−cID0 to obtain the real location Locireal of the cooperative user Pi.Then, EncPK−cIDiLocirealTi−0 and signSK−cID0EncPK−cIDiLocirealTi−0 are calculated and written into the transaction bill Tran for broadcasting(2)
If the verification fails, thenLocireal is not used to construct the anonymous area ACR, and the penalty transaction bill is broadcast(9)Tranpun=Ti−0,cID0,cIDi,Punishment,signSK−cID0punishmentTi−0,EncPK−cID0LocirealTi−0,signSK−cIDiEncPK−cID0LocirealTi−0.The anonymous region can be constructed successfully when the requesting user obtains the real location provided by no less thanK−1 cooperative users.Step 4.
All of the users in the network verify their authenticity after receiving the transaction bill sent by the broadcast. If the verification fails, then new penalty transaction bills are generated and broadcast. If the verification is passed, the transaction bill is saved to generate a new blockBlockM. When the distributed anonymous zone is to be updated to construct the blockchain cooperatively, if
(10)λjM=argmaxλi′modλmaxM−1, then the user Pj obtains the accounting rights and joins the new block BlockM into the distributed anonymous area to construct the blockchain cooperatively.In the above scheme, the user’scID will be used as an index to retrieve all of the historical transaction bills that contain the cID in the blockchain system, in such a way that each user in the network can trace the historical behavior of the requesting user and the cooperative user. In addition, when the “requesting user” uses the above scheme to protect his location privacy during an LBS query, the following three situations could occur:
(1)
When the requesting user makes multipleLBS queries in the same location, the user does not need to broadcast and send the construction anonymous area cooperation request. Only by looking up the transaction bills stored in the blockchain can it quickly obtain the real location provided by the collaborative users in the historical query, to construct the anonymous area efficiently and improve the quality of service(2)
When the requesting user makes a continuousLBS query, the user does not need to send a request to construct an anonymous zone. At this time, by querying the transaction bills stored in the blockchain, it can quickly obtain the users who cooperated in the last query and then directly send the cooperation request to these users, quickly construct the anonymous area, and improve the quality of service(3)
When a new block is generated, if there are multiple usersPj1,Pj2,⋯,Pjn, we let(11)λj1M=λj2M=⋯=λjnM=argmaxλi′modλmaxM−1hold. The users in the network decide which user in Pj1,Pj2,⋯,Pjn gets the bookkeeping rights of this blockchain by voting. In addition, to reduce the networks user query overhead, in practical applications, we can introduce a sliding window mechanism in the above scheme to reduce the number of blocks that store transaction bills in the blockchain.In addition, if the location privacy data update frequency is much higher than the transaction speed in the public chain network when using the scheme in practice, the scheme can be optimized by using methods such as region division and alliance chain technology.


### 4.3. Scheme Analysis

#### 4.3.1. Security Certification

This paper assumes that there are at leastK−1 users Pi1⩽i⩽K−1 with the threshold δi⩽λ0 in the network. The requesting user P0 can successfully construct an anonymous area ACR that contains the location provided by the other K−1 cooperative users. Moreover, it is also assumed that if the requesting user P0 receives the real locations Loc1real,Loc2real,⋯,LocK−1real provided by the K−1 users, the anonymous area construction method Area· adopted by the user is secure; in other words, equation (12) holds.
(12)PrLSPLoc0real∣AreaLoc0real,Loc1real,⋯,LocK−1real⩽1K.Therefore, this paper proves only that the scheme is secure from the perspective of anonymous region construction.Lemma 5.
Letα denote the probability that the cooperative user Pi can correctly identify the location disclosure behavior of the requesting user P0 and let β represent the probability that the requesting user P0 identifies the false location provided by the cooperative user Pi. When the threshold δi⩽λ0 of K−1 users exists in the network, if m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, then the scheme is able to not only prevent the requesting users P0 from disclosing the location information of the cooperative users Pi1⩽i⩽K−1 but also ensure that the cooperative users Pi provide the real locations Locireal when participating in the distributed anonymous construction.Proof.
Proof by contradiction.
Suppose that when the threshold value of rational userPi is δi⩽λ0 and m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, the requesting user P0 will disclose the real location Lociq−real to the third party after receiving the rational user Pi’s real location in any q-th anonymous area cooperative construction game, in other words, the selection strategy a0q_2. At this time, for the requesting user P0, his profit in the game GACRq is as follows:
(13)u0a0q_2=U+−.When the rational cooperative userPi confirms that P0 has ever disclosed his real location Lociq_real, P0 still acts as the requester in the ai2 anonymous area cooperative construction game GACRq¯, GACRq¯+1, ⋯,GACRq¯+m after that time, and the revenue satisfies the following:
(14)u0q¯+ja0q¯+ja0q_2=U−−,for 1⩽j⩽m.Therefore, the total revenue of rational user P0 for the selection strategy a0q_2 in the (m+1)-time game GACRq,GACRq¯, GACRq¯+1,⋯,GACRq¯+m is as follows:
(15)u¯0a0q_2=α·u0a0q_2+1−α·u0a0q¯a0q_2+u0a0q¯+1a0q_2+⋯+u0a0q¯+ma0q_2=U−+mU−+α·m·U−−−−U−However, if the requesting userP0 does not disclose the real location to the third party after receiving the real location GACRq¯,GACRq¯+1,⋯,GACRq¯+m in the aiq_1-th anonymous area cooperative construction game, in other words, when selecting the strategy a0q_1, the overall revenue of the user in the anonymous area cooperative construction game GACRq and GACRq¯,GACRq¯+1,⋯,GACRq¯+m is as follows:
(16)u¯0a0q_1=u0a0q_1+u0a0q¯a0q_1+u0a0q¯+1a0q_1+⋯+u0a0q¯+ma0q_1=U−+mU−.According to the hypothesis, if and only ifu¯0a0q_1⩽u¯0a0q−2, the requesting user will disclose the location information provided by the cooperative user. More specifically, the following
(17)U−+mU−⩽U+−+mU−+α·m·U−−−−U−holds. Then, m⩽α·U+−−U−/U−−U−−− contradicts the known m>α·U+−−U−/U−−U−−−. Therefore, for rational requesting users P0, it will not reveal the real location of the collaborative users Pi .In the same way, suppose that in any q-th anonymous cooperative construction game, when m>maxU+−−U−/α·U−−U−−−,1−β·W+−+W−/β·U−−U−−− and the cooperative user Pi1⩽i⩽K−1 decides to help the requesting user construct the anonymous area, the cooperative user Pi provides a false location Lociq_fake, in other words, the selection strategy aiq_3. At this time, the rational cooperative user Pi provides a false location Lociq_fake to the requesting user P0, and the probability of correct identification of the requesting user P0 is β. Therefore, after the cooperative user is proven to provide a false location in the current game GACRq, the total revenue of the cooperative users participating in the ai2-th anonymous zone cooperative construction game GACRq¯,GACRq¯+1,⋯,GACRq¯+m is as follows:
(18)u¯iaiq−3=β·uiaiq−3+1−β·ui⟶0a0q¯∣aiq3+ui⟶0a0q¯+1∣aiq3+⋯+ui⟶0a0q¯+m∣aiq3=1−β·W+−+β·Wf−+β·m·U−−−−U−.Among them, in the anonymous area collaborative construction gameGACRq, ui⟶0· represents the revenue function of the cooperative users as requesters in the subsequent collaborative construction game. When the cooperative user Pi decides to help the requesting user construct the anonymous area and provide the real location Locireal, in other words, to choose the strategy aiq_1, the total revenue in the game GACRq and GACRq¯,GACRq¯+1,⋯,GACRq¯+m is as follows:
(19)u¯iaiq_1=uiaiq_1+ui⟶0a0q¯+ui⟶0a0q¯+1+⋯+ui⟶0a0q¯+m=W−+mU−.According to the hypothesis, if and only ifu¯iaiq_1⩽u¯iaiq_3, the cooperative user Pi will provide a false location to the requesting user. In other words, W−+mU−⩽1−β·W+−+β·Wf−+β·m·U−−−−U− holds. Then, m<1−β·W+−−W−/β·U−−U−−− and m>1−β·W+−−W−/β·U−−U−−− are contradictory. Therefore, when the cooperative user decides to help the requesting user construct the anonymous zone, it will provide the real location.The proof is complete.Lemma 6.
Letα denote the probability that the cooperative user can correctly identify the location leakage behavior of the requesting user P0 . Here, β represents the probability that the requesting user P0 identifies the false location provided by the cooperative user. For any rational user Pi in the network, when δi⩽λ0 and m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, this scheme can encourage the user Pi to participate in the construction of the distributed anonymous area. From Lemma 5 and Lemma 6, the following can be concluded:
Letα denote the probability that the cooperative user can correctly identify the location leakage behavior of the requesting user P0. Here, β represents the probability that the requesting user P0 identifies the false location provided by the cooperative user. It is assumed that rational users P0 adopt this scheme to protect their location privacy during an LBS query, and there is a threshold δi⩽λ0 of K−1 other rational users Pi1⩽i⩽K−1 in the network. Here, λ0 represents the number of times in the history that rational requesting users P0 help other users to construct anonymous zones. If m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, the scheme is safe. In other words, this scheme is able to not only promote the cooperative users Pi1⩽i⩽K−1 to provide their real locations to the requesting users P0 but also prevent the requesting users P0 from divulging these locations. At the same time, the accuracy rate of the LSP in identifying the real location from the anonymous area submitted by the requesting user P0 is not higher than that of 1/K.


#### 4.3.2. Computational Complexity

This scheme involves encryption, decryption, and a signature operation. In this paper, the signature operation is regarded as a special encryption operation. Because the decryption operation is the inverse of the encryption operation,OEnc is used to represent the computational complexity of the encryption, decryption, and signature operations.In this scheme, when each cooperative userPi receives the anonymous region construction request sent by the requesting user P0, it first calculates according to the requesting user Pi’s public key PK−cID0, and it verifies the correctness of the signature data signSK−cID0λ0T0⟶i. At this time, the required computational complexity is OEnc. If the correctness is verified, then the cooperative user Pi will query the transaction bill stored in the blockchain Blockchain=Block1,Block2,⋯,BlockM−1, determine the authenticity of the number of times λ0 that requesting user P0 helped other users construct an anonymous area, and determine whether there is a penalty transaction bill from recording P0 cheating in the blockchain. When it is found that the requesting user P0 sends a false λ0 or it is still in the penalty period, the penalty transaction bill is broadcast after calculating the signSK−cIDiPunishmentTi−0. In this case, the computational complexity of is
(20)OM+OEnc=OEnc.Whenλ0 is verified to be correct and no penalty transaction bill is found to record the cheating behavior of the requesting user P0, then the cooperative user Pi decides whether to provide his own location to the requesting user P0 according to the threshold value δi. If λ0<δi, then it does not respond to the anonymous area construction request sent by the requesting user, and the computational cost is O1. If λ0⩽δi, then after calculating the EncPK−cID0LocirealTi−0 and the corresponding signature signSK−cIDiEncPK−cID0LocirealTi−0, the transaction bill is sent to the requesting user P0, and the computational complexity of the cooperative user Pi is
(21)O1+OEnc+OEnc=OEnc.Therefore, when an anonymous construction request is received, the upper limit of the computational complexity required by the cooperative userPi is as follows:
(22)OEnc+OEnc+OEnc=OEnc.In the same way, after receiving the transaction bill sent by the cooperative userPi, the computational complexity required by the requesting user is OEnc . When a new block is generated, the computational complexity of the users participating in the new block BlockM generation is OEnc.To summarize, if the user successfully obtains the real location provided byr⩽K−1 cooperative users, the computational complexity of each user in the network is as follows:
(1)
For the requesting user, the calculation complexity is as follows:(23)r·OEnc+OEnc=OEnc.(2)
For users who provide their own real location to construct the anonymous area, the computational complexity is as follows:(24)OEnc+OEnc+OEnc=OEnc.(3)
For the users who do not respond to the anonymous zone cooperative construction request, the computational complexity is as follows:(25)OEnc+O1+OEnc=OEnc.


## 4.1. Consensus Mechanism

To prevent the requesting users from divulging the location information of cooperative users and providing false locations to cheat the requesting users during the construction of a distributed anonymous area, this section first designs a collaboration request recording mechanism to constrain the self-interest behavior of the requesting user and the collaborative user and also proposes a blockchain accounting competition mechanism to encourage all users in the network to participate in the maintenance of the blockchain.Suppose that in anyq-th anonymous region cooperative construction game, policy a0q_1 means that the requesting user P0 will not disclose the location Lociq provided by cooperative user Pi to the third party after receiving it. Policy a0q_2 means that the requesting user P0 will disclose the location Lociq provided by the cooperative user Pi to the third party after receiving it.Policyaiq_1 means that the cooperative user Pi provides the real location Locireal to the requesting user P0 after receiving the collaboration request. Policy aiq_2 means that the cooperative user Pi does not provide any location information to the requesting user P0 after receiving the collaboration request. Policy aiq_3 indicates that the cooperative user Pi provides a false location Locifake to the requesting user P0 after receiving the cooperation request. Let u0q and uiq represent the profits of the requesting user P0 and the cooperating user Pi at the end of the q-th anonymous region cooperative construction game, respectively. Moreover, the strategy a0⟶0q+j represents the strategy chosen by the requester P0 of the q-th anonymous zone cooperative construction game when he is still the requester in the j-th game. The strategy ai⟶0q+j represents the strategy chosen by the cooperative user Pi, who participates in the q-th anonymous zone cooperative construction game as the requester in the j-th game. Then, the collaboration request recording mechanism proposed in this paper is as follows:Definition 3 (Consensus mechanism I-interactive recording mechanism).
The interactive record mechanismMR=aq,pq−+m is a two-tuple. Among them, we have the following:
(i)
aq=a0q,aiq is a combination of strategies (a0q and aiq) selected by the requesting user P0 and the cooperating user Pi in the q-th anonymous region cooperative construction game(ii)
pq−+m=p0q−+m,piq−+m is the interactive record mechanism MR, according to the strategy chosen by the requesting user P0 and the cooperative user Pi in the q-th anonymous area collaborative construction game, and it gives them the payment income from the q-th anonymous area collaborative construction game to the q+m-th anonymous area collaborative construction game GACRq−+m.For any j∈q−,q−+m, it satisfies the following:(2)p0j=u0ja0⟶0j,ai′j_1,a0q=a0q_1,u0ja0⟶0j,ai′j_2,a0q=a0q_2,pij=ui⟶0jai⟶0j,ai′j_1,aiq=aiq_1,ui⟶0jai⟶0j,ai′jλi⟶0,δi′,aiq=aiq_2,ui⟶0jai⟶0j,ai′j_2,aiq=aiq_3.Among them,m is the number of penalty rounds, ai′j represents the cooperative user Pi′ selection strategy in the anonymous zone cooperative construction game GACRj, λi⟶0 is the number of times that the cooperative users Pi who participate in the anonymous zone cooperative construction game GACRq assist other users in constructing the anonymous area when they participate in game GACRj, and δi′ is the judgment threshold of cooperative users Pi′ in the anonymous zone cooperative construction game GACRj. When λi⟶0<δi′, ai′jλi⟶0,δi′=ai′j_2; otherwise, ai′jλi⟶0,δi′=ai′j_1. Interactive recording mechanism MR refers to using the requesting users, cooperative users, and location information provided by them to restrict their self-interest behavior. In other words, in the anonymous region collaborative construction game GACRq, once it is found that the requesting user P0 divulges the location information of the cooperative user, and then there will be no user to help him construct an anonymous area in the subsequent m-times service queries. Similarly, in the anonymous region collaborative construction game GACRq, if the cooperative user Pi provides a false location, then the cooperative user will not have other users to help him construct the anonymous area in the subsequent m-times of service queries.In the scheme proposed in this paper, the researcher uses blockchain distributed storage, with the requesting user, collaborative user, and location information, as evidence. Therefore, to encourage all users in the network to participate in the maintenance of the blockchain, this paper also proposes a block chain accounting rights competition mechanism.Definition 4 (Consensus mechanism II-accounting rights competition mechanism).
Accounting rights competition mechanismMC=λ−,p− is a two-tuple. Among them, we have the following:
(i)
λ−=λ1−,λ2−,⋯,λn− is the set of times λ1−,λ2−,⋯,λn− that users p1−,p2−,⋯,pn− who participate in the competition to obtain accounting rights help other users to construct an anonymous area in the competitive production of the new block blockM.Here, λi− is the number of times that the i−-th users pi− history, which participates in the generation of accounting rights in the new block, and helps other users to construct anonymous zones(ii)
p−=p1−−,p2−−,⋯,pn−− is the revenue when the new block is generated (users p1−,p2−,⋯,pn− who participate in the competition of the new block generation bookkeeping rights help other users to construct anonymous areas in history). For any pi−∈p−, the following conditions are satisfied:(3)P¯i¯=0,otherλi¯+1,λi¯=argmaxλi′¯modλmaxM−1.Among them,λmaxM−1 represents the number of times i′−∈1−,2−,⋯,n− that the user who has obtained the accounting rights of the generated block blockM−1 has helped other users to construct an anonymous zone at that time.In short, the basic idea of the new block accounting rights competition mechanismMC proposed in this paper is to allow the users who participate in the anonymous zone construction for the largest number of times obtain the accounting rights. However, to prevent the users who participate in the anonymous zone construction for the largest number of times from always obtaining the accounting permission, and thus have the opportunity to forge the distributed anonymous area collaborative construction blockchain, this paper uses λi−=argmaxλi′−modλmaxM−1 to make the accounting rights of the blockchain disperse to each user in the network. In addition, to encourage all users in the network to participate in the updating of the blockchain, this paper regards the accounting rights of generating new blocks as a special way to participate in the construction of an anonymous area. Obviously, for any user pi− in the network, the larger that λi− is, the more help to other users in constructing anonymous areas. Then, when pi− as a requester sends an anonymous area collaborative construction request, the larger the number of users who provide their location information to him is, and the greater the probability that RR can successfully construct an anonymous area. This approach can also prevent users from using new cID frequently in the blockchain system to a certain extent.It is worthwhile to note that in the accounting rights, competition mechanism proposed in this paper, any user in the network, including the requesting user who sends the anonymous zone collaborative construction request, the collaborative user who provides the location information, and the other users who receive the anonymous zone collaborative construction request without providing the location information, can participate in the competition of generating the new block accounting rights.


## 4.2. Specific Scheme

In this paper, the process of requesting users to obtain the real location of collaborative users is regarded as a special kind of transaction. TheIDs of both parties and the location information provided by cooperative users are recorded in the transaction bill, and the bill is stored in the public chain. When the requesting user indicates that the cooperative user provides a false location or the cooperative user indicates that the requesting user discloses his location, the transaction bill can be used as a voucher for arbitration. Once the location disclosure or spoofing behavior is confirmed, the user who has the above behavior will not be helped by other users when they are the requester, which makes them unable to construct an anonymous area successfully. In addition, to encourage network users to participate in the maintenance of the blockchain, users who generate blocks each time are regarded as helping users to construct anonymous zones. The specific scheme is as follows:Step 1.
The requesting user sends an anonymous zone construction collaboration request to the cooperative user.(4)Req=T0−i,cID0,λ0,NTranl1,NTranl2,⋯,NTranλ0,signSK−cID0λ0T0−i.Among them,T0⟶i represents the timestamp when the requesting user P0 sends an anonymous zone construction collaboration request. Additionally, cID0 is the pseudonym used by the requesting user P0 in the blockchain system, and λ0 represents the number of times that the requesting user has participated in the anonymous zone construction when he is a cooperative user. NTranlk represents the bill number of the transaction bill Tranlk, which stores the request of user P0 to cooperate with other users to construct the anonymous zone. Here, 1⩽k⩽λ0, SK−cID0, is the private key of the requesting user in the blockchain system. signSK−cID0λ0T0−i means signing λ0T0−i with private key SK−cID0 and “‖” is the connection symbol.Step 2.
After receiving the anonymous area construction request sent by the requesting user, the cooperative userPii≠0 first counts the number of times λ0′ that the requesting user has participated in the anonymous area construction in the distributed anonymous area collaborative construction blockchain Blockchain=Block1,Block2,⋯,BlockM−1 and determines whether there is a penalty transaction bill recording the cheating behavior of the requesting user P0 in the blockchain.
(1)
Whenλ0′=λ0 and no penalty transaction bill is found to record the cheating behavior of the current requesting user P0, the cooperative user Pi decides whether to send his real location Locireal to the requesting user according to the threshold value δi(i)
Ifλ0<δi, the collaboration user Pi does not respond to the collaboration request of the requesting user P0(ii)
Ifλ0⩽δi, the cooperative user Pi sends the transaction bill to the requesting user P0(5)Tran=Ti−0,cID0,EncPK−cID0LocirealTi−0,signSK−cIDiEncPK−cID0LocirealTi−0.(2)
Whenλ0′=λ0, but the penalty transaction bill recording the cheating behavior of the current requesting user P0 is found in the block Blockl′, the cooperative user Pi judges whether the requesting user P0 is still in the penalty period according to the number of current blocks(i)
IfM−1−l′⩽m, in other words, the requesting user P0 is still in the penalty period, the cooperative user Pi does not respond to the request of the requesting user P0, and the penalty transaction bill is broadcast:(6)Tranpun=Ti−0,cID0,cIDi,Punishment,signSK−cIDipunishmentTi−0.(ii)
IfM−1−l′>m, in other words, the requesting user P0 has been punished, and the cooperative user Pi will send the transaction bill Tran to the requesting user P0(3)
Whenλ0′≠λ0, the cooperative user Pi does not respond to the request of the requesting user P0, and the penalty transaction bill is broadcast:(7)Tranpun=Ti−0,cID0,cIDi,Punishment,signSK−cIDipunishmentTi−0,T0−i,λ0,signSK−cID0λ0T0−i.M represents the number of blocks in the distributed anonymous zone collaborative construction blockchain when the requesting user P0 sends the cooperation request. Here, l′ represents the block number of the recorded requesting user P0′s spoofing behavior, which satisfies 1⩽l′⩽M−1. Ti−0 represents the timestamp that generated the transaction bill and is the penalty threshold. PK−cID0 is the public key of the requesting user P0 in the blockchain system. SK−cIDi is the private key of the cooperative users Pi in the blockchain system. Punish−ment is the identifier of the penalty transaction bill. EncPK−cID0LocirealTi−0 represents the ciphertext obtained by encrypting LocirealTi−0 with the public key PK−cID0 of the requesting user P0 in the blockchain system.Step 3.
After receiving the transaction billTran sent by the cooperative user Pi, requesting user P0 uses the public key PK−cIDi of the cooperative user Pi in the blockchain system to verify the correctness of the signature information.
(8)signSK−cIDiEncPK−cID0LocirealTi−0.(1)
If the verification is successful, then requesting userP0 decrypts EncPK−cID0LocirealTi−0 with his private key SK−cID0 to obtain the real location Locireal of the cooperative user Pi.Then, EncPK−cIDiLocirealTi−0 and signSK−cID0EncPK−cIDiLocirealTi−0 are calculated and written into the transaction bill Tran for broadcasting(2)
If the verification fails, thenLocireal is not used to construct the anonymous area ACR, and the penalty transaction bill is broadcast(9)Tranpun=Ti−0,cID0,cIDi,Punishment,signSK−cID0punishmentTi−0,EncPK−cID0LocirealTi−0,signSK−cIDiEncPK−cID0LocirealTi−0.The anonymous region can be constructed successfully when the requesting user obtains the real location provided by no less thanK−1 cooperative users.Step 4.
All of the users in the network verify their authenticity after receiving the transaction bill sent by the broadcast. If the verification fails, then new penalty transaction bills are generated and broadcast. If the verification is passed, the transaction bill is saved to generate a new blockBlockM. When the distributed anonymous zone is to be updated to construct the blockchain cooperatively, if
(10)λjM=argmaxλi′modλmaxM−1, then the user Pj obtains the accounting rights and joins the new block BlockM into the distributed anonymous area to construct the blockchain cooperatively.In the above scheme, the user’scID will be used as an index to retrieve all of the historical transaction bills that contain the cID in the blockchain system, in such a way that each user in the network can trace the historical behavior of the requesting user and the cooperative user. In addition, when the “requesting user” uses the above scheme to protect his location privacy during an LBS query, the following three situations could occur:
(1)
When the requesting user makes multipleLBS queries in the same location, the user does not need to broadcast and send the construction anonymous area cooperation request. Only by looking up the transaction bills stored in the blockchain can it quickly obtain the real location provided by the collaborative users in the historical query, to construct the anonymous area efficiently and improve the quality of service(2)
When the requesting user makes a continuousLBS query, the user does not need to send a request to construct an anonymous zone. At this time, by querying the transaction bills stored in the blockchain, it can quickly obtain the users who cooperated in the last query and then directly send the cooperation request to these users, quickly construct the anonymous area, and improve the quality of service(3)
When a new block is generated, if there are multiple usersPj1,Pj2,⋯,Pjn, we let(11)λj1M=λj2M=⋯=λjnM=argmaxλi′modλmaxM−1hold. The users in the network decide which user in Pj1,Pj2,⋯,Pjn gets the bookkeeping rights of this blockchain by voting. In addition, to reduce the networks user query overhead, in practical applications, we can introduce a sliding window mechanism in the above scheme to reduce the number of blocks that store transaction bills in the blockchain.In addition, if the location privacy data update frequency is much higher than the transaction speed in the public chain network when using the scheme in practice, the scheme can be optimized by using methods such as region division and alliance chain technology.


## 4.3. Scheme Analysis

### 4.3.1. Security Certification

This paper assumes that there are at leastK−1 users Pi1⩽i⩽K−1 with the threshold δi⩽λ0 in the network. The requesting user P0 can successfully construct an anonymous area ACR that contains the location provided by the other K−1 cooperative users. Moreover, it is also assumed that if the requesting user P0 receives the real locations Loc1real,Loc2real,⋯,LocK−1real provided by the K−1 users, the anonymous area construction method Area· adopted by the user is secure; in other words, equation (12) holds.
(12)PrLSPLoc0real∣AreaLoc0real,Loc1real,⋯,LocK−1real⩽1K.Therefore, this paper proves only that the scheme is secure from the perspective of anonymous region construction.Lemma 5.
Letα denote the probability that the cooperative user Pi can correctly identify the location disclosure behavior of the requesting user P0 and let β represent the probability that the requesting user P0 identifies the false location provided by the cooperative user Pi. When the threshold δi⩽λ0 of K−1 users exists in the network, if m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, then the scheme is able to not only prevent the requesting users P0 from disclosing the location information of the cooperative users Pi1⩽i⩽K−1 but also ensure that the cooperative users Pi provide the real locations Locireal when participating in the distributed anonymous construction.Proof.
Proof by contradiction.
Suppose that when the threshold value of rational userPi is δi⩽λ0 and m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, the requesting user P0 will disclose the real location Lociq−real to the third party after receiving the rational user Pi’s real location in any q-th anonymous area cooperative construction game, in other words, the selection strategy a0q_2. At this time, for the requesting user P0, his profit in the game GACRq is as follows:
(13)u0a0q_2=U+−.When the rational cooperative userPi confirms that P0 has ever disclosed his real location Lociq_real, P0 still acts as the requester in the ai2 anonymous area cooperative construction game GACRq¯, GACRq¯+1, ⋯,GACRq¯+m after that time, and the revenue satisfies the following:
(14)u0q¯+ja0q¯+ja0q_2=U−−,for 1⩽j⩽m.Therefore, the total revenue of rational user P0 for the selection strategy a0q_2 in the (m+1)-time game GACRq,GACRq¯, GACRq¯+1,⋯,GACRq¯+m is as follows:
(15)u¯0a0q_2=α·u0a0q_2+1−α·u0a0q¯a0q_2+u0a0q¯+1a0q_2+⋯+u0a0q¯+ma0q_2=U−+mU−+α·m·U−−−−U−However, if the requesting userP0 does not disclose the real location to the third party after receiving the real location GACRq¯,GACRq¯+1,⋯,GACRq¯+m in the aiq_1-th anonymous area cooperative construction game, in other words, when selecting the strategy a0q_1, the overall revenue of the user in the anonymous area cooperative construction game GACRq and GACRq¯,GACRq¯+1,⋯,GACRq¯+m is as follows:
(16)u¯0a0q_1=u0a0q_1+u0a0q¯a0q_1+u0a0q¯+1a0q_1+⋯+u0a0q¯+ma0q_1=U−+mU−.According to the hypothesis, if and only ifu¯0a0q_1⩽u¯0a0q−2, the requesting user will disclose the location information provided by the cooperative user. More specifically, the following
(17)U−+mU−⩽U+−+mU−+α·m·U−−−−U−holds. Then, m⩽α·U+−−U−/U−−U−−− contradicts the known m>α·U+−−U−/U−−U−−−. Therefore, for rational requesting users P0, it will not reveal the real location of the collaborative users Pi .In the same way, suppose that in any q-th anonymous cooperative construction game, when m>maxU+−−U−/α·U−−U−−−,1−β·W+−+W−/β·U−−U−−− and the cooperative user Pi1⩽i⩽K−1 decides to help the requesting user construct the anonymous area, the cooperative user Pi provides a false location Lociq_fake, in other words, the selection strategy aiq_3. At this time, the rational cooperative user Pi provides a false location Lociq_fake to the requesting user P0, and the probability of correct identification of the requesting user P0 is β. Therefore, after the cooperative user is proven to provide a false location in the current game GACRq, the total revenue of the cooperative users participating in the ai2-th anonymous zone cooperative construction game GACRq¯,GACRq¯+1,⋯,GACRq¯+m is as follows:
(18)u¯iaiq−3=β·uiaiq−3+1−β·ui⟶0a0q¯∣aiq3+ui⟶0a0q¯+1∣aiq3+⋯+ui⟶0a0q¯+m∣aiq3=1−β·W+−+β·Wf−+β·m·U−−−−U−.Among them, in the anonymous area collaborative construction gameGACRq, ui⟶0· represents the revenue function of the cooperative users as requesters in the subsequent collaborative construction game. When the cooperative user Pi decides to help the requesting user construct the anonymous area and provide the real location Locireal, in other words, to choose the strategy aiq_1, the total revenue in the game GACRq and GACRq¯,GACRq¯+1,⋯,GACRq¯+m is as follows:
(19)u¯iaiq_1=uiaiq_1+ui⟶0a0q¯+ui⟶0a0q¯+1+⋯+ui⟶0a0q¯+m=W−+mU−.According to the hypothesis, if and only ifu¯iaiq_1⩽u¯iaiq_3, the cooperative user Pi will provide a false location to the requesting user. In other words, W−+mU−⩽1−β·W+−+β·Wf−+β·m·U−−−−U− holds. Then, m<1−β·W+−−W−/β·U−−U−−− and m>1−β·W+−−W−/β·U−−U−−− are contradictory. Therefore, when the cooperative user decides to help the requesting user construct the anonymous zone, it will provide the real location.The proof is complete.Lemma 6.
Letα denote the probability that the cooperative user can correctly identify the location leakage behavior of the requesting user P0 . Here, β represents the probability that the requesting user P0 identifies the false location provided by the cooperative user. For any rational user Pi in the network, when δi⩽λ0 and m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, this scheme can encourage the user Pi to participate in the construction of the distributed anonymous area. From Lemma 5 and Lemma 6, the following can be concluded:
Letα denote the probability that the cooperative user can correctly identify the location leakage behavior of the requesting user P0. Here, β represents the probability that the requesting user P0 identifies the false location provided by the cooperative user. It is assumed that rational users P0 adopt this scheme to protect their location privacy during an LBS query, and there is a threshold δi⩽λ0 of K−1 other rational users Pi1⩽i⩽K−1 in the network. Here, λ0 represents the number of times in the history that rational requesting users P0 help other users to construct anonymous zones. If m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, the scheme is safe. In other words, this scheme is able to not only promote the cooperative users Pi1⩽i⩽K−1 to provide their real locations to the requesting users P0 but also prevent the requesting users P0 from divulging these locations. At the same time, the accuracy rate of the LSP in identifying the real location from the anonymous area submitted by the requesting user P0 is not higher than that of 1/K.


### 4.3.2. Computational Complexity

This scheme involves encryption, decryption, and a signature operation. In this paper, the signature operation is regarded as a special encryption operation. Because the decryption operation is the inverse of the encryption operation,OEnc is used to represent the computational complexity of the encryption, decryption, and signature operations.In this scheme, when each cooperative userPi receives the anonymous region construction request sent by the requesting user P0, it first calculates according to the requesting user Pi’s public key PK−cID0, and it verifies the correctness of the signature data signSK−cID0λ0T0⟶i. At this time, the required computational complexity is OEnc. If the correctness is verified, then the cooperative user Pi will query the transaction bill stored in the blockchain Blockchain=Block1,Block2,⋯,BlockM−1, determine the authenticity of the number of times λ0 that requesting user P0 helped other users construct an anonymous area, and determine whether there is a penalty transaction bill from recording P0 cheating in the blockchain. When it is found that the requesting user P0 sends a false λ0 or it is still in the penalty period, the penalty transaction bill is broadcast after calculating the signSK−cIDiPunishmentTi−0. In this case, the computational complexity of is
(20)OM+OEnc=OEnc.Whenλ0 is verified to be correct and no penalty transaction bill is found to record the cheating behavior of the requesting user P0, then the cooperative user Pi decides whether to provide his own location to the requesting user P0 according to the threshold value δi. If λ0<δi, then it does not respond to the anonymous area construction request sent by the requesting user, and the computational cost is O1. If λ0⩽δi, then after calculating the EncPK−cID0LocirealTi−0 and the corresponding signature signSK−cIDiEncPK−cID0LocirealTi−0, the transaction bill is sent to the requesting user P0, and the computational complexity of the cooperative user Pi is
(21)O1+OEnc+OEnc=OEnc.Therefore, when an anonymous construction request is received, the upper limit of the computational complexity required by the cooperative userPi is as follows:
(22)OEnc+OEnc+OEnc=OEnc.In the same way, after receiving the transaction bill sent by the cooperative userPi, the computational complexity required by the requesting user is OEnc . When a new block is generated, the computational complexity of the users participating in the new block BlockM generation is OEnc.To summarize, if the user successfully obtains the real location provided byr⩽K−1 cooperative users, the computational complexity of each user in the network is as follows:
(1)
For the requesting user, the calculation complexity is as follows:(23)r·OEnc+OEnc=OEnc.(2)
For users who provide their own real location to construct the anonymous area, the computational complexity is as follows:(24)OEnc+OEnc+OEnc=OEnc.(3)
For the users who do not respond to the anonymous zone cooperative construction request, the computational complexity is as follows:(25)OEnc+O1+OEnc=OEnc.


## 4.3.1. Security Certification

This paper assumes that there are at leastK−1 users Pi1⩽i⩽K−1 with the threshold δi⩽λ0 in the network. The requesting user P0 can successfully construct an anonymous area ACR that contains the location provided by the other K−1 cooperative users. Moreover, it is also assumed that if the requesting user P0 receives the real locations Loc1real,Loc2real,⋯,LocK−1real provided by the K−1 users, the anonymous area construction method Area· adopted by the user is secure; in other words, equation (12) holds.
(12)PrLSPLoc0real∣AreaLoc0real,Loc1real,⋯,LocK−1real⩽1K.Therefore, this paper proves only that the scheme is secure from the perspective of anonymous region construction.Lemma 5.
Letα denote the probability that the cooperative user Pi can correctly identify the location disclosure behavior of the requesting user P0 and let β represent the probability that the requesting user P0 identifies the false location provided by the cooperative user Pi. When the threshold δi⩽λ0 of K−1 users exists in the network, if m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, then the scheme is able to not only prevent the requesting users P0 from disclosing the location information of the cooperative users Pi1⩽i⩽K−1 but also ensure that the cooperative users Pi provide the real locations Locireal when participating in the distributed anonymous construction.Proof.
Proof by contradiction.
Suppose that when the threshold value of rational userPi is δi⩽λ0 and m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, the requesting user P0 will disclose the real location Lociq−real to the third party after receiving the rational user Pi’s real location in any q-th anonymous area cooperative construction game, in other words, the selection strategy a0q_2. At this time, for the requesting user P0, his profit in the game GACRq is as follows:
(13)u0a0q_2=U+−.When the rational cooperative userPi confirms that P0 has ever disclosed his real location Lociq_real, P0 still acts as the requester in the ai2 anonymous area cooperative construction game GACRq¯, GACRq¯+1, ⋯,GACRq¯+m after that time, and the revenue satisfies the following:
(14)u0q¯+ja0q¯+ja0q_2=U−−,for 1⩽j⩽m.Therefore, the total revenue of rational user P0 for the selection strategy a0q_2 in the (m+1)-time game GACRq,GACRq¯, GACRq¯+1,⋯,GACRq¯+m is as follows:
(15)u¯0a0q_2=α·u0a0q_2+1−α·u0a0q¯a0q_2+u0a0q¯+1a0q_2+⋯+u0a0q¯+ma0q_2=U−+mU−+α·m·U−−−−U−However, if the requesting userP0 does not disclose the real location to the third party after receiving the real location GACRq¯,GACRq¯+1,⋯,GACRq¯+m in the aiq_1-th anonymous area cooperative construction game, in other words, when selecting the strategy a0q_1, the overall revenue of the user in the anonymous area cooperative construction game GACRq and GACRq¯,GACRq¯+1,⋯,GACRq¯+m is as follows:
(16)u¯0a0q_1=u0a0q_1+u0a0q¯a0q_1+u0a0q¯+1a0q_1+⋯+u0a0q¯+ma0q_1=U−+mU−.According to the hypothesis, if and only ifu¯0a0q_1⩽u¯0a0q−2, the requesting user will disclose the location information provided by the cooperative user. More specifically, the following
(17)U−+mU−⩽U+−+mU−+α·m·U−−−−U−holds. Then, m⩽α·U+−−U−/U−−U−−− contradicts the known m>α·U+−−U−/U−−U−−−. Therefore, for rational requesting users P0, it will not reveal the real location of the collaborative users Pi .In the same way, suppose that in any q-th anonymous cooperative construction game, when m>maxU+−−U−/α·U−−U−−−,1−β·W+−+W−/β·U−−U−−− and the cooperative user Pi1⩽i⩽K−1 decides to help the requesting user construct the anonymous area, the cooperative user Pi provides a false location Lociq_fake, in other words, the selection strategy aiq_3. At this time, the rational cooperative user Pi provides a false location Lociq_fake to the requesting user P0, and the probability of correct identification of the requesting user P0 is β. Therefore, after the cooperative user is proven to provide a false location in the current game GACRq, the total revenue of the cooperative users participating in the ai2-th anonymous zone cooperative construction game GACRq¯,GACRq¯+1,⋯,GACRq¯+m is as follows:
(18)u¯iaiq−3=β·uiaiq−3+1−β·ui⟶0a0q¯∣aiq3+ui⟶0a0q¯+1∣aiq3+⋯+ui⟶0a0q¯+m∣aiq3=1−β·W+−+β·Wf−+β·m·U−−−−U−.Among them, in the anonymous area collaborative construction gameGACRq, ui⟶0· represents the revenue function of the cooperative users as requesters in the subsequent collaborative construction game. When the cooperative user Pi decides to help the requesting user construct the anonymous area and provide the real location Locireal, in other words, to choose the strategy aiq_1, the total revenue in the game GACRq and GACRq¯,GACRq¯+1,⋯,GACRq¯+m is as follows:
(19)u¯iaiq_1=uiaiq_1+ui⟶0a0q¯+ui⟶0a0q¯+1+⋯+ui⟶0a0q¯+m=W−+mU−.According to the hypothesis, if and only ifu¯iaiq_1⩽u¯iaiq_3, the cooperative user Pi will provide a false location to the requesting user. In other words, W−+mU−⩽1−β·W+−+β·Wf−+β·m·U−−−−U− holds. Then, m<1−β·W+−−W−/β·U−−U−−− and m>1−β·W+−−W−/β·U−−U−−− are contradictory. Therefore, when the cooperative user decides to help the requesting user construct the anonymous zone, it will provide the real location.The proof is complete.Lemma 6.
Letα denote the probability that the cooperative user can correctly identify the location leakage behavior of the requesting user P0 . Here, β represents the probability that the requesting user P0 identifies the false location provided by the cooperative user. For any rational user Pi in the network, when δi⩽λ0 and m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, this scheme can encourage the user Pi to participate in the construction of the distributed anonymous area. From Lemma 5 and Lemma 6, the following can be concluded:
Letα denote the probability that the cooperative user can correctly identify the location leakage behavior of the requesting user P0. Here, β represents the probability that the requesting user P0 identifies the false location provided by the cooperative user. It is assumed that rational users P0 adopt this scheme to protect their location privacy during an LBS query, and there is a threshold δi⩽λ0 of K−1 other rational users Pi1⩽i⩽K−1 in the network. Here, λ0 represents the number of times in the history that rational requesting users P0 help other users to construct anonymous zones. If m>maxU+−−U−/α·U−−U−−−,1−β·W+−−W−/β·U−−U−−−, the scheme is safe. In other words, this scheme is able to not only promote the cooperative users Pi1⩽i⩽K−1 to provide their real locations to the requesting users P0 but also prevent the requesting users P0 from divulging these locations. At the same time, the accuracy rate of the LSP in identifying the real location from the anonymous area submitted by the requesting user P0 is not higher than that of 1/K.


## 4.3.2. Computational Complexity

This scheme involves encryption, decryption, and a signature operation. In this paper, the signature operation is regarded as a special encryption operation. Because the decryption operation is the inverse of the encryption operation,OEnc is used to represent the computational complexity of the encryption, decryption, and signature operations.In this scheme, when each cooperative userPi receives the anonymous region construction request sent by the requesting user P0, it first calculates according to the requesting user Pi’s public key PK−cID0, and it verifies the correctness of the signature data signSK−cID0λ0T0⟶i. At this time, the required computational complexity is OEnc. If the correctness is verified, then the cooperative user Pi will query the transaction bill stored in the blockchain Blockchain=Block1,Block2,⋯,BlockM−1, determine the authenticity of the number of times λ0 that requesting user P0 helped other users construct an anonymous area, and determine whether there is a penalty transaction bill from recording P0 cheating in the blockchain. When it is found that the requesting user P0 sends a false λ0 or it is still in the penalty period, the penalty transaction bill is broadcast after calculating the signSK−cIDiPunishmentTi−0. In this case, the computational complexity of is
(20)OM+OEnc=OEnc.Whenλ0 is verified to be correct and no penalty transaction bill is found to record the cheating behavior of the requesting user P0, then the cooperative user Pi decides whether to provide his own location to the requesting user P0 according to the threshold value δi. If λ0<δi, then it does not respond to the anonymous area construction request sent by the requesting user, and the computational cost is O1. If λ0⩽δi, then after calculating the EncPK−cID0LocirealTi−0 and the corresponding signature signSK−cIDiEncPK−cID0LocirealTi−0, the transaction bill is sent to the requesting user P0, and the computational complexity of the cooperative user Pi is
(21)O1+OEnc+OEnc=OEnc.Therefore, when an anonymous construction request is received, the upper limit of the computational complexity required by the cooperative userPi is as follows:
(22)OEnc+OEnc+OEnc=OEnc.In the same way, after receiving the transaction bill sent by the cooperative userPi, the computational complexity required by the requesting user is OEnc . When a new block is generated, the computational complexity of the users participating in the new block BlockM generation is OEnc.To summarize, if the user successfully obtains the real location provided byr⩽K−1 cooperative users, the computational complexity of each user in the network is as follows:
(1)
For the requesting user, the calculation complexity is as follows:(23)r·OEnc+OEnc=OEnc.(2)
For users who provide their own real location to construct the anonymous area, the computational complexity is as follows:(24)OEnc+OEnc+OEnc=OEnc.(3)
For the users who do not respond to the anonymous zone cooperative construction request, the computational complexity is as follows:(25)OEnc+O1+OEnc=OEnc.


## 5. Experiment

To test the effectiveness of the proposed scheme, the computational cost and communication overhead are examined. The experimental environment configuration is shown in Table1.Table 1
The configuration of the experimental environment.
NameParameterRemarksCPUIntel(R) CoreTM i5-2400 @ 3.10 GHZMemoryDDR3 1333/1600 MHz,4G8McacheI/OReadHarddisk256 GB PCIe×4 NVMe SSD-ing speed 2 MNetworkGuangxi telecomOperating−systemUbuntu 17.10Blockchain−platformEthereum 1.5.5NothingEncryption−modeOpenSSL-1.0.0c,256Bit, ECCPrograming−languageJAVAIn the blockchain network, there are 25 network nodes: one is the requesting userP0 node, and the other 24 are the cooperative user P1,P2,⋯,P24 nodes. By generating random numbers, the number of times λ0 that the requesting user’s P0 node has participated in the construction of an anonymous area and the thresholds δ1,δ2,⋯,δ24 of the cooperative user nodes are generated in such a way that there are at least K−1 cooperative users Pi1,Pi2,⋯,PiK−1 with thresholds δi1,δi2,⋯,δiK−1⩽λ0. In other words, after sending an anonymous region to construct a cooperative request, the requesting user can obtain at least cooperative users’ location information to construct the anonymous region. In addition, in the established blockchain network platform, the “Consensus mechanism —competition mechanism of bookkeeping rights” proposed in this paper is used to determine which user in the network obtains the generation rights to the new block. Moreover, in the blockchain network platform, each block is set to store 100 historical transaction bills. Each transaction bill is used to record the ciphertext and signature data of the requesting user and the cooperative user about the location information provided by the cooperative user during the construction of the anonymous area. We set the current blockchain length toBlockchain=100; in other words, there are 100×100=10000 historical transaction bills. In this experiment, the user’s privacy protection requirement K value changes from 2 to 20, and the algorithm is repeated 100 times for different K values.


### 5.1. Experiment-1

This experiment is to construct an anonymous region. In experiment 1, suppose that the requesting user has provided his real location and participated in the construction of an anonymous area 100 times, in other words,λ0=100. When the requesting user receives more than K−1 cooperative users’ location information, K−1 locations are randomly selected to construct the anonymous area. The average computation delay and communication cost required by the cooperative user and the requesting user in the anonymous region construction process are shown in Figure 1, respectively.Figure 1
The average computation delay and communication cost of constructing an anonymous region.
(a)
Average computing delay of requesting user and cooperating user(b)
Average communication cost requesting user and cooperating userWhen the user uses this scheme to protect its location privacy in anLBS query, the average computing delay required for the successful construction of the anonymous area increases when K increases. For cooperative users, the average computing delay is independent of the privacy protection requirements K value of the requesting user, as shown in Figure 1(a). The reason for the above phenomenon is that with an increasing K value, the requesting user must verify the correctness of the signature data sent by the cooperative user, and the number of times to decrypt and obtain the real location of the cooperative user also increases. However, for cooperative users Pi1⩽i⩽K−1, when they receive the cooperation request of constructing the anonymous area sent by the requesting user P0 and δi⩽λ0, it is only required to encrypt its real location with the public key of the requesting user and send the encrypted ciphertext to the requesting user. Therefore, the average computing delay required by the requesting user is independent of the K value.In addition, in the process of constructing the anonymous area, the average communication cost of the requesting user increases with the increase in theK value of the privacy protection requirement of the requesting user. The reason is that with an increase in the K value, the requesting user must receive more location information provided by cooperative users to construct the anonymous area, which increases the average communication cost of the requesting users. However, for the cooperative users, the point-to-point communication is used to provide their real location to the requesting users. Therefore, the average communication cost required by the cooperative users does not change with the K value of the privacy protection requirement of the requesting users, as shown in Figure 1(b).Through the above experiments, it can also be found that when the requesting user successfully generates the anonymous area by using this scheme, the computation delay and communication cost required by the requesting user and the cooperative user are also very limited. For example, whenK=20, the average computing delay of the requesting user is 311.924 ms, and the average communication cost is 17.206 kb; additionally, the average computing delay of the cooperative user is 32.985 ms, and the average computational communication cost is 1.241 kb. This finding shows that the scheme has good usability and can efficiently generate an anonymous area for the requesting user.


### 5.2. Experiment-2

This experiment is to update the blockchain. Next, we analyze the average computing cost and storage cost of a block chain update. In experiment 2, we set the number of transaction bills included in the new block generation to 100. When updating the blockchain, regardless of whether the requesting user has the permission to update the blockchain or not, the calculation delay decreases with the increase in the privacy protection demandK value. The reason is that when the K value increases, the amount of verified signature data sent by the cooperative users increases when the requesting users construct the anonymous zone, which reduces the amount of verified signature data sent by cooperative users in the process of updating the blockchain. Figure 2(a) shows this relationship. For example, when the K value changes from 2 to 20, if the requesting user does not have permission to update the blockchain, the calculation delay required for updating the blockchain is reduced from 3528.142 ms to 3385.354 ms. If the requesting user is given permission to update the blockchain, the computation delay is reduced from 3242.084 ms to 3125.916 ms.Figure 2
Average computing delay required by the requesting user and collaboration user in the blockchain update.
(a)
Average computing delay of requesting user(b)
Average computing delay of cooperative userFor collaborative users, when updating the blockchain, regardless of whether the requesting user has permission to update the blockchain or not, it must verify the correctness of all transaction bills sent by the requesting user. Therefore, the computing delay required by the cooperative user is not affected by theK value of the requesting user, as shown in Figure 2(b).Moreover, since the cooperative user is only required to verify the correctness of the signature data about the real location of the cooperative user in each transaction bill, in the process of updating the blockchain, the computing time delay required by the cooperative users is much less than that of the requesting users.


### 5.3. Experiment-3

This experiment is used to analyze when the blockchain is updated, to assess the impact of the number of transaction bills on the communication cost, calculation delay, and block size. We set the number of transaction bills from 100 to 1000 when the new block is generated. In this scheme, the transaction bills stored in the blockchain are finally broadcasted by the requesting users, which enables all of the users in the network to verify the correctness of these transaction bills. Therefore, the communication cost of the requesting users in the process of the blockchain update increases with an increase in the number of transaction bills, as shown in Figure3. Moreover, with an increase in the number of transaction bills, when the new block is generated, the number of transaction bills to be stored ,and the computing delay of the Merkle tree root node to calculate these bills will also increase. As a result, the calculation delay and the size of the new block will increase with an increase in the number of transaction bills, as shown in Figure 4, respectively.Figure 3
The number of transaction bills and communication costs of the requesting user.Figure 4
Impact of the transaction bill quantity on the network users during the blockchain update.According to the above analysis, when a new block is generated, when there is an increase in the number of transaction bills, the computing delay, communication cost, and storage cost of each user in the network will also increase. However, for the requesting user, when it obtains the generation rights of the new block, it can construct the anonymous area first and then generate the new block. It can be seen from Figure1(a) and Figure 1(b) that the computation delay and communication cost required by both the requesting user and the cooperative user are very limited when the anonymous area is generated by this scheme. This finding shows that the scheme can generate an anonymous region efficiently and has good practicability.In addition, in practical applications, the number of transaction bills used to generate a new block can be reduced by adjusting the frequency of generating new blocks, and the computing delay, communication cost, and storage cost of each user in the network can be reduced when the blockchain is updated, to further improve the usability of the scheme.


## 5.1. Experiment-1

This experiment is to construct an anonymous region. In experiment 1, suppose that the requesting user has provided his real location and participated in the construction of an anonymous area 100 times, in other words,λ0=100. When the requesting user receives more than K−1 cooperative users’ location information, K−1 locations are randomly selected to construct the anonymous area. The average computation delay and communication cost required by the cooperative user and the requesting user in the anonymous region construction process are shown in Figure 1, respectively.Figure 1
The average computation delay and communication cost of constructing an anonymous region.
(a)
Average computing delay of requesting user and cooperating user(b)
Average communication cost requesting user and cooperating userWhen the user uses this scheme to protect its location privacy in anLBS query, the average computing delay required for the successful construction of the anonymous area increases when K increases. For cooperative users, the average computing delay is independent of the privacy protection requirements K value of the requesting user, as shown in Figure 1(a). The reason for the above phenomenon is that with an increasing K value, the requesting user must verify the correctness of the signature data sent by the cooperative user, and the number of times to decrypt and obtain the real location of the cooperative user also increases. However, for cooperative users Pi1⩽i⩽K−1, when they receive the cooperation request of constructing the anonymous area sent by the requesting user P0 and δi⩽λ0, it is only required to encrypt its real location with the public key of the requesting user and send the encrypted ciphertext to the requesting user. Therefore, the average computing delay required by the requesting user is independent of the K value.In addition, in the process of constructing the anonymous area, the average communication cost of the requesting user increases with the increase in theK value of the privacy protection requirement of the requesting user. The reason is that with an increase in the K value, the requesting user must receive more location information provided by cooperative users to construct the anonymous area, which increases the average communication cost of the requesting users. However, for the cooperative users, the point-to-point communication is used to provide their real location to the requesting users. Therefore, the average communication cost required by the cooperative users does not change with the K value of the privacy protection requirement of the requesting users, as shown in Figure 1(b).Through the above experiments, it can also be found that when the requesting user successfully generates the anonymous area by using this scheme, the computation delay and communication cost required by the requesting user and the cooperative user are also very limited. For example, whenK=20, the average computing delay of the requesting user is 311.924 ms, and the average communication cost is 17.206 kb; additionally, the average computing delay of the cooperative user is 32.985 ms, and the average computational communication cost is 1.241 kb. This finding shows that the scheme has good usability and can efficiently generate an anonymous area for the requesting user.


## 5.2. Experiment-2

This experiment is to update the blockchain. Next, we analyze the average computing cost and storage cost of a block chain update. In experiment 2, we set the number of transaction bills included in the new block generation to 100. When updating the blockchain, regardless of whether the requesting user has the permission to update the blockchain or not, the calculation delay decreases with the increase in the privacy protection demandK value. The reason is that when the K value increases, the amount of verified signature data sent by the cooperative users increases when the requesting users construct the anonymous zone, which reduces the amount of verified signature data sent by cooperative users in the process of updating the blockchain. Figure 2(a) shows this relationship. For example, when the K value changes from 2 to 20, if the requesting user does not have permission to update the blockchain, the calculation delay required for updating the blockchain is reduced from 3528.142 ms to 3385.354 ms. If the requesting user is given permission to update the blockchain, the computation delay is reduced from 3242.084 ms to 3125.916 ms.Figure 2
Average computing delay required by the requesting user and collaboration user in the blockchain update.
(a)
Average computing delay of requesting user(b)
Average computing delay of cooperative userFor collaborative users, when updating the blockchain, regardless of whether the requesting user has permission to update the blockchain or not, it must verify the correctness of all transaction bills sent by the requesting user. Therefore, the computing delay required by the cooperative user is not affected by theK value of the requesting user, as shown in Figure 2(b).Moreover, since the cooperative user is only required to verify the correctness of the signature data about the real location of the cooperative user in each transaction bill, in the process of updating the blockchain, the computing time delay required by the cooperative users is much less than that of the requesting users.


## 5.3. Experiment-3

This experiment is used to analyze when the blockchain is updated, to assess the impact of the number of transaction bills on the communication cost, calculation delay, and block size. We set the number of transaction bills from 100 to 1000 when the new block is generated. In this scheme, the transaction bills stored in the blockchain are finally broadcasted by the requesting users, which enables all of the users in the network to verify the correctness of these transaction bills. Therefore, the communication cost of the requesting users in the process of the blockchain update increases with an increase in the number of transaction bills, as shown in Figure3. Moreover, with an increase in the number of transaction bills, when the new block is generated, the number of transaction bills to be stored ,and the computing delay of the Merkle tree root node to calculate these bills will also increase. As a result, the calculation delay and the size of the new block will increase with an increase in the number of transaction bills, as shown in Figure 4, respectively.Figure 3
The number of transaction bills and communication costs of the requesting user.Figure 4
Impact of the transaction bill quantity on the network users during the blockchain update.According to the above analysis, when a new block is generated, when there is an increase in the number of transaction bills, the computing delay, communication cost, and storage cost of each user in the network will also increase. However, for the requesting user, when it obtains the generation rights of the new block, it can construct the anonymous area first and then generate the new block. It can be seen from Figure1(a) and Figure 1(b) that the computation delay and communication cost required by both the requesting user and the cooperative user are very limited when the anonymous area is generated by this scheme. This finding shows that the scheme can generate an anonymous region efficiently and has good practicability.In addition, in practical applications, the number of transaction bills used to generate a new block can be reduced by adjusting the frequency of generating new blocks, and the computing delay, communication cost, and storage cost of each user in the network can be reduced when the blockchain is updated, to further improve the usability of the scheme.


## 6. Summary and Prospects

The existing distributedk-anonymity privacy protection schemes cannot effectively protect the users’ location privacy. The reason for this problem is that these schemes do not consider privacy disclosure and deception during the construction of an anonymous area, which makes a self-interested requesting user disclose the real location of the cooperative users to a third party to obtain additional benefits. However, the self-interested cooperative users will provide false locations to the requesting user, which results in the constructed anonymous area not meeting the location privacy protection requirements of the requesting user. To solve this problem, this paper first describes the game of constructing a distributed anonymous area, and it then analyzes the policy choices and benefits of the requesting and cooperating users. The security definition of distributed k-anonymous location privacy protection is given. Then, the block chain distributed storage is used to take the requesting users, cooperative users, and location information provided by the cooperative users as evidence. When punishing the users who have location leakage and spoofing behavior, they cannot construct an anonymous area successfully when sending anonymous area collaborative construction requests in the future, which will restrict the self-interest behavior of the requesting users and the cooperative users. Based on the above discussion, this paper proposes a distributed k-anonymous location privacy protection scheme based on blockchain. Security analysis and experiments show that this scheme can not only effectively prevent the requesting users from divulging the location information of the cooperative users but also urge the cooperative users to provide the real location, to construct the anonymous area efficiently. In addition, this scheme can not only protect the location privacy of the user in a sparse crowd scene but also protect the location privacy of the continuous queries.



---

*Source: 2328734-2022-04-20.xml*