Dual-Resolution Friend Locator System With Privacy Enhancement Through Polygon Decomposition

Online social networks have become increasingly popular. One of the interesting applications is the friend locator, in which the application server informs a user through a mobile device if some of his/her listed friends are close enough in terms of geographical locations. However, in such services, it is challenging to protect the privacy of the individual users. Previous solutions for the friend locator do not guarantee a high level of privacy and do not maintain efficiency. In this paper, we propose a dual-resolution system structure to guarantee both strong privacy and efficiency. Additionally, we use the polygon decomposition method to achieve both accuracy and flexibility. To be more specific, in the coarse resolution level, each regular mobile user uploads his/her encrypted coarse location information to a central server periodically for comparisons. If a regular mobile user is found to be in the same grid block as an active mobile user, then the friend locator procedure with a higher resolution level will be conducted. Finally, through numerical analysis and simulations, we show that the proposed system design and algorithm can achieve high privacy, efficiency, accuracy, and flexibility.