# Protecting Check-In Data Privacy in Blockchain Transactions with Preserving High Trajectory Pattern Utility

Authors: Xiufeng Xia; Tingting Hou; Xiangyu Liu; Chuanyu Zong; Shengsheng Mu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Because the blockchain is secure and untamperable, it has been widely used in many industries, such as the financial industry, digital tokens, and e-commerce logistics. The remarkable security feature of the blockchain is that the blockchain verifies the transaction initiated on each block through the node, and its process is broadcast throughout the whole network to let everyone know. On the one hand, this ensures the security of every transaction, but on the other hand, it is easy to cause privacy disclosure problems for transaction users. Therefore, under the premise of ensuring the security of the blockchain, it has become a hot issue to protect the sensitive information of transaction users. A check-in privacy protection (CPP) algorithm based on check-in location generalization is proposed in this paper, which can be applied to blockchain transactions to solve the privacy leakage problem of transaction users’ sensitive information. CPP algorithm not only protects the privacy of check-in data but also keeps the high utility of trajectory pattern data. Firstly, location types are recommended in the sensitive check-in location generalization based on the user’s trajectory pattern by using Markov chain technology. Secondly, to make sure that the generalized locations can be scattered as much as possible to prevent the attacker from deducing back, a heuristic rule is designed to select the generalized location based on the recommended location types, and at the same time, the similarity between the anonymous trajectory and the original trajectory is maintained. In addition, a generalized location search strategy is designed to improve the efficiency of the algorithm. Based on the real spatial-temporal check-in data, the results of the experiment indicate that our algorithm can effectively protect the privacy of sensitive check-in while ensuring the high utility of trajectory pattern data.


---

## Body

## 1. Introduction

In recent years, the blockchain [1] has been broadly used in the financial industry, digital tokens, e-commerce logistics, and many other industries due to its characteristics of security and untampering. The significant security feature of the blockchain is that the blockchain authenticates each transaction initiated on each block through the node, and its process is broadcast throughout the network for everyone to know. This not only ensures the security of the transaction but also brings privacy harm to the transaction users. Hence, under the premise of ensuring the security of the blockchain [2, 3], it is already an issue worthy of attention to protect the sensitive information of transaction users. With the constant development of mobile networks [4, 5], vehicular networks [6–9], wireless communications network [10], and GPS-enabled devices, a mass of check-in data [11] of mobile users has been collected and utilized.Check-in data contains the characteristics of human behavior, which plays a key role in major social science issues such as disease transmission, epidemic prevention and control, poverty eradication, urban planning, and other important life applications such as route recommendation and bus travel. Government and many research institutions hope to create more value through data mining. The trajectory contains many sensitive check-in data. Users’ private information (home address, religious belief, interests, health, and other private information) will be obtained and used by malicious attackers, assuming these sensitive check-in data is leaked. Therefore, protecting sensitive check-in data in trajectory has become a challenging problem.Check-in data means the user visits a certain place at a certain time. Sensitive check-in refers to user hopes to keep check-in data from being leaked. The useru’s historical trajectory set Tr=tr1,tr2,tr3,tr4,tr5,tr6 is shown in Figure 1(a), and four check-in data in chronological order are included in the trajectory tr5=<l2,t51,l5,t52,l7,t53,l8,t54>. The check-in data l7,t53 indicates that user u visits location l7 at time t53. The location type of l7 is the zoo, and t53 belongs to user u’s office time. User u does not want to disclose the check-in data; therefore, l7,t53 is set to sensitive check-in of user u. Currently, there is no privacy protection technology for sensitive check-in, and location privacy protection [12–15] is nearest to the problem.Figure 1
User trajectory set and anonymous trajectory.
(a)
A set of user history trajectory(b)
The random method is used to protect the sensitive check-in in the trajectory(c)
This experiment is used to protect the sensitive check-in in the trajectoryLocation generalization [16] is a popular location privacy protection method, and it has the characteristics of retaining the user’s complete location information, law computation, and simple mechanism. However, these current location generalization methods do not consider the user trajectory pattern factor, which may reduce the privacy protection degree of sensitive check-in or even directly reveal the real sensitive check-in of user.For example, the trajectory in Figure1(b) is an anonymous trajectory obtained by using location generalization technology under 4-anonymity privacy requirement (4-anonymity means that the probability of identifying the sensitive check-in location based on this anonymous trajectory is no more than 1/4). Generalized locations l71, l72, and l73 are obtained by a random method in literature [17], and these and the real sensitive check-in location l7 form an anonymous location set to participate in the trajectory release; thus, the attacker cannot guess the real check-in location of user u at time t53. This anonymous trajectory has two problems: (1) it does not conform to the user trajectory pattern. Location type of l5 is bank. Based on user history trajectory, it can be seen that the next possible location type is the zoo, the coffee shop, and the bank from the current location type with the probability of visit being 4/7, 2/7, and 1/7, respectively. However, the location type of l71 and l73 is the fitness room. Obviously, the attacker can easily deduce that l71,t53 and (l73,t53) are false check-in based on user history trajectory. (2) The similarity between the anonymous trajectory and the original trajectory decreases. l7a is the anonymous central location generated after random generalization, and l7a′ is the anonymous central location generated after another anonymization. As shown in Figure 1(b), the shape of the anonymous trajectory <l2,t51,l5,t52,l7a,t53,l8,t54> differs greatly from that of the original trajectory <l2,t51,l5,t52,l7,t53,l8,t54>. In Figure 1(c), the shape of the anonymous trajectory <l2,t51,l5,t52,l7a′,t53,l8,t54> is closer to that of the original trajectory <l2,t51,l5,t52,l7,t53,l8,t54>. Due to the above two problems, the probability of identifying sensitive check-in will be greater than 1/4 and lead to privacy disclosure of sensitive check-in. To solve the problem, this paper proposes a check-in privacy protection algorithm based on check-in location generalization to protect the privacy of check-in data and keep the high utility of trajectory pattern data.The main contributions are as follows:(1)
We propose a check-in privacy protection (CPP) algorithm based on check-in location generalization(2)
We recommend generalized location types by using Markov chain technology, and design a heuristic rule to select generalized locations(3)
We optimize the generalized location search strategy to improve the efficiency of the algorithm(4)
Extensive empirical studies show that our algorithm performs efficiently to protect check-in data while preserving the high utility of trajectory pattern dataThe rest of the paper is organized as follows. Section2 analyzes related work. Section 3 presents some important concepts and problem definition. Section 4 elaborates our scheme in detail. Section 5 evaluates the performance of CPP. We conclude this paper in Section 6.


