A Differential Privacy Protection Protocol Based on Location Entropy

When a user initiates a request for assistance, selecting $k$ neighboring users, whose reputation scores are greater than $W_{\min }$ within $\delta$ to construct anonymity set, then, set the location similarity of the user $i$ as $P_i$ and the reputation as $W_i$ , then the reliability $h_i$ of auxiliary user can be expressed as

(5) $$h_i=-\underset{i=1}{\overset{k}{\sum }}{W}_i\times P_i\times \log P_i$$

where $W_i$ represents the latest reputation score of node $i$ .

The requesting user uses the anonymity set LE value as the selection condition for users to participate in anonymous assistance. The larger the LE value, the higher the reputation of the anonymity set assistance user and the higher the similarity to the query of the requesting user. On the contrary, anonymous sets are less reliable, and it is more likely to maliciously disclose the real location of the requesting user. The main steps are as follows shown in Algorithm 1:

Step 1: Record the total amount of a certain query category of the user as $E_q$ and the total amount of all query categories as $E_q(C_q={\sum }_{i-1}^n{E}_q)$ ,

(6) $$P_i=E_q/C_q$$

where $P_i$ represents the probability of querying a certain category, where $i=1,2,\mathrm{\dots },n$ ( $n$ is the total of query categories).

Step 2: Rank $P_i$ and $W_i$ from large to small, and then select the top $k$ users in $Q_i$ and $W_i$ (total $2k$ ) as the candidate set $C_m$ , where $m=1,2,\mathrm{\dots },2k$ .

Step 3: Do $m$ operations on $C_m$ , each operation selects $k-1$ users to constract anonymous set $C_j$ ( $j=1,2,\mathrm{\dots },K$ ) with request users, and then calculate $h_i$ by Eq. ( 5 ).

Step 4: Select the anonymous set with the largest $h_i$ and return it to the requesting user to submit a location query.

When the number of assisted users within the maximum anonymity radius $r$ is less than $k$ , the DP protection requires the addition of a noise mechanism. In this study, an anonymous point is constructed by adding noise that conforms to the Laplace distribution to achieve $ϵ$ -DP protection, the privacy budget parameter $ϵ$ indicates the degree of privacy protection, the smaller the value, the higher the degree of privacy protection.

Definition 6 If the probability density function distribution of a random variable is $f(x\Vert \mu ,b)=1/2b\times \exp (-|x-\mu |/b)$ , where $\mu$ is the positional parameter, then is the Laplace distribution.

For anonymous points, the protocol in this study treats longitude and latitude independently, and generates a longitude and latitude that are indistinguishable within the privacy budget parameters, which are recorded as anonymous points $L_a(x_a,y_a)$ . According to Definition 1, by setting the position parameter $\mu =0$ , the latitude and longitude of the anonymous point should meet the following conditions, as shown in Algorithm 2.

(7) $$Pr(x_a)=1/2b_x\times \exp (x_a/b_x),$$ $$Pr(y_a)=1/2b_y\times \exp (y_a/b_y)$$

(8) $$b_x=\bar{x}/ϵ,b_y=\bar{y}/ϵ,$$ $$\bar{x}=1/K{\displaystyle \underset{j=1}{\overset{K}{\sum }}}{x}_j,\bar{y}=1/K{\displaystyle \underset{j=1}{\overset{K}{\sum }}}{y}_j$$

Step 1: Calculate $\bar{x}=\mathrm{average}(C_{Kx})$ and $\bar{y}=\mathrm{average}(C_{Ky})$ .

Step 2: Calculate $b_x=\bar{x}/ϵ$ and $b_y=\bar{y}/ϵ.$

Step 3: Calculate anonymous point results $L_a=(b_x,b_y).$

When a user initiates a request for assistance, selecting $k$ neighboring users, whose reputation scores are greater than $W_{\min }$ within $\delta$ to construct anonymity set, then, set the location similarity of the user $i$ as $P_i$ and the reputation as $W_i$ , then the reliability $h_i$ of auxiliary user can be expressed as

(5) $$h_i=-\underset{i=1}{\overset{k}{\sum }}{W}_i\times P_i\times \log P_i$$

where $W_i$ represents the latest reputation score of node $i$ .

The requesting user uses the anonymity set LE value as the selection condition for users to participate in anonymous assistance. The larger the LE value, the higher the reputation of the anonymity set assistance user and the higher the similarity to the query of the requesting user. On the contrary, anonymous sets are less reliable, and it is more likely to maliciously disclose the real location of the requesting user. The main steps are as follows shown in Algorithm 1:

