# A Search Efficient Privacy-Preserving Location-Sharing Scheme in Mobile Online Social Networks
## 1 Introduction  
The rapid advance of mobile communication technologies and modern smart mobiles is changing the way people socialize [1; 2]. Fresh social paradigms named mobile online social networks (mOSNs) have become ubiquitous in recent years. In addition to providing regular services such as sharing pictures, status, and moods on traditional web-based social networks, mOSNs also supply new services such as searching Points of Interests (POIs), querying for nearby friends and so on, which offer users much convenience. Location-based service (LBS), one of the most important components in mOSNs, plays an increasingly significant role in daily life [3; 4]. With the help of network access service and positioning techniques (e.g., Global Positioning System (GPS) and cellular tower geolocation service) of mobile devices, many applications of LBS have been proposed, such as location-based mobile service recommendations and check-in games like Foursquare. LBS promotes the change from traditional social networks to mobile social networks and makes real-time location-sharing services a reality. Due to the convenience brought by real-time location-sharing services, users can enjoy a better experience by updating their real-time location information. However, some security issues, especially location privacy, have become the focus of users. It is important to prevent personal location information from being obtained by malicious attackers since users' geographical locations are a very sensitive factor that is related to the spatial and contextual information about users. For example, users' job and housing locations may be inferred from public records of bicycle renting stations [5]. By collecting and analyzing the social and location-related information, adversaries can infer users' crucial privacy information such as users' preferences, faiths, and physical conditions. Some criminals may even launch personal tracking attacks after grasping users' privacy information. Without the guarantee of privacy, users may not be willing to share their location information. Therefore, how to protect users' privacy, especially in real-time location-sharing services, is one of the main challenges at present. Fortunately, some solutions have been put forward on this issue. [PERSON] et al. [6] proposed a location-sharing system, named MobiShare, to protect users' location privacy for friends' and strangers' queries in location-sharing applications. Then, to prevent a third-party such as the location server from learning users' sensitive information, [PERSON] et al. [7] proposed a series of privacy interaction protocols to reduce security risks. Subsequently, a solution, called N-Mobishare, was introduced by [PERSON] et al. [8] to preserve users' location and social information via the social network server and the location server respectively. Afterwards, [PERSON] et al. [9] put forward a scheme named B-Mobishare that used Bloom Filter to improve the efficiency of privacy interaction protocols proposed in [7]. To prevent the disclosure of users' privacy in social networks and improve the flexibility of privacy protection, [PERSON] et al. [10] designed a user-defined location-sharing system. To overcome the drawback of disclosing users' social network privacy and prevent the location server from learning users' complete social network relationships, [PERSON] et al. [11] proposed a scheme which used multiple location servers (MLS) to protect users' social network privacy. Further, to decrease communication overhead, [PERSON] et al. [12] designed a centralized architecture to address the privacy issues in location-sharing systems. However, while protecting users' privacy, the previous solutions seldom consider the problems of system efficiency and the flexibility of users' privacy-preserving requirements. In location-sharing systems, a user can request a location-sharing service for querying friends' locations.