## 2. Related Work

Sweeney [12] first proposed the concept of the k-anonymity model, and it was first applied in the relational database. Subsequently, Gruteser and Grunwald and Gruteser and Liu [18, 19] applied the k-anonymity model to location privacy protection. The core idea of it is that the anonymous server selects k−1 generalized locations to form an anonymous set with user real location, and the k locations cannot be distinguished from each other. Gedik and Ling [20] proposed the Clique Cloak algorithm, which constructed the anonymous region based on the graph model combined with time and space factors, and transformed the problem of anonymous set into the problem of finding k−1 neighbors in the graph model. Wang et al. [21] proposed a generalized location generation scheme based on semantic information and query probability, which can generate k−1 generalized locations related to user location semantic information. Niu et al. [22] proposed an enhanced DLS algorithm, which can select 2k generalized locations with high query probability similarity to the real location by calculating the location entropy and then select k−1 generalized locations from them by calculating the product of location distance. Lu et al. [23] proposed two generalized location generation algorithms CirDummy and GridDummy to realize location k-anonymity considering the shape of user privacy region.Dwork [13] first proposed the differential privacy protection method, which protects privacy by adding noise to distort data. The differential privacy protection technology with mathematical theory and strict mathematical definition has two characteristics: first, it is not affected by attackers with background knowledge, and second, it is not affected by changing the specific data. Xiong et al. [24] proposed a spatial crowdsourcing algorithm based on a reward mechanism, which protects location privacy by adding Laplace noise to location data. Xu et al. [25] proposed a hybrid location privacy protection method, which divided locations into discrete locations and nondiscrete locations. For discrete locations, differential privacy technology was directly used for noise processing; while for nondiscrete locations, a k-means clustering algorithm based on differential privacy technology was used for generalization processing. However, excessive noise will lead to poor data availability and serious errors. Thus, Ping et al. [26] proposed PriLocation, a differential privacy protection method for noise reduction, to solve effectively this problem caused by excessive noise.The basic idea of the location privacy protection method based on encryption technology is to encrypt the user’s query information. Even if the attacker obtains the query information, he cannot know the real privacy information behind the query information. Zhang and Ni [14, 15] proposed a neighbor query method PRN-KNN, which uses a spatial encryption algorithm to enable users to quickly query k-neighbor candidate sets and introduces pseudo-random number secret rules to effectively reduce algorithm processing time. Papadopoulos et al. [27] used security hardware to assist PIR protocol and protected user location privacy through KNN query. Encryption-based location privacy protection technology can better ensure data availability and service accuracy, but the disadvantage is a large amount of calculation.


## 3. Preliminaries and Problem Definition

