Research On Private Proximity Testing Based On Grid In Mobile Social Networks

As a basic one of location-based services, proximity testing can help mobile users find nearby friends. In recent years, it has been widely used in people’s daily lives, meanwhile, its hidden location privacy problem has gradually arisen privay concern, which is because proximity testing requires users to submit their locations to the location server, and the leakage of location information will pose a great threat to user’ location privacy. However, most existing schemes protect the locations at the expense of costing large amounts of CPU and memory, which ignore the quality of proximity testing service and reduce its applicability. Therefore, we aims to study the private proximity testing algorithms based on grids that not only protect the location privacy but also guarantee the service quality.In this paper, according to the characteristic and application of grids in protecting location information, we propose the private proximity testing algorithm based on’one degree’grid (ODG).’One degree’grid refers to a random 1° (longitude)×1°(latitude) grid region on the map. The ODG algorithm reduces the testing zone to’one degree’ grid, transforms users’location information into irrelevant grid serial numbers, and then makes use of set inclusion and the irreversibility of hash function to test the proximity without disclosing the location privacy. In order to investigate the ODG algorithm, we define the system model, describe the establishment of’one degree’grid and the implenmentation of the algorihm in detail, and analyze the security and efficiency of ODG. In addition, we make simulation experiments for studying the performance of ODG, as well as the classical grid testing algorithm VicintiyLocator, and the results show our algorithm is better than the performance of Vicinity Locator.However, there are still some shortcomings in the ODG algorithm. For example, the establishment process of’one degree’grid is cumbersome, and friends do not share the same location privacy protection with users. To eliminate these shortcomings, we further propose the private proximity testing algorithm based on reference point (RefP). RefP algorithm simplies the’one degree’grid to a reference point, which omits the establishment of’one degree’grid. Besides, friends can define their detected regions according to their privacy protection preference for locations. In addition, friends do not need to execute the hash function, which greatly reduces the CPU costs. Through the theoretical analysis and simulation experiments, we compare the ODG and RefP algorithms. The results show that the performance of RefP is superior to ODG.Finally, we develop an iOS application based on RefP algorithm. The analysis of the performance of the application futher demonstrates the effectiveness and stability of RefP algorithm.