1.

INTRODUCTION

In the environment of the interconnection of all things, the rapid development of mobile communication technology and mobile computing have made earth shaking changes in people’s life. Mobile devices capable of networked communication can freely send and receive data in a wireless environment, which brings users a convenient and fast service experience. In recent years, mobile smart devices have become a standard configuration for urban residents. Mobile phones, tablets and smart mobile wearable devices such as smart watches have become an indispensable part of people’s modern life. Many mobile phone giants have launched their own mobile smart wearable devices and iterated quickly, such as apple, Huawei, Xiaomi and so on. According to the statistics of well-known research institute strategy analytics¹, in the second quarter of 2021 alone, the global shipment of smart watches has reached 18 million units, and the global shipment of smart phones is 314.2 million. It can be seen that mobile smart devices have penetrated into thousands of households. At the same time, according to the latest research report of Emarketer², in 2020, the average time spent on mobile phones by Chinese people will reach 3 hours and 16 minutes a day, and that of Americans will reach 3 hours and 10 minutes a day, which is enough to say that mobile smart devices have established a solid and inseparable relationship with human daily life. The user carries the smart device with him. According to the data obtained by the sensor of the smart device, the user can determine his location in real time, and then use it to interact with the location-based service application^3-4, This kind of location-based service (LBS) has brought people a convenient and practical user experience and is deeply favoured by users. Additionally, location information is useful for some commercial applications. For example, the number of electric vehicles at charging piles could be used to support business decision. However, electric vehicle location may contain personal private information, which cannot be collected directly.

Differential privacy mechanism based on distance measurement is one of the main methods of differential privacy in geographic location privacy protection. ε-Geo-indistinguishability as the de facto standard of local differential privacy geographic location protection scheme using distance measurement, the Plane Laplace mechanism to realize its requirements has become the basis of the existing local differential privacy protection mechanism based on distance measurement. Researchers at home and abroad have made many improvements to its original definition and put forward many meaningful schemes For example, in terms of utility, a new randomization algorithm based on linear programming technology is proposed in⁵ In terms of the correlation between individual user locations in the set of repeated locations, Lan et al.⁶ introduced an R-tree, which caches previously published confusion locations for reuse in future versions⁷ Another method combined with relevance is introduced by Zhang et al.⁸, which can reduce the consumption of privacy budget and improve the degree of privacy protection by replacing the actual location with the previously published predicted location.

The Utility-Optimized Local Differential Privacy (ULDP)⁹ proposed by Murakami provides us with an inspiration, that is, the existing researchers have not noticed a common fact, that is, different geographical locations have different sensitivities and different privacy protection needs. Combining the ideas of ε-Geo-indistinguishability and Utility-Optimized Local Differential Privacy, we propose a differential privacy concept called Utility-Optimized- ε -Geo- indistinguishability which meets the different degrees of privacy protection in different geographical locations. And we propose a localized differential privacy mechanism called Utility-Optimized Planar Laplace Mechanism (UPL).

The content of this paper is arranged as follows. Section I introduces relevant work at home and abroad; Section II introduces the preparatory knowledge required; Section III proposes Utility-Optimized-ε-Geo-indistinguishability and its implementation mechanism UPL; Section IV compares UPL with existing mechanisms through experiments; Section V summarizes and prospects.

2.

PRELIMINARIES

Please follow these instructions as carefully as possible so all articles within a conference have the same style to the title page. This paragraph follows a section title so it should not be indented.

2.1

Differential privacy

Differential privacy¹⁰ is defined by Dwork as a formal and provable privacy guarantee. The idea of this mechanism is that the aggregation results calculated for the dataset should be almost the same whether there is a single element in the dataset or not. In other words, the addition or deletion of a single element should not significantly change the probability of any result of the aggregation function. The differential privacy model assumes that the attacker has the maximum background knowledge and the maximum attack ability, and gives a rigorous and quantitative representation and proof of the risk of privacy disclosure, which is defined as follows.