The check-in data set of useru is represented as Cu=ci∣i∈1,m. The check-in data ci=li,ti indicates that user u visits location li at time ti, where ti is the check-in time, and li is the specific location on the map, such as Northeastern University, Wanda Plaza, and Beiling Park, and (x,y) is the latitude and longitude of a specific location, respectively. Ti represents the location type of a specific location, such as universities, shopping centers, and parks.Definition 1 Sensitive check-in.
Given trajectorytr=<l1,t1,ls,ts,⋯,ln,tn>, if the user does not want to check in, (ls,ts) was exposed, so (ls,ts) is called sensitive check-in. As shown in Figure 1(b), (l7,t53) is a sensitive check-in in trajectory tr5.Definition 2 Trajectory pattern matrixM.
Given anm∗m matrix, T1,⋯,Tm represents the location type, and MTi,Tj represents the probability that the user travels from location type Ti to location type Tj.As shown in Table1(a), the location type of the zoo, the fitness room, the coffee shop, and the bank are, respectively, denoted T1, T2, T3, and T4, respectively. The user trajectory pattern matrix M is obtained according to the transfer situation of location type in user’s historical trajectory set Tr, where MT1,T2 represents the transfer probability that the user travels from location type T1 to the next location type T2. In Figure 1(a), location type T1 includes l7, l8, and l9. The next location of l7 is l1 (T2) and l8 (T1). The next location of l8 is l2 (T3). The next location of l9 is l3 (T2) and l5 (T4). Therefore, the value of MT1,T2 is 2/5.Definition 3 Check-in location generalization.
Given a check-in data (ls,ts), generalization operation refers to convert location ls of check-in (ls,ts) to a location set L′=ls,l1′,l2′,⋯,li′, there are 1+i locations in L′, and the probability that any location in the set appears between moment ts−1 and moment ts+1 is equal.Definition 4 Anonymous trajectory.
The trajectory obtained after replacing the sensitive check-in locationls in the original trajectory with the anonymous center location lsa after anonymization.Table 1
Trajectory pattern matrix.
(a)
User trajectory pattern matrix
MatrixMT1T2T3T4T10.20.40.20.2T20001T30.250.2500.5T44/702/71/7(b)
Anonymous trajectory pattern matrix
MatrixM′T1T2T3T4T13/198/194/194/19T20001T30.250.2500.5T416/2908/295/29As shown in Figure1(b), the anonymous trajectory is represented as <l2,t51,l5,t52,l7a,t53,l8,t54>.Definition 5 Trajectory pattern similarity.
Given the original trajectory pattern matrixM and the anonymous trajectory pattern matrix M′ (the order of the matrix is m), the trajectory pattern similarity is shown in Formula (1):
(1)simM,M′=∑Mi,j∗M′i,j∑Mi,j2∑M′i,j2i,j∈1,m.As shown in Figure1(b), the anonymous trajectory pattern matrix M′ is obtained by anonymizing the original trajectory pattern matrix M, and the value of trajectory pattern similarity simM,M′ is 99.93%.Definition 6 Check-ink-anonymity.
Given sensitive check-in (ls,ts), the generalized location set c′=ls1,⋯,lsm is get through the check-in location generalization operation, where size c′>=k, so that the leakage rate of check-in location is not greater than 1/k, namely, check-in k-anonymity.Definition 7 Location exposure rate LE.
The generalized location is expressed asl′, the location anonymous set is composed of the real check-in location l and k−1 generalized locations, namely, LAS=l,l1,l2,⋯,lk−1. Given the user location anonymous set LAS, the attacker uses background knowledge to identify LAS and infers the probability of the user real check-in location as shown in Formula (2):
(2)LE=1LAS−LAS′.
∣LAS∣ represents the total number of locations in an anonymous set, and |LAS′| indicates that the attacker can identify the number of generalized locations.Definition 8 Distance between trajectories.
Given original trajectory, sensitive check-in locationls, anonymous trajectory, and anonymous center location lsa, the distance between trajectories is defined as the Euclidean distance between two locations as seen in Formula (3):
(3)tr_distls,lsa=ls.x−lsa.x2+ls.y−lsa.y2.Problem definition. Given check-in data set Cu, sensitive check-in set Su of user u, real trajectory tr, and privacy protection threshold k, the location anonymous set LAS is obtained by generalizing the sensitive check-ins in sensitive check-in set based on trajectory pattern. The generalized check-ins in LAS not only meet check-in k-anonymity but also ensure the maximum similarity of trajectory pattern.


## 4. Check-In Privacy Protection Algorithm Based on Generalization of Check-In Location

In this section, the check-in privacy protection algorithm based on check-in location generalization (Algorithm1) is proposed. The main idea is to select the generalized location based on the original trajectory pattern matrix in the process of check-in location generalization so that the generalization operation can change the similarity between the original trajectory pattern matrix and the anonymous trajectory pattern matrix as little as possible. Thus, high data availability of anonymous trajectory in trajectory patterns is guaranteed. The algorithm framework of this paper is shown in Figure 2. The algorithm framework can show that users’ sensitive check-ins are protected by the four algorithms (Algorithms 1–4) proposed in this paper, and this method can be used to protect user identity information in blockchain transactions.Algorithm 1: Check-in privacy protection algorithm based on generalization of check-in location.
Input: sensitive check-in locationls, privacy protection threshold k;Output: an anonymous set of locations containingk locations.1.LAS⟵∅;2.T= MC-LTR (M,rM,sub_T,s);3.L= GLS (D−index,R,tr);4.S = LATP (k,T,M,Ts);5.Candl= DLS (S,k,ls);6. LAS =Candl⋃ls;7. if(LE<1/k)then8. Return LAS.9. else10. Return∅ .Figure 2
The algorithm framework of CPP.First, the Markov chain-location type recommendation (MC-LTR) algorithm is used to recommend the set of location types for sensitive check-ins (line 2). Generalizing location search (GLS) algorithm is used to search the specific location in the generalization area (line 3). The location assignment based on trajectory pattern (LATP) algorithm is adopted to allocate the number of generalized locations corresponding to the recommended location type, and the aim is to ensure that the change of the anonymized trajectory pattern matrix is minimal (line 4). The dummy location selection (DLS) algorithm is used to obtain the candidate array of generalized locations (line 5). As shown in Formula (4), score is a heuristic function, whose value measures the influence of the distance product between the generalized locations and the sensitive check-in location and the distance between trajectories before and after anonymity. The higher the value, the more scattered between the generalized locations and the sensitive check-in location, and the closer the distance between the anonymous trajectory and real trajectory is. Finally, the CPP algorithm returns an anonymous location set containing k locations (line 6).
(4)Score=∏distli,ljdistls,lsali≠lj.For example, we protect sensitive check-in (l7,t53) in trajectory tr5.The random choice of location type is likely to expose the user’s sensitive check-in, so the MC-LTR algorithm is used to ensure that the generalized location type conforms to the user’s historical trajectory pattern. The location type of sensitive check-in location l7 is T1, and the location type of next moment predicted based on Markov chain includes T1, T2, T3, and T4, and the recommendation probability is 4/35, 0, 1/14, and 4/49, respectively. Therefore, the recommended set of location types for sensitive check-in (l7,t53) is T=T1,T4,T3. Searching the specific location corresponding to the recommended location type mainly considers two factors: historical average speed and time accessibility. In the query area, GLS algorithm will be used to put the searched specific locations corresponding to each location type in the set into location queue L, namely, L=l11,l12,l41,l42,l43,l32, wherein the location type T1 contains two specific locations l11 and l12, and the location type T4 contains three specific locations l41, l42 and l43, and the location type T3 contains one specific location l32. Due to need to achieve the 4-anonymity protection, three generalized locations are selected from location queue L to ensure that the anonymous set can achieve optimal protection. By using the LATP algorithm, one location type meeting the requirement of anonymity is selected at a time, and the number array S of generalized location types is obtained. Among them, ST1=2, ST4=1, and ST3=0. The dispersion between locations and the change situation of the original trajectory’s shape and the anonymous trajectory’s shape are considered. The purpose is to prevent the location exposure and ensure trajectory similarity. Finally, the DLS algorithm is used to select 3 candidates from the location queue L and put them into the location anonymous set LAS, namely, LAS=l11,l12,l42.


