# A Security-Enhanced Query Result Verification Scheme for Outsourced Data in Location-Based Services
## 1 Introduction  
Location-based services (LBSs) are pervasive in people's social lives. With the increase in LBS applications, users can enjoy many convenient social services, such as map navigation, restaurant recommendations, and taxi reservations. One typical LBS is the point of interest (POI) information query system. By inputting locations and POI types, users can reach relevant POI information [1]. However, since the location-based service provider (LBSP) has to maintain exponentially-growing POI data to provide a better service, storing and computing data have been burdens for LBSP. Outsourcing a service, as a prevalent service mode, has many advantages, such as cost saving, quick deployment, and flexible resource configuration [2]. In this mode, enterprises could migrate their service data to a third party, such as the cloud or fog side, and outsource their services to the cloud or fog server. Motivated by the rich benefits brought about by outsourcing services, the LBSP could reduce its burden by utilizing the computing and storage resources of a third party [3; 4; 5]. However, how to guarantee the confidentiality of outsourced data has become a key problem (due to the separation from the direct control of outsourced data) [6]. To address this problem, one common way is to encrypt the service data before outsourcing. Therefore, many research studies focus on how to search for encrypted data. Searchable encryption, as a method that enables the outsourced data to be searched without decrypting, has been adopted in many research studies [4; 7; 8]. For example, searchable encryption is used in [7] to store electronic health records, allowing different participating healthcare organizations and individuals (e.g., physicians, hospitals, medical laboratories, and insurance companies) to securely access electronic health records, enabling efficientdata sharing. However, driven by illegal profits, such as saving storage costs, the third party may behave dishonestly. Therefore, many researchers have designed query result verification mechanisms to guarantee the correctness and completeness of query results. For example, researchers in [9] proposed a fine-grained query result verification scheme. In this scheme, the verification object of the query result was constructed by the Bloom filter, and a user who received the query result can check the correctness and completeness by verifying the corresponding verification object. Although the scheme achieves a fine-grained query result verification, the construction process is not perfect. Specifically, the structure of the certain verification object has an exceptional layout, which will provide additional knowledge to the third party and further lead to the privacy disclosure of the outsourced data. For example, if the LBSP outsources its service data to the cloud side and adopts this query result verification mechanism, the cloud side could easily figure out which is the largest number of encrypted outsourced POI type data. The schemes [10; 11; 12] also provide verification solutions to support the check of the query result. Although the confidentiality of the query index and the outsourced data can be guaranteed by the method of encryption, the relationship between the encrypted query index and corresponding encrypted query objects (e.g., the verification object) is one-to-one. That is, the above query result verification mechanisms will provide additional statistical information to the third party and further lead to the information leakage of the encrypted outsourced data. For example, if the LBSP outsources its service data to the cloud side and adopts the above query result verification mechanisms, the cloud side could infer the meaning of the encrypted POI type by counting the frequency of the query indexes and popularity of POI types. Although current schemes have proposed various query result verification mechanisms to prevent the third party from returning erroneous or incomplete query results, there is little research on the non-repudiation of the returned data.