Step 1: Record the total amount of a certain query category of the user as $E_q$ and the total amount of all query categories as $E_q(C_q={\sum }_{i-1}^n{E}_q)$ ,

(6) $$P_i=E_q/C_q$$

where $P_i$ represents the probability of querying a certain category, where $i=1,2,\mathrm{\dots },n$ ( $n$ is the total of query categories).

Step 2: Rank $P_i$ and $W_i$ from large to small, and then select the top $k$ users in $Q_i$ and $W_i$ (total $2k$ ) as the candidate set $C_m$ , where $m=1,2,\mathrm{\dots },2k$ .

Step 3: Do $m$ operations on $C_m$ , each operation selects $k-1$ users to constract anonymous set $C_j$ ( $j=1,2,\mathrm{\dots },K$ ) with request users, and then calculate $h_i$ by Eq. ( 5 ).

Step 4: Select the anonymous set with the largest $h_i$ and return it to the requesting user to submit a location query.

When the number of assisted users within the maximum anonymity radius $r$ is less than $k$ , the DP protection requires the addition of a noise mechanism. In this study, an anonymous point is constructed by adding noise that conforms to the Laplace distribution to achieve $ϵ$ -DP protection, the privacy budget parameter $ϵ$ indicates the degree of privacy protection, the smaller the value, the higher the degree of privacy protection.

Definition 6 If the probability density function distribution of a random variable is $f(x\Vert \mu ,b)=1/2b\times \exp (-|x-\mu |/b)$ , where $\mu$ is the positional parameter, then is the Laplace distribution.

For anonymous points, the protocol in this study treats longitude and latitude independently, and generates a longitude and latitude that are indistinguishable within the privacy budget parameters, which are recorded as anonymous points $L_a(x_a,y_a)$ . According to Definition 1, by setting the position parameter $\mu =0$ , the latitude and longitude of the anonymous point should meet the following conditions, as shown in Algorithm 2.

(7) $$Pr(x_a)=1/2b_x\times \exp (x_a/b_x),$$ $$Pr(y_a)=1/2b_y\times \exp (y_a/b_y)$$

(8) $$b_x=\bar{x}/ϵ,b_y=\bar{y}/ϵ,$$ $$\bar{x}=1/K{\displaystyle \underset{j=1}{\overset{K}{\sum }}}{x}_j,\bar{y}=1/K{\displaystyle \underset{j=1}{\overset{K}{\sum }}}{y}_j$$

Step 1: Calculate $\bar{x}=\mathrm{average}(C_{Kx})$ and $\bar{y}=\mathrm{average}(C_{Ky})$ .

Step 2: Calculate $b_x=\bar{x}/ϵ$ and $b_y=\bar{y}/ϵ.$

Step 3: Calculate anonymous point results $L_a=(b_x,b_y).$

When a user successfully constructs an anonymous set to submit a query, the user’s privacy needs are met, but the privacy of the user’s location data must also be ensured at the same time as the data availability. In this section, we construct a query-result graph based on a directed graph. The LSP applies the shortest path algorithm^{[ 43 ]} idea to further filter and process the query results and finally returns the optimal query results to the requesting user (see Fig. 4 ), as shown in Algorithm 3.

10.26599/TST.2022.9010003.F004 Fig. 4Weighted directed graph of query results.

Query result processing:

Step 1: Request user $r_1$ to successfully construct an anonymous set $As=(i{d}^{\prime },L,data)$ , where $L$ is the current location of requesting user $r_1$ and $k-1$ assisting user geographic location sets, data is the content of the submitted query.

Step 2: After receiving the query-request, the server obtains the query result set $Sq=(i{d}_1^{\prime },l_1),$ $(i{d}_2^{\prime },l_2),$ $(i{d}_3^{\prime },l_3),\mathrm{\dots },(i{d}_k^{\prime },l_k)$ according to the anonymous set. Constructing a digraph between the query result and anonymous point, the weights of the edges in digraph are the distance between users.

We find the result with the smallest sum of the distance from the anonymous set position and return it as the exact query result (Dijkstra seeks the shortest path problem), the solution process is shown in Table 1 .

As we can see, we find the sum of the distances $(L_1,r_1),(L_1,r_2,),$ and $(L_1,r_3)$ are the smallest, so $L_1$ can be returned as the optimal result to the requesting users $r_1,r_2,$ and $r_3$ .