### 4.1. Recommendations for Generalizing Location Types

This section mainly introduces recommendations of the location type for sensitive check-in based on the MC-LTR algorithm (Algorithm2). For example, by using this algorithm, the location type recommendation is made during generalized sensitive check-in (l7,t53). Check-in data is an integral part of user trajectory, and user trajectory patterns can reflect user behavior characteristics, so the selection of location type should be in accordance with the user trajectory movement pattern. Because the sensitive check-in location l7 is located in the middle of the trajectory, two predictions are needed to realize the location type recommendation. According to the previous moment location type T4 of the sensitive check-in, it is predicted that the generalized location types of the sensitive check-in are T1, T2, T3, and T4, and the probabilities are 4/7, 0, 2/7, and 1/7, respectively. The transfer probability of each generalized location type to the next moment location type for sensitive location is 1/5, 0, 1/4, and 4/7, respectively. Therefore, the recommended set of generalized location types for sensitive check-in is represented as T=T1,T4,T3.As shown in Table2, the user reverse trajectory pattern matrix RM is obtained in reverse time based on the user trajectory set Tr. In Algorithm 2, M and RM are taken as inputs to recommend set T of location types that meets the trajectory pattern.Algorithm 2: The Markov-chain location type recommendation algorithm.
Input: trajectory pattern matrixM, reverse trajectory pattern matrix R(M), sensitive sub-trajectory type sub_T= {Tbefore,Ts,Tbehind}, recommended location type quantity threshold s;Output: setT of location types.1. InitializeT[i], i∈1,∣M∣;2. if (sub_T[0] ==∅) then3.T[i]=RMsub_T2i,i∈1,∣M∣;4. else if (sub_T[2] ==∅) then5.T[i]=Msub_T0i,i∈1,∣M∣;6. else then7.T[i]=Msub_T0i×RMisub_T2; i∈1,∣M∣;8. sort(T[i]);9. Select the firsts location types with higher probability values and put them into T;10. ReturnT.Table 2
Reverse trajectory pattern matrix.
MatrixRMT1T2T3T4T11/601/62/3T22/301/30T31/3002/3T40.20.20.40.2Algorithm2 shows the recommendation process of location types when generalizing sensitive check-in. The algorithm takes into account three kinds of location situations of sensitive check-in in the trajectory. When the sensitive check-in location is located at the beginning of the trajectory, the reverse trajectory pattern matrix is used for the recommended location type of the sensitive check-in (lines 2 and 3). When the sensitive check-in location is located at the end of the trajectory, the trajectory pattern matrix is used for the recommended location type of the sensitive check-in (lines 4 and 5). When the sensitive check-in location is located at the nonhead-tail location of the trajectory, the combination of two trajectory pattern matrices is used to recommend location type for the sensitive check-in (lines 6 and 7). Finally, the first s location types with high recommendation probability values are selected from the recommended location types and put into the set T of location types.


### 4.2. Search for Specific Generalization Location

