FASTGEO: EFFICIENT GEOMETRIC RANGE QUERIES ONENCRYPTED SPATIAL DATA
ABSTRACT
Spatial data have wide applications, e.g., location-based services, and geometric range queries (i.e., finding points insidegeometric areas, e.g., circles or polygons) are one of the fundamental search functions over spatial data. The rising demand ofoutsourcing data is moving large-scale datasets, including large-scale spatial datasets, to public clouds. Meanwhile, due to the concernof insider attackers and hackers on public clouds, the privacy of spatial datasets should be cautiously preserved while querying them atthe server side, especially for location-based and medical usage. In this paper, we formalize the concept of Geometrically SearchableEncryption, and propose an efficient scheme, named FastGeo, to protect the privacy of clients’ spatial datasets stored and queried ata public server. With FastGeo, which is a novel two-level search for encrypted spatial data, an honest-but-curious server can efficientlyperform geometric range queries, and correctly return data points that are inside a geometric range to a client without learning sensitivedata points or this private query. FastGeo supports arbitrary geometric areas, achieves sublinear search time, and enables dynamicupdates over encrypted spatial datasets. Our scheme is provably secure, and our experimental results on real-world spatial datasets incloud platform demonstrate that FastGeo can boost search time over 100 times.
PROPOSED SYSTEM:
The major contributions of thispaper are summarized as below:_ With the embedding of a hash table and a set of linklists in our two-level search as a novel structure forspatial data, FastGeo can achieve sublinear searchand support arbitrary geometric ranges (e.g., circlesand polygons). Compared to recent solutions, FastGeo not only provides highly efficientupdates over encrypted spatial data, but also improvessearch performance over 100x._ We formalize the definition of GSE and its leakagefunction, and rigorously prove data privacy andquery privacy with indistinguishability under selectivechosen plaintext attacks (IND-SCPA).We implement and evaluate FastGeo in cloud platform(Amazon EC2), and demonstrate that FastGeois highly efficient over a real-world spatialdataset. For instance, a geometric range query over49,870 encrypted tuples can be performed within15 seconds, and an update only requires less than1 second on average.
EXISTING SYSTEM:
OPE and some SE schemes that supportcomparisons, can perform rectangular range queries byapplying multiple dimensions. However, those extensionsdo not work with other geometric range areas, e.g.,circles and polygons in general. Wang et. al. [9] proposeda scheme, which particularly retrieves points inside acircle over encrypted data by using a set of concentriccircles. Zhu et al also built a scheme for circularrange search over encrypted spatial data. Unfortunately,these two schemes exclusively work for circles, and donot apply to other geometric areas.Ghinita and Rughinis designed a scheme, whichsupports geometric range queries by using Hidden VectorEncryption . Instead of encoding a point with abinary vector of T2bits, where T is the dimension size,it leverages a hierarchical encoding, which reduces thevector length to 2 logT bits. However, its search timeis still linear with regard to the number of tuples ina dataset, which not only runs slowly over large-scaledatasets but also disables efficient updates.2
CONCLUSION
We propose FastGeo, an efficient two-level searchscheme that can operate geometric ranges over encryptedspatial datasets. Our experiment results over a realworlddataset demonstrate its effectiveness in practice.Moreover, our comparison with previous solutions indicatesthat the general idea of two-level search can beleveraged as an important methodology to boost searchtime and enable highly efficient updates over encrypteddata when complex operations, such as compute-thencompareoperations, are involved in search.
REFERENCES
[1] D. Song, D. Wagner, and A. Perrig, “Practical Techniques forSearches on Encrypted Data,” in Proc. of IEEE S&P’00, 2000.
[2] R. Curtmola, J. A. Garay, S. Kamara, and R. Ostrovsky, “SearchableSymmetric Encryption: Improved Definitions and EfficientConstructions,” in Proc. of ACM CCS’06, 2006.
[3] S. Kamara, C. Papamanthou, and T. Roeder, “Dynamic SearchableSymmetric Encryption,” in Proc. of ACM CCS’12, 2012.
[4] D. Cash, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Rosu, andM. Steiner, “Highly-Scalable Searchable Symmetric Encryptionwith Support for Boolean Queries ,” in Proc. of CRYPTO’13, 2013.
[5] V. Pappas, F. Krell, B. Vo, V. Kolesnikov, T. Malkin, S. G. Choi,W. George, A. Keromytis, and S. Bellovin, “Blind Seer: A SearchablePrivate DBMS,” in Proc. of IEEE S&P’14, 2014.
[6] D. Cash, J. Jaeger, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Rosu,and M. Steiner, “Dynamic Searchable Encryption in Very-LargeDatabases: Data Structures and Implementation,” in Proc. ofNDSS’14, 2014.
[7] E. Stefanov, C. Papamanthou, and E. Shi, “Practical DynamicSearchable Encryption with Small Leakage,” in Proc. of NDSS’14,2014.
[8] G. Ghinita and R. Rughinis, “An Efficient Privacy-Preserving Systemfor Monitoring Mobile Users: Making Searchable EncryptionPractical,” in Proc. of ACM CODASPY’14, 2014.
[9] B. Wang, M. Li, H. Wang, and H. Li, “Circular Range Search onEncrypted Spatial Data,” in Proc. of IEEE CNS’15, 2015.
[10] H. Zhu, R. Lu, C. Huang, L. Chen, and H. Li, “An EfficientPrivacy-PReserving Location Based Services Query Scheme inOutsourced Cloud,” Ieee Trans. on Vehicular Technology, 2015.
[11] B. Wang, M. Li, and H. Wang, “Geometric Range Search on EncryptedSpatial Data,” IEEE Transactions on Information Forensicsand Security, vol. 11, no. 4, pp. 704–719, 2016.