Privacy-Preserving Spatio-Temporal Keyword Search for Outsourced Location-Based Services

With the popularization of location-based services (LBS), encryption techniques have been utilized to protect data security when outsourcing LBS to cloud. However, existing schemes only consider spatial range search or keyword search, while expressive and practical search over encrypted LBS data is still a challenging problem. In this article, we introduce PrivSTL, a privacy-preserving spatio-temporal keyword search framework over the encrypted LBS data based on attribute-based encryption, linear encryption and RSA encryption. It allows mobile users to submit LBS query with spatial range, time interval and Boolean keyword expression, and provides accurate and authorized search by matching these query conditions and also the access policy. Then we introduce an extended scheme PrivSTG, which utilizes Geohash to divide the locations into grids, and outsources an encrypted index tree to cloud servers. PrivSTG improves the service efficiency by searching only over the ciphertexts in the surrounding grids of mobile user. Finally, we analyze the security of PrivSTL against chosen-plaintext, chosen-keyword and outside keyword-guessing attacks in generic bilinear group model, and show that PrivSTL guarantees the spatio-temporal keyword profile privacy, and also protects the query privacy. The experimental results indicate that our scheme is practical and efficient for outsourced LBS.