Algorithm 3: The generalized location search algorithm.
Input: distance indexD-index, query distance R, any location li;Output: location queueL.1.L=∅;2. pos =1, end =lens (D-index [li]);3. While (pos<end) do4.  mid=(post+end)/2;5. ifD-index[mid]<Rthen6.   pos=mid+1;7. else ifD-index[mid]>R then8.   end=mid-1;9.  else10.   pos=end=mid;11.L=D-index [li], i∈(1, pos);12. ReturnL.This section mainly introduces the use of a generalized location search algorithm (Algorithm3) to generate location queue L. According to the recommended location type, the specific location of the corresponding location type should be searched in the query area. At the same time, the specific location selected should meet the time accessibility. For example, the query areas of sensitive check-in (l7,t53) are circular areas with check-in location l5 at the previous time and check-in location l8 at the later time as the center and v¯t53−t52 and v¯t54−t53 as the query radius, respectively, where v¯ is the average speed calculated from the user’s historical trajectory. First, the specific locations corresponding to each location type in the query area are put into location queue L, namely, L=l11,l12,l41,l42,l43,l32. There are two locations belonging to location type T1, there are three locations belonging to location type T4, there is one location belonging to location type T3, and then, l.DR is defined to represent a group of locations within distance R of sensitive location l. As shown in Table 3, search the location of distance sensitive location l7 within the 0.7 km, that is, l7.D0.7={l11,l12,l41,l42,l32}, and the unit of distance is kilometer (km). The generalized location search algorithm proposed in this paper implements the breadth-first search on the query area to realize the location search. l.D is used to store the searched candidate locations and the corresponding distance index (D-index), and then, the binary search algorithm is used to select the qualified locations, in order to save the running time of the algorithm.Definition 9 Distance index (D-index).
Given a sensitive locationl, the distance index (D-index) between this location and other locations is defined as a list l.D. The elements stored in the list are candidate locations and the distance data between each candidate location and the sensitive location l, and the distance data in l.D are arranged in order from small to large.Algorithm 4: The location assignment based on trajectory pattern algorithm.
Input: privacy protection thresholdk, generalized location type set T, trajectory pattern matrix M, sensitive location type Ts, location queue L;Output: generalized location type quantity arrayS.1. InitializeS [Ti]=0, i∈[1,|T|];2.S [Ts]=min (k-1, L (Ts));3. While∑STi<k-1 do4.   for each location typeTiϵTTi≠Tsdo5.   ifSTi<=L (Ti) then6.STi++;7.    updateM based on STi to change M toMTi;8.    CalculatesimM,MTi;9.STi--;10.Tmax= Ti which maximizes simM,MTi;11.M=MTmax;12. ReturnS.Table 3
Distance index for each sensitive location.
l1l56l31l220.100.200.40l2l16l510.140.18l4l18l94l470.200.220.65l5l72l46l110.240.360.45l7l11l12l32l41l42l430.180.190.580.680.690.72l8l41l41l11l430.110.320.500.75


### 4.3. Generalized Location Quantity Allocation

This section mainly introduces the generalized location quantity allocation algorithm based on the trajectory pattern (Algorithm4). The purpose is to determine the number of specific locations allocated for the recommended location type and to ensure the maximum similarity of the trajectory pattern matrix. As shown in Table 4, five generalized locations (l11,l12,l41,l42,l32) are found for sensitive check-in (l7,t53) through the generalized location search algorithm. Because the privacy protection threshold k is 4, so three of the five generalized locations are selected to ensure the maximum similarity of the trajectory pattern matrix. In the generalized location allocation algorithm based on trajectory pattern, the same generalized location type as the sensitive check-in location is first assigned (line 2), so two generalized locations of location type T1 are assigned. The selection of the remaining generalization location is determined by adding a generalization location of different location type at a time and calculating the similarity value of the corresponding trajectory pattern matrix (lines 4-9). When the generalized location type T3 is added, the similarity of trajectory pattern is 99.81%. When the generalized location T4 is added, the similarity of trajectory pattern is 99.93%. So, a generalization location of type T4 is assigned and returns a generalization location type quantity array S.Table 4
Generalized location quantity allocation.
Location typeT1T2T3T4Number of locations2013Allocated quantity2001


### 4.4. Selection of Candidate Generalized Location

Algorithm 5: The dummy location selection algorithm.
Input: generalized location type quantity arrayS, real sensitive location ls, privacy protection threshold k, location queue L;Output: generalized location candidate arrayCandl.1. InitializeCandl[Ti]=0, i∈[1,|S|];2. while lens (Candl)<k-1 do3. for each location typeTi∈S &&CandlTi<= S [Ti] do4.  if lens (Candl)==0 then5.   Select the location furthest from the real sensitive location from the generalized locations inTi and add it to Candl;6.  else7.   Select the location with the maximum Score inTi and add it to Candl;8. ReturnCandl;This section mainly introduces the selection of candidate generalized locations by candidate location selection algorithm (Algorithm5). The generalized location candidate array needs to meet two conditions: (1) the locations in the array are as scattered as possible, which can effectively prevent the antideduction of the attacker. (2) The center location of the area formed by each location is as close as possible to the sensitive check-in location, which ensures that the anonymous trajectory is similar to the original trajectory. Among them, the traditional method to ensure the dispersion between locations is to calculate the sum of the distance between locations ∑i≠jdistli,lj. However, the product of the distance method ∏i≠jdistli,lj can better reflect the dispersion of locations in most cases. As shown in Figure 3, A and B are selected generalization locations, and C and D are to be selected generalization locations. When selecting the third generalization location, both C and D can meet the requirements if the sum of distance method is used, because tr_distD,A+tr_distD,B=tr_distC,A+tr_distC,B. However, the product of distance method is used, and we should choose the generalization location C, because tr_distC,A∗tr_distC,B>tr_distD,A∗tr_distD,B, and the anonymous region formed by the generalization location A, B, and C is more scattered, so the product of distance method is adopted in this algorithm.Figure 3
Distance product scene graph.


### 4.5. Algorithm Complexity Analysis

In the MC-LTR algorithm, generalized location types are recommended through the trajectory pattern matrix. SupposeM is the order of the user trajectory pattern matrix, so, the time complexity of the MC-LTR algorithm is OM+Mlog2M. In the GLS algorithm, we use the binary search algorithm to find specific generalized locations that match the location type, and the algorithm complexity of the location queue at any sensitive location is Olog2∣D−indexli∣. In the LATP algorithm, we need to assign generalized locations for the recommended location type, because the privacy protection threshold is k, so, the generalization location needs to be allocated through k−1 cycles, and each cycle needs to update the matrix and calculate the matrix similarity. The algorithm’s time complexity is Ok−1s−13+M∗M+2=Ok∗sM2. In the DLS algorithm, we need to choose k−1 candidate generalization locations from the generalization region, and it is necessary to judge ∣STi∣ locations every time, so the algorithm complexity is Ok∗S. Therefore, the time complexity of the CPP algorithm is Ok∗sM2.


