Artificial Impostors: An Efficient and Scalable Scheme for Location Privacy Preservation

The progress of location-based services has led to severe concerns about location privacy leakage. However, existing methods are still incompetent for efficient and scalable location privacy preservation (LPP). They are often vulnerable to inference attacks with side information, or hard to be implemented due to the high computational complexity. In this paper, we pursue the high protection quality with low computational complexity. We propose a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">scalable</i> LPP method based on the paradigm of counterfeiting locations. To make fake locations extremely plausible, we forge them by synthesizing <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">artificial impostors</i>. The so-called artificial impostors refer to the synthesized traces that have similar semantic features to the actual traces, e.g., similar transition patterns, and do not contain any <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">protected location</i>, i.e., the exact location that needs to be protected. We devise two dedicated techniques: the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">station-based synthesis method</i> and the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">population-level semantic model</i>. We conduct the experiments on real datasets of two cities (Shanghai of China and Asturias of Spain) to validate the quality of privacy preservation, utility loss, and scalability of the proposed method. Based on these two datasets, the experimental results show that our method achieves the privacy preservation quality of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$97.68\%$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$96.24\%$</tex-math></inline-formula>, respectively, and the time spent on building generators is only 144.96 seconds and 136.08 seconds, respectively. The experimental results also show that our method achieves a good trade-off between privacy and utility. Our study would give the research community new insights into improving the practicality of LPP paradigm via counterfeiting locations.