# An Efficient Approach for LBS Privacy Preservation in Mobile Social Networks
## 1 Introduction  
Due to the rapid advance of mobile communication technologies and modern smart mobiles, location-based service (LBS) has become ubiquitous in recent years. With positioning technologies and applications loaded on smart mobiles, users could query location-based service providers (LBSP) for personalized services according to their locations, such as finding the nearest restaurant, getting a travel guide, or searching for a nearby market, etc. Although location-based service brings convenience to users and plays an increasingly important role in daily life, people are also aware that their private information may be revealed along with the services provided by LBSP. Hence, the problem of privacy leakage has become a main factor that hinders the further development of LBS. Therefore, how to protect users' privacy information while providing conventional services to users has become a topic of major interest. Generally speaking, current popular applications on smart phones can be roughly divided into two categories. One is to hide the \"who\" aspect completely for LBSP, and just uses the service with \"what\" and \"where\", such as AMAP. Another is not to hide the \"who\" for LBSP, and uses the service with \"who\", \"what\", and \"where\", such as Dianping. Here, \"who\" means the identity of a user, \"where\" means the location of a user, and \"what\" means the preference of a user. For the wide application of LBS, users' sensitive information (i.e., \"who\", \"where\", \"what\") should be protectedwell while interacting with LBSP. For the aspect of \"who\", security techniques such as pseudo-ID [1] and pseudonym are usually used to make users' real identity indistinguishable, but it is insufficient to protect users' sensitive information [2]. For the aspect of \"what\", exposure of a user's preference may result in the leakage of his sensitive information. For example, if [PERSON] often sends some requests about the knowledge of coronary disease to LBSP, then LBSP or adversary could infer that [PERSON] or his family members may have a health problem of coronary disease. For the aspect of \"where\", if [PERSON] often reveals his locations close to a hospital when sending his requests to LBSP, adversary or LBSP may also infer that [PERSON] may have some health problems. If this sensitive information is leaked, some commercial organizations or adversary may send drug ads to [PERSON] frequently. To address the problem of leaking users' privacy caused by location information, k-anonymity as a classic scheme was proposed. k-anonymity is an anonymity set which is composed of users with different locations, and makes one user's location indistinguishable from the locations of at least k-1 other users at some point [3]. For example, there are \(k\) users simultaneously requesting LBSP. But k-anonymity is insufficient to guarantee users' preference privacy when they request the same preference service in LBS query. There are at least two attacks, the Homogeneity Attack and Background Knowledge Attack, that can be used to compromise a anonymity set [4]. In order to overcome this deficiency, the concept of \(l\)-diversity, which ensures at least \(l\) well-represented values in each equivalence class, was proposed to protect users' privacy. Figure 1 shows the way to protect users' privacy by k-anonymity and \(l\)-diversity. There are 6 users (i.e., \(k=6\)) who are distributed in different locations requesting 4 different services (i.e., \(l=4\)), and LBSP cannot link a specific service to a specific user. There are many studies adopt both k-anonymity and l-diversity to protect personal privacy in LBS query. For example, the authors [5] proposed a Dummy-Location-Selection (DLS) algorithm to protect location privacy and preference privacy. The paper [6] used Snet-Hierarchy to protect personal privacy by k-anonymity and l-diversity.