## 4.1. Recommendations for Generalizing Location Types

This section mainly introduces recommendations of the location type for sensitive check-in based on the MC-LTR algorithm (Algorithm2). For example, by using this algorithm, the location type recommendation is made during generalized sensitive check-in (l7,t53). Check-in data is an integral part of user trajectory, and user trajectory patterns can reflect user behavior characteristics, so the selection of location type should be in accordance with the user trajectory movement pattern. Because the sensitive check-in location l7 is located in the middle of the trajectory, two predictions are needed to realize the location type recommendation. According to the previous moment location type T4 of the sensitive check-in, it is predicted that the generalized location types of the sensitive check-in are T1, T2, T3, and T4, and the probabilities are 4/7, 0, 2/7, and 1/7, respectively. The transfer probability of each generalized location type to the next moment location type for sensitive location is 1/5, 0, 1/4, and 4/7, respectively. Therefore, the recommended set of generalized location types for sensitive check-in is represented as T=T1,T4,T3.As shown in Table2, the user reverse trajectory pattern matrix RM is obtained in reverse time based on the user trajectory set Tr. In Algorithm 2, M and RM are taken as inputs to recommend set T of location types that meets the trajectory pattern.Algorithm 2: The Markov-chain location type recommendation algorithm.
Input: trajectory pattern matrixM, reverse trajectory pattern matrix R(M), sensitive sub-trajectory type sub_T= {Tbefore,Ts,Tbehind}, recommended location type quantity threshold s;Output: setT of location types.1. InitializeT[i], i∈1,∣M∣;2. if (sub_T[0] ==∅) then3.T[i]=RMsub_T2i,i∈1,∣M∣;4. else if (sub_T[2] ==∅) then5.T[i]=Msub_T0i,i∈1,∣M∣;6. else then7.T[i]=Msub_T0i×RMisub_T2; i∈1,∣M∣;8. sort(T[i]);9. Select the firsts location types with higher probability values and put them into T;10. ReturnT.Table 2
Reverse trajectory pattern matrix.
MatrixRMT1T2T3T4T11/601/62/3T22/301/30T31/3002/3T40.20.20.40.2Algorithm2 shows the recommendation process of location types when generalizing sensitive check-in. The algorithm takes into account three kinds of location situations of sensitive check-in in the trajectory. When the sensitive check-in location is located at the beginning of the trajectory, the reverse trajectory pattern matrix is used for the recommended location type of the sensitive check-in (lines 2 and 3). When the sensitive check-in location is located at the end of the trajectory, the trajectory pattern matrix is used for the recommended location type of the sensitive check-in (lines 4 and 5). When the sensitive check-in location is located at the nonhead-tail location of the trajectory, the combination of two trajectory pattern matrices is used to recommend location type for the sensitive check-in (lines 6 and 7). Finally, the first s location types with high recommendation probability values are selected from the recommended location types and put into the set T of location types.


## 4.2. Search for Specific Generalization Location

Algorithm 3: The generalized location search algorithm.
Input: distance indexD-index, query distance R, any location li;Output: location queueL.1.L=∅;2. pos =1, end =lens (D-index [li]);3. While (pos<end) do4.  mid=(post+end)/2;5. ifD-index[mid]<Rthen6.   pos=mid+1;7. else ifD-index[mid]>R then8.   end=mid-1;9.  else10.   pos=end=mid;11.L=D-index [li], i∈(1, pos);12. ReturnL.This section mainly introduces the use of a generalized location search algorithm (Algorithm3) to generate location queue L. According to the recommended location type, the specific location of the corresponding location type should be searched in the query area. At the same time, the specific location selected should meet the time accessibility. For example, the query areas of sensitive check-in (l7,t53) are circular areas with check-in location l5 at the previous time and check-in location l8 at the later time as the center and v¯t53−t52 and v¯t54−t53 as the query radius, respectively, where v¯ is the average speed calculated from the user’s historical trajectory. First, the specific locations corresponding to each location type in the query area are put into location queue L, namely, L=l11,l12,l41,l42,l43,l32. There are two locations belonging to location type T1, there are three locations belonging to location type T4, there is one location belonging to location type T3, and then, l.DR is defined to represent a group of locations within distance R of sensitive location l. As shown in Table 3, search the location of distance sensitive location l7 within the 0.7 km, that is, l7.D0.7={l11,l12,l41,l42,l32}, and the unit of distance is kilometer (km). The generalized location search algorithm proposed in this paper implements the breadth-first search on the query area to realize the location search. l.D is used to store the searched candidate locations and the corresponding distance index (D-index), and then, the binary search algorithm is used to select the qualified locations, in order to save the running time of the algorithm.Definition 9 Distance index (D-index).
Given a sensitive locationl, the distance index (D-index) between this location and other locations is defined as a list l.D. The elements stored in the list are candidate locations and the distance data between each candidate location and the sensitive location l, and the distance data in l.D are arranged in order from small to large.Algorithm 4: The location assignment based on trajectory pattern algorithm.
Input: privacy protection thresholdk, generalized location type set T, trajectory pattern matrix M, sensitive location type Ts, location queue L;Output: generalized location type quantity arrayS.1. InitializeS [Ti]=0, i∈[1,|T|];2.S [Ts]=min (k-1, L (Ts));3. While∑STi<k-1 do4.   for each location typeTiϵTTi≠Tsdo5.   ifSTi<=L (Ti) then6.STi++;7.    updateM based on STi to change M toMTi;8.    CalculatesimM,MTi;9.STi--;10.Tmax= Ti which maximizes simM,MTi;11.M=MTmax;12. ReturnS.Table 3
Distance index for each sensitive location.
l1l56l31l220.100.200.40l2l16l510.140.18l4l18l94l470.200.220.65l5l72l46l110.240.360.45l7l11l12l32l41l42l430.180.190.580.680.690.72l8l41l41l11l430.110.320.500.75


