Geometric Searchable Encryption Without False Positive And Its Applications

As a prominent cryptographic tool, geometric searchable encryption (GSE) can be applied in many scenarios, such as location-based services (LBS), social networks and vehicle networks. Unfortunately, most of existing searchable encryption schemes supporting the functionality of geometric range searches suffer from false positives, which will lead people to make a wrong decision and further raise some serious consequences such as financial loss. In addition, some of them are designed under a symmetric system, which is not enough flexible deployed in LBS since in a symmetric system only a private key holder creates ciphertext, whereas in a public-key system anyone who holds a public key can produce ciphertext. In this paper, we intend to design a novel GSE scheme without any false positive under a public-key system supporting arbitrary geometric area searches, which is able to guarantee an accurate query result. Toward this goal, we develop a novel technique in handling the relation between a point and any convex polygon in combination with an inner product encryption, which is able to support arbitrary convex polygon range searches without any false positive. A comprehensive experiment demonstrates that, compared with the known schemes, our scheme possesses a 100% accuracy as well as an acceptable efficiency in the sense that it can guarantee that all files retrieved by users are exactly matched ones. Finally, we provide two practical examples of our GSE scheme: privacy-preserving friend-nearby notification with a common point of interest and privacy-preserving parking monitor and guiding system.