Geometric range search is a fundamental primitive for spatial data analysis in SQL and NoSQL databases. It has extensive applications in location-based services, computer aided design, and computational geometry. Due to the dramatic increase in data size, it is necessary for companies and organizations to outsource their spatial data sets to third-party cloud services (e.g., Amazon) in order to reduce storage and query processing costs, but, meanwhile, with the promise of no privacy leakage to the third party. Searchable encryption is a technique to perform meaningful queries on encrypted data without revealing privacy. However, geometric range search on spatial data has not been fully investigated nor supported by existing searchable encryption schemes. In this paper, we design a symmetric-key searchable encryption scheme that can support geometric range queries on encrypted spatial data. One of our major contributions is that our design is a general approach, which can support different types of geometric range queries. In other words, our design on encrypted data is independent from the shapes of geometric range queries. Moreover, we further extend our scheme with the additional use of tree structures to achieve search complexity that is faster than linear. We formally define and prove the security of our scheme with indistinguish ability under selective chosen-plaintext attacks, and demonstrate the performance of our scheme with experiments in a real cloud platform (Amazon EC2).
While most of the searchable encryption schemes focus on common SQL queries, such as keyword queries and Boolean queries, few studies have specifically investigated geometric range search over encrypted spatial data.
Wang et al. proposed a novel scheme to specifically perform circular range queries on encrypted data by leveraging a set of concentric circles.
Some previous searchable encryptions handling order comparisons can essentially manage axis parallel rectangular range search on encrypted spatial data.
Similarly, Order-Preserving Encryption, which has weaker privacy guarantee than searchable encryption, is also able to perform axis-parallel rectangular range search with trivial extensions.
Ghinita and Rughinis particularly leveraged certain Functional Encryption with hierarchical encoding to efficiently operate axis-parallel rectangular range search on encrypted spatial data in the application of mobile users monitoring.
DISADVANTAGES OF EXISTING SYSTEM:
Most of the searchable encryption schemes focus on common SQL queries, such as keyword queries and Boolean queries, few studies have specifically investigated geometric range search over encrypted spatial data.
Inevitably introduces obstacles in terms of search functionalities over encrypted data.
None of these previous works have particularly studied geometric range queries which are expressed as non-axis-parallel rectangles or triangles.
More importantly, there still lacks a general approach, which can flexibly and securely support different types of geometric range queries over encrypted spatial data regardless of their specific geometric shapes.
In this paper, we propose a symmetric-key probabilistic Geometric Range Searchable Encryption. With our scheme, a semi-honest (i.e., honest-but-curious) cloud server can verify whether a point is inside a geometric range over encrypted spatial datasets. Informally, except learning the necessary Boolean search result (i.e., inside or outside) of a geometric range search, the semi-honest cloud server is not able to reveal any private information about data or queries.
Our main contributions are summarized as follows:
We present a symmetric-key probabilistic Geometric Range Searchable Encryption, and formally define and prove its security with indistinguishability under Selective Chosen-Plaintext Attacks (IND-SCPA).
In addition, our search process is non-interactive on encrypted data. In terms of search complexity, our baseline scheme incurs linear complexity (with regard to the number of data records), and its advanced version realizes faster than- linear search by integrating with tree structures.
Our design is a general approach, which can securely support different types of geometric range queries on encrypted spatial data regardless of their geometric shapes. Furthermore, our design is not only suitable for geometric range queries, but also compatible with other regular types of geometric queries, such as intersection queries and point enclosure queries, over encrypted spatial data.
ADVANTAGES OF PROPOSED SYSTEM:
The security of our scheme is formally defined and analyzed with indistinguishability under Selective Chosen-Plaintext Attacks.
Our design has great potential to be used and implemented in wide applications, such as Location-Based Services and spatial databases, where the use of sensitive spatial data with a requirement of strong privacy guarantee is needed.
System : Pentium Dual Core.
Hard Disk : 120 GB.
Monitor : 15’’ LED
Input Devices : Keyboard, Mouse
Ram : 1GB
Operating system : Windows 7.
Coding Language : JAVA/J2EE
Tool : Netbeans 7.2.1
Database : MYSQL
Boyang Wang, Student Member, IEEE, Ming Li, Member, IEEE, and Haitao Wang, “Geometric Range Search on Encrypted Spatial Data”, IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 11, NO. 4, APRIL 2016.