## 4.3. Generalized Location Quantity Allocation

This section mainly introduces the generalized location quantity allocation algorithm based on the trajectory pattern (Algorithm4). The purpose is to determine the number of specific locations allocated for the recommended location type and to ensure the maximum similarity of the trajectory pattern matrix. As shown in Table 4, five generalized locations (l11,l12,l41,l42,l32) are found for sensitive check-in (l7,t53) through the generalized location search algorithm. Because the privacy protection threshold k is 4, so three of the five generalized locations are selected to ensure the maximum similarity of the trajectory pattern matrix. In the generalized location allocation algorithm based on trajectory pattern, the same generalized location type as the sensitive check-in location is first assigned (line 2), so two generalized locations of location type T1 are assigned. The selection of the remaining generalization location is determined by adding a generalization location of different location type at a time and calculating the similarity value of the corresponding trajectory pattern matrix (lines 4-9). When the generalized location type T3 is added, the similarity of trajectory pattern is 99.81%. When the generalized location T4 is added, the similarity of trajectory pattern is 99.93%. So, a generalization location of type T4 is assigned and returns a generalization location type quantity array S.Table 4
Generalized location quantity allocation.
Location typeT1T2T3T4Number of locations2013Allocated quantity2001


## 4.4. Selection of Candidate Generalized Location

Algorithm 5: The dummy location selection algorithm.
Input: generalized location type quantity arrayS, real sensitive location ls, privacy protection threshold k, location queue L;Output: generalized location candidate arrayCandl.1. InitializeCandl[Ti]=0, i∈[1,|S|];2. while lens (Candl)<k-1 do3. for each location typeTi∈S &&CandlTi<= S [Ti] do4.  if lens (Candl)==0 then5.   Select the location furthest from the real sensitive location from the generalized locations inTi and add it to Candl;6.  else7.   Select the location with the maximum Score inTi and add it to Candl;8. ReturnCandl;This section mainly introduces the selection of candidate generalized locations by candidate location selection algorithm (Algorithm5). The generalized location candidate array needs to meet two conditions: (1) the locations in the array are as scattered as possible, which can effectively prevent the antideduction of the attacker. (2) The center location of the area formed by each location is as close as possible to the sensitive check-in location, which ensures that the anonymous trajectory is similar to the original trajectory. Among them, the traditional method to ensure the dispersion between locations is to calculate the sum of the distance between locations ∑i≠jdistli,lj. However, the product of the distance method ∏i≠jdistli,lj can better reflect the dispersion of locations in most cases. As shown in Figure 3, A and B are selected generalization locations, and C and D are to be selected generalization locations. When selecting the third generalization location, both C and D can meet the requirements if the sum of distance method is used, because tr_distD,A+tr_distD,B=tr_distC,A+tr_distC,B. However, the product of distance method is used, and we should choose the generalization location C, because tr_distC,A∗tr_distC,B>tr_distD,A∗tr_distD,B, and the anonymous region formed by the generalization location A, B, and C is more scattered, so the product of distance method is adopted in this algorithm.Figure 3
Distance product scene graph.


## 4.5. Algorithm Complexity Analysis

In the MC-LTR algorithm, generalized location types are recommended through the trajectory pattern matrix. SupposeM is the order of the user trajectory pattern matrix, so, the time complexity of the MC-LTR algorithm is OM+Mlog2M. In the GLS algorithm, we use the binary search algorithm to find specific generalized locations that match the location type, and the algorithm complexity of the location queue at any sensitive location is Olog2∣D−indexli∣. In the LATP algorithm, we need to assign generalized locations for the recommended location type, because the privacy protection threshold is k, so, the generalization location needs to be allocated through k−1 cycles, and each cycle needs to update the matrix and calculate the matrix similarity. The algorithm’s time complexity is Ok−1s−13+M∗M+2=Ok∗sM2. In the DLS algorithm, we need to choose k−1 candidate generalization locations from the generalization region, and it is necessary to judge ∣STi∣ locations every time, so the algorithm complexity is Ok∗S. Therefore, the time complexity of the CPP algorithm is Ok∗sM2.


## 5. Experimental Evaluation and Analysis

