Non-Exposure Location Anonymity

Abstract

Location cloaking has been proposed and well studied to protect user privacy. It blurs the accurate user location (i.e., a point with coordinates) and replaces it with a well-shaped cloaked region (usually a circle or a rectangle). However, to obtain such a cloaked region, all existing cloaking algorithms require to know the accurate locations of all users. Since such information is exactly what the user wants to hide, these algorithms can work only if all parties involved in the cloaking process are trusted. However, in practice this assumption rarely holds as any of these parties could be malicious. Therefore, location cloaking without exposing the accurate user location to any party is urgently needed. In this paper, we present such a non-exposure cloaking algorithm. It is designed for k-anonymity and cloaking is performed based on the proximity information among mobile users, instead of directly on their coordinates. We decompose the problem into two subproblems --- proximity minimum k-clustering and secure bounding, and develop distributed algorithms for both of them. Experimental results consistently show that these algorithms are efficient and robust under various proximity topologies and system settings.