As location-based services (LBSs) on smartphones become increasingly popular, such services are causing serious privacy concerns, because many users are unwilling to see their location information leaked to service providers. Recently, in order to protect users' location privacy, researchers have introduced geo-indistinguishability, the first specialized privacy model for LBSs that can provide provable privacy guarantees. Intuitively, geo-indistinguishability means that through perturbation, any two locations within a given distance produce observations with similar distributions, and thus, attackers have no way to learn users' real locations. However, even if geo-indistinguishability is achieved, there remains a significant threat to users' location privacy: the privacy consumption increases with the number of queries for the existing geo-indistinguishable location perturbation mechanism, and therefore, there is a high risk of privacy violation when the number of queries is not small. In this paper, we enhance the privacy protection for LBSs by proposing an improved geo-indistinguishable mechanism. It can reduce the privacy costs to almost 0 when the user's location satisfies a condition. We also present an improvement to further reduce the privacy costs when the above condition is not satisfied. Evaluations upon two public trace data sets show that the proposed mechanisms can dramatically save the privacy budget and thus support much more queries. The results also show that the proposed mechanisms are efficient, and their performance is controllable.
In the original geo-indistinguishable mechanism , a user chooses another perturbation location in the area according to a distribution and reports the chosen location directly. Due to the property of planar laplacian, the privacy cost incurred by this mechanism should be exact the privacy parameter ? for each query, and the privacy costs increase linearly with the number of queries.
When applied to multiple queries, planar laplacian may not work well. The whole privacy budget will be quickly consumed if the user performs a large number of queries. Our goal is to design an improved mechanism that satisfies geo- indistinguishability and can significantly improve the number of queries given a specific privacy budget (the privacy cost of one query approaches 0 in most cases). Below we first define privacy cost for each query based on the concept of differential privacy.
our mechanism generates a number of cells at the first step. To improve the flexibility of our mechanism, every user needs an independent cell layout, because the areas of interest (AOI) are various among different users and many LBSs allow users to customize their areas of retrieval (AOR) so that users’ accuracy requirements could be satisfied. In addition, the larger the cell is, the less the privacy cost consume. Some users also want to reduce their privacy costs by using larger cells.
As a result, different users need different choices of the size of cells. In our design, the cell layouts are generated by the LBS servers, because it may be unaffordable for a mobile user to generate its own layout when the geographic information is massive. If the LBS server just simply generates an indepen- dent cell layout for each user, the cost of generating such various cell layouts may be very huge.
one of the technical challenges is how to determine which area p falls into. Here, we assume that all the cells are hexagons with the same size and do not overlap each other
However, when the entire region is large and the cells are small, it may not be practical to adopt such a brute-force approach. Therefore, we propose a method that is based on the geometric properties.
Recently, in order to protect users’ location privacy, researchers have introduced geo-indistinguishability, the first specialized privacy model for LBSs that can provide provable privacy guarantees. Intuitively, geo-indistinguishability means that through pertur- bation, any two locations within a given distance produce observations with similar distributions, and thus, attackers have no way to learn users’ real locations.
However, even if geo- indistinguishability is achieved, there remains a significant threat to users’ location privacy: the privacy consumption increases with the number of queries for the existing geo-indistinguishable location perturbation mechanism, and therefore, there is a high risk of privacy violation when the number of queries is not small.
We propose an improved geo-indistinguishable location perturbation mechanism for LBSs to support multiple queries. It divides the target space into cell layouts for users and guarantees that when the users are not close to the cell borderlines, the privacy consumption of each query approaches 0. For those close to the border, although the privacy consumption rises quickly, it is still confined below that of the existing mechanism. As a result, our proposal could significantly increase the number of queries given the same privacy budget. What’s more, the errors of the reported locations are confined below the cell radius. 2) 3)
Next, we present an improvement to further reduce the privacy consumption when users are within border areas. Its basic idea is to dynamically adjust the cell size according to the user movement. After applying this mechanism, the privacy consumption can be also reduced to almost 0 when the users are moving insider the border areas.
We have conducted extensive experiments based on two widely-used real-world datasets. We evaluate the privacy cost of the proposed mechanisms when users are in both stationary and moving scenarios. We also examine the utility that the proposed mechanisms can provide and the time efficiency of them. The results demonstrate that our mechanisms can significantly reduce the privacy cost in various cases. Furthermore, controllable utility and time efficiency are also provided.
In this paper, we have proposed an improved geo- indistinguishable location perturbation mechanism for LBSs which can significantly reduce the privacy cost so that support multiple queries. Then, based on the basic mechanism, we present an enhanced mechanism, which can further reduce privacy consumption when users are approaching the border- lines of cells.
We use rigorous proof and extensive exper- iments to validate the geo-indistinguishability and evaluate the performance of the proposed mechanisms, respectively. Results show that the proposed mechanisms can support much more queries than the baseline mechanisms with the control- lable utility. Furthermore, our mechanisms are also efficient.