This section analyzes and evaluates the performance of the proposed check-in privacy protection algorithm based on generalized check-in location. The data used in the experiment comes from two real data sets Brightkite and Gowalla disclosed by the complex network analysis platform of Stanford University. The map data of California where these two data sets are located are also obtained. Firstly, this paper deletes and filters users whose cumulative check-in days are less than 50 days in the data set and then deletes the trajectory that contains only one check-in data in a single trajectory. Finally, this article selects 5000 users and their corresponding data from the two data sets. Table5 shows the relevant information of the experimental data.Table 5
Experimental data statistics.
Experimental data setNumber of usersNumber of locationsNumber of check-insNumber of trajectoriesNumber of location typesBrightkite50002747613185493168766316Gowalla50001939891501739121436665This paper proposes a check-in privacy protection algorithm based on the generalization of check-in location (recorded as CPP), compared with the dummy location selection algorithm based on multiobjective optimization (recorded as enhanced DLS) [12] and the location privacy protection algorithm based on random selection method (recorded as RS) [7]. The performance of the algorithm is analyzed by comparison, and the influence of the parameters involved in the algorithm on the algorithm is evaluated. In the test, the value range of privacy protection anonymous parameter k is from 2 to 32.The software and hardware environment of this experiment are as follows: (1) hardware environment: Intel Xeon 3.90 GHz CPU and 256 GB; (2) operating system platform: Microsoft Windows 10; and (3) programming environment: Python language, Pycharm.This section compares the performance of the CPP algorithm, enhanced DLS algorithm, and RS algorithm by analyzing the running times of the algorithm, the change of score value, and data availability. The following can be seen from Figures4 and 5: (1) The running time of the three algorithms increases with the increase of the privacy protection threshold k. The running time of the CPP algorithm is between the RS algorithm and the enhanced DLS algorithm. The running time of the enhanced DLS algorithm changes significantly with the increase of k, and the running time of the RS algorithm is the smallest and tends to be stable. The enhanced DLS algorithm should consider the influence of the query probability and the entropy when selecting generalized locations, and the running time will be increased with the number of generalized locations, The CPP algorithm saves the running time by proposing a reasonable and effective location search algorithm. (2) The score value measures the degree of dispersion between locations and the distance between the anonymous trajectory and the original trajectory.Figure 4
Change situation of running time.
(a)
Gowalla(b)
BrightkiteFigure 5
Change situation of score value.
(a)
Gowalla(b)
BrightkiteWhen the score value is larger, it means that the selected generalized location and sensitive check-in location are more dispersed, and the distance between the generalized trajectory and the real trajectory is closer. With the increase of the privacy protection thresholdk, the score of the three algorithms increases significantly. The CPP algorithm has the better performance in score value because the CPP algorithm uses the heuristic rules to select each generalization location, and it ensures that each selected generalized location can keep the maximum score value. However, the random selection of each generalized location will lead to uncertainty, and the size of the score value to be unstable. When the order of magnitude of score value is too large, this paper uses the logarithm of score value to express it.The availability of measurement data can be evaluated from three aspects: the change of user trajectory pattern, the change of access location type, and the change of access location points. The following can be seen from Figures6–8:
(1)
According to the position type transition probability difference before and after anonymity of the trajectory pattern matrix, it can be divided into four intervals:0~10−9,10−9~10−7,10−7~10−5,>10−5, counting the quantity distribution of each interval. The probability difference greater than 98% in the CPP algorithm falls in the 0~10−9 interval, and it shows that the change of location type transition probability is small, the similarity of the trajectory pattern matrix before and after anonymity is high, while the performance of enhanced DLS algorithm and RS algorithm is lower than that of CPP algorithm. The similarity of the trajectory pattern matrix before and after anonymity is high, and the performance of the enhanced DLS algorithm and RS algorithm is lower than the CPP algorithm(2)
The Changes in the Type of User Access Location. The total number of original location types visited by a user is 38. It can be seen from the figure that the number of access location types of the CPP algorithm changes little with the increasing of the k, and the algorithm will not generate new location types. The access location type of the enhanced DLS algorithm increases gradually as the increasing value of the k, while the number of access location types of the RS algorithm changes significantly with the increasing of the k. Because the CPP algorithm recommends the location type for the user according to the user’s trajectory pattern, the generalized location selected by the random method is uncertain, and the location type of the generalized location will exceed the range of the user’s original access location type.(3)
For the user’s access location change index, set the number of user visits to each access location before generalization asni, and after generalization, the number of user visits to each location becomes ni′; the change in the number of visits for each location is defined as Δni=∣ni−ni′∣. Set a standard number threshold N and a location set S, and put the locations with the change of the number of visits greater than or equal to the standard number threshold into the set S, symbolized as S=li∣Δni≥N. The value of ∣S∣ represents the number of position points in the set S. The smaller the value of ∣S∣, the more stable the number of visits of the user to each access location after anonymity, and the better anonymity. It can be seen from Figure 8 that the CPP algorithm proposed in this paper has the smallest ∣S∣ value, which is much lower than the other two algorithms, so the anonymous protection effect is the best. The RS algorithm is easy to generate new locations when selecting generalized locations, and the number of new locations is uncertain, so the ∣S∣ value is largerFigure 6
Distribution situation of probability change.
(a)
Gowalla(b)
BrightkiteFigure 7
Change situation of location types.
(a)
Gowalla(b)
BrightkiteFigure 8
Change situation of specific location.
(a)
Gowalla(b)
Brightkite


## 6. Conclusion

In this paper, a check-in privacy protection algorithm based on check-in location generalization for sensitive check-in protection is proposed for the first time and can be applied to blockchain transactions to solve the privacy protection problem of transaction users’ sensitive information. Considering the user’s trajectory pattern factor, the algorithm recommends the location type of the generalized check-in location for the user and selects generalized locations that can ensure the minimum change of trajectory pattern. Experimental research based on real check-in data sets shows that the CPP algorithm can effectively protect the sensitive check-ins in the trajectory, greatly reduce the probability of the attacker identifying the real sensitive check-ins, and maintain the high availability of the trajectory pattern data. This method is suitable for protecting the location in the area with dense geographical density. However, thek-anonymity method may not be implemented in areas with sparse geographical density. The solution to the above problem needs to be further studied.



---

*Source: 9358531-2022-03-15.xml*