# A Search Efficient Privacy-Preserving Location-Sharing Scheme in Mobile Online Social Networks
## 2 Related Work  
With the increasing prevalence of mobile devices, especially smartphones, mOSNs have gone through rapid development [13; 14]. Location-sharing, as an increasingly important service in mOSNs, brings people great convenience. However, the privacy issues caused by location-sharing also become an urgent problem [15]. To address this issue, many privacy-preserving methods such as k-anonymity [16], dummy [17], and spatial cloaking [18] have been widely adopted. The security and system efficiency are the important two aspects in location-sharing systems. Therefore, the current location-sharing solutions are introduced based on the two aspects mentioned above. Many solutions have been proposed to protect users' sensitive information such as identities and locations. For example, [PERSON] et al. [7] pointed out that users' real identities may be leaked to the location server during location-sharing services. Thus, they proposed a security mechanism named MobiShare+ which employed dummy queries to protect identity privacy. [PERSON] et al. [19] used a broadcast form to query the information of friends nearby and introduced a new cryptography primitive called the functional pseudonym to protect users' identity information. To overcome the privacy threat caused by users' co-location information, [PERSON] et al. [20] proposed a game-theoretic framework to explore the relationship between users' behaviors and locations. [PERSON] et al. [21] stated that users may provide inaccurate positioning data in location-sharing systems. Hence, they designed an attack method to reveal the shortcomings of protecting location privacy in existing location-sharing mechanisms. Recently, to prevent the disclosure of users' identities caused by users' threshold distances, [PERSON] et al. [22] have proposed a secure distance comparison protocol by the paillier encryption. However, the above solutions mainly focus on the basic security requirements in location-sharing systems such as protecting users' identity privacy and location privacy, but can not meet user-defined privacy-preserving requirements. To resist attacks from friends, [PERSON] et al. [10] created a user-defined access control policy which can allow a user to determine whether to share a location with part of his/her friends. However, the above access control policy is aimed at some trust-less friends but not some sensitive areas. If the user has a privacy-preserving requirement for some geofences such as the workplace, the user has to set the access control policy to all his/her friends each time when the user is in these geofences. Similarly, when the user moves to other places and wants to use location-sharing services, the user has to reset the access control policy. Therefore, in terms of the privacy-preserving requirements for sensitive areas, the above access control policy is not flexible enough. While maintaining users' privacy, some schemes are proposed to improve the efficiency of location-sharing systems. For example, the location update database is adopted in paper [6] to improve search efficiency and reduce the time of finding users' locations. However, the location update database brings a great storage burden. In order to increase the transmission efficiency, [PERSON] et al. [9] proposed a scheme named B-Mobishare and used Bloom Filter to filter the sensitive data in the transmission between the social network server and the location server. However, B-Mobishare suffers a high time cost and computational overhead. To prevent the location server from getting users' complete social network relationships, [PERSON] et al. [11] designed a new architecture with multiple location servers, which also can increase the computing power of distance calculation and comparison. Unfortunately, multiple location servers mean an increase in hardware costs. To enhance the efficiency of data transmission, [PERSON] et al. [12] proposed a centralized location-sharing system that integrates the social network server and the location server into one server.