SOLS: A scheme for outsourced location based service

Due to the high demand on computation and storage, location based service (LBS) providers prefer to outsource their data and services to powerful cloud service providers (CSPs). However, this mechanism brings three challenging issues, namely, user location privacy, data security, and service efficiency. In this paper, a scheme for outsourced location based service (SOLS) is proposed for addressing above three open issues. The SOLS consists of secure index generation (SIG), dynamic trapdoor generation (DTG) and privacy-preserving efficient index exploration(PPEIE). In SIG, every location will be hashed into three parts representing three levels. The function of the first and second part is the entrance and label respectively, while the third part functions as a key. In DTG, the trapdoor will be generated differently even for the same location by introducing the random mechanism to trapdoor generation. The target entrances, labels and messages are sequentially selected in PPEIE. Due to the DTG and PPEIE, SOLS is able to resist the search pattern leakage and provide efficient services. We also analyze the security of SOLS in the proposed stronger threat model where CSPs can get public LBS information from websites at any time interval. The analysis result shows the SOLS is safe under this threat model. An experiment is conducted using the collection set built from SimpleGeo׳s Places data which includes nearly 2 million points. The result shows that with the number of locations increasing linearly, the search time of SOLS increases sub-linearly.