A randomization mechanism 𝓜: D → O satisfies ε −Differential Privacy, if and only if, for any two adjacent data sets D and D′ with only one record difference and any possible output o ∈ O, the following inequality is satisfied:

2.2

Local differential privacy

The differential privacy technology using centralized architecture is called Centralized Differential Privacy (CDP). These methods need a trusted third party to collect users’ data and add noise to them for disturbance processing to ensure users’ data privacy, but this assumption is unrealistic in practical application. In this context, Local Differential Privacy (LDP)¹¹ is proposed and widely used. In LDP, users add noise to their original data locally, and then send the disturbed data to the data collector for further processing. The model has good practicability without the participation of a trusted third party. At the same time, the user’s real data is not local, which can ensure the user’s data privacy. The formal definition of LDP is as follows.

Given the input set X, the output set Y, any x，x′ ∈ X，y ∈ Y, the randomization mechanism 𝓜 is ε - LDP, if it satisfies

2.4

Geo-indistinguishability

ε-Geo-indistinguishability¹² is a privacy concept for geographic location data privacy protection proposed by Andres et al. It believes that the privacy protection level of user data should be related to distance. This concept is an extension of the traditional differential privacy. The core idea is that within the specified range, the user’s real geographical location and approximate location are indistinguishable. Its formal definition is as follows.

Given the geographic location data set X, the data set output after being disturbed by the randomization scrambling mechanism 𝓜 is Z, if the randomization mechanism 𝓜 is satisfied ε-Geo-indistinguishability, then for anyx, x′ ∈ X,z ∈ Z, and the Euclidean distance d (x, x′) ≤ d_max，d_max is the protection scope of the mechanism:

where 𝓜 (x) (z) represents the probability of inputting position point x to mechanism 𝓜 to obtain position point z, ε is the budget for privacy protection.

3.

MECHANISM DESIGN

The existing scheme does not take into account the fact that different geographical locations have different sensitivities and different privacy protection needs. To solve this problem, we propose Utility-Optimized-ε-Geo-indistinguishability. Further, we propose its implementation mechanism called Utility-Optimized Planar Laplace Mechanism (UPL). The mechanism divides the geographical location into sensitive areas and non-sensitive areas to provide better utility.

4.

EXPERIMENT

The data sets used in the experiment are yelp Las Vegas data set and the generated uniform data set.

We compare the utility optimized planar Laplacian mechanism UPL with Laplacian mechanism LM and planar Laplacian mechanism PL in the above data sets. The experimental index is utility, i.e., MSE:

We set that there is only one sensitive area and it is located at the center of the two-dimensional plane. The side length of the sensitive area is 1/2 of the side length of the whole area. We take the privacy budget ε range of 5 to 20 as the abscissa of the experiment results. The results are shown in Figure 1. Affected by the real geographical distribution, the curves of the three experimental results are slightly different, but it can be found that the effect of UPL is always better than LM and PL.

Figure 1.

Experimental comparison of mechanism in each data set.

There are usually multiple sensitive areas in the real geographical location plane. Therefore, next, we conduct experiments on the situation that there are multiple sensitive regions in two-dimensional plane region. We set the number of sensitive areas n as 6, and the side length of each sensitive area is 1/8 of the side length of the whole area. The location of the sensitive area is randomly distributed. Repeat the calculation for 10 times and take the average value. The experimental results on the Yelp dataset are shown in Figure 2. It can be seen that in the case of multi sensitive regions, the utility of UPL is still better than other mechanisms.

Figure 2.

Experimental comparison of various mechanisms in the case of multiple sensitive regions.

5.

CONCLUSION

This paper extends the previous research work, first puts forward Utility-Optimized-ε-Geo-indistinguishability, and then designs Utility-Optimized Planar Laplace Mechanism. Theoretical analysis and experiments based on real geographic location data sets show that UPL meets the geographic location indistinguishability of utility optimization, and it is better than other geographic location protection mechanisms that meet the geographic location indistinguishability.