## 1 Introduction  
With the rapid development of the Internet of Things (IoTs), fog computing has been presented by Cisco in 2012 [1] as a supplement to cloud computing. Based on its network edge computing feature, fog computing is able to provide location-awareness applications, where the location-based service (LBS) is the most popular [2; 3]. With the assistance of fog computing, the LBS providers can outsource the LBS data to fog nodes and thus provide people a convenient life [4]. For instance, through the LBS provided by a local fog node, a mobile user can query and search points of interest (POIs) within a given distance to his/her location [5; 6]. Actually, LBS query has become one of the killer applications in LBS, which allows mobile users to query a LBS provider (such as Google or Bing maps) to obtain the detailed information about POIs in their vicinity (e.g., restaurants, hospitals, etc.). For example, when a tourist arrives at a new place, it is very necessary to query some interesting places, such as hotels, restaurants, scenic spots and so on, based on the LBS. Hence, we focus on the LBS query in this paper. Although LBS can benefit people a lot, the submitted queries may lead to some sensitive information about users being revealed, such as hobbies, current location and the location where mobile users will reach [7; 8]. To clearly illustrate the privacy challenge in LBS query, we consider the following scenario, where a mobile user wants to find a hospital by exposing his location to a local fog node. Thus, this fog node can infer user's location where he will reach according to his request (the content of the matched POIs). However, even worse, the health condition that is very sensitive to this user, may be disclosed. Conceivably, without the privacy assurance in fog computing, the LBS can not continue to its flourish because users' personal trajectory and hobby may be exposed. In addition, owing to the mobility of mobile users, the low-latency is very critical for the LBS query [9]. For example, when a driver wants to find the nearest restaurant on a heavy-traffic road, he has to keep driving while waiting for the response to ensure smooth traffic. If the response is slow, the result may already not satisfy the current spatial range of this diver, i.e., the driver has traveled far away. Therefore, latency should also be taken into account. Recently, many privacy-preserving LBS schemes have been proposed to prevent the location privacy of LBS users. For examples, location obfuscation technology has been presented to protect users' precise locations from disclosing [10; 11]. In addition, spatial cloaking technology has been proposed to conceal the precise location in a cloaking area [12; 13]. However, the accuracy of the matched results in these schemes are not satisfactory, since the locations submitted by users are not precise. In order to ensure the data privacy and improve the accuracy of results simultaneously, privacy information retrieval (PIR) [14] has been applied to the LBS query [15; 16]. Unfortunately, as mentioned in [17], PIR needs to transmit the entire LBS data to the mobile users, which brings about the heavy communication burden, especially for big data. In addition, a mobile user has to additionally access the LBS database's index data in a privacy-preserving way, which leads to the linear calculations of all LBS data. Hence, the communication and computational costs are tremendous, which is not cost-efficient for mobile users. To overcome this disadvantage, some efficient cryptographic algorithm-based schemes have been developed for the LBS query, where most of these schemes focused on cloud computing, as it can offer on-demand and scalable storage and unlimited computing capacity, especially for big data processing. For examples, [PERSON] et al. [18] discussed an efficient privacy-preserving location-based query over outsourced encrypted data by coding and bilinear pairing techniques; [PERSON] et al.