Efficient evaluation of range queries over spatial data by clients

Pilli Satya Veni, Nadella. Sunil


The notion of Geometrically Searchable Encryption, and anticipated an effectual scheme, named FastGeo, to keep the privacy of clients’ spatial datasets kept and enquired at a public server. With FastGeo, which is a novel two-level search for scrambled spatial data, an honest-but-curious server can proficiently complete geometric range queries, and suitably return data points that are private a geometric range to a client without culture penetrating data points or this cloistered query. FastGeo wires arbitrary geometric areas, accomplishes sub linear search time, and qualifies go-ahead updates over encrypted spatial datasets. Our outline is provably sheltered, and our new results on real-world spatial datasets in cloud platform determine that FastGeo can enhance search time over 100 times.


D. Song, D. Wagner, and A. Perrig, “Practical Techniques for Searches on Encrypted Data,” in Proc. of IEEE S&P’00, 2000.

R. Curtmola, J. A. Garay, S. Kamara, and R. Ostrovsky, “Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions,” in Proc. of ACM CCS’06, 2006.

S. Kamara, C. Papamanthou, and T. Roeder, “Dynamic Searchable Symmetric Encryption,” in Proc. of ACM CCS’12, 2012.

D. Cash, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Rosu, and M. Steiner, “Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries ,” in Proc. of CRYPTO’13, 2013.

V. Pappas, F. Krell, B. Vo, V. Kolesnikov, T. Malkin, S. G. Choi, W. George, A. Keromytis, and S. Bellovin, “Blind Seer: A Searchable Private DBMS,” in Proc. of IEEE S&P’14, 2014.

D. Cash, J. Jaeger, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Rosu, and M. Steiner, “Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation,” in Proc. Of NDSS’14, 2014.

E. Stefanov, C. Papamanthou, and E. Shi, “Practical Dynamic Searchable Encryption with Small Leakage,” in Proc. of NDSS’14, 2014.

G. Ghinita and R. Rughinis, “An Efficient Privacy-Preserving System for Monitoring Mobile Users: Making Searchable Encryption Practical,” in Proc. of ACM CODASPY’14, 2014.

B.Wang, M. Li, H. Wang, and H. Li, “Circular Range Search on Encrypted Spatial Data,” in Proc. of IEEE CNS’15, 2015.

H. Zhu, R. Lu, C. Huang, L. Chen, and H. Li, “An Efficient Privacy-Preserving Location Based Services Query Scheme in Outsourced Cloud,” IEEE Trans. on Vehicular Technology, 2015.

B. Wang, M. Li, and H. Wang, “Geometric Range Search on Encrypted Spatial Data,” IEEE Transactions on Information Forensics and Security, vol. 11, no. 4, pp. 704–719, 2016.

M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications. Springer- Verlag, 2008.

Satyan L. Devadoss and Joseph O’Rourke, Discrete and Computational Geometry. Princeton University Press, 2011.

J. Katz and Y. Lindell, Introduction to Modern Cryptography, Second, Ed. CRC Press, 2014.

R. A. Popa, F. H. Li, and N. Zeldovich, “An Ideal-Security Protocol for Order-Preserving Encoding,” in Proc. of IEEE S&P’13, 2013.

Boyang Wang, Ming Li, Member, IEEE, and Li Xiong, Member, IEEE, Fastgeo: Efficient Geometric Range Queries On Encrypted Spatial Data, 2017.

Full Text: PDF [Full Text]


  • There are currently no refbacks.

Copyright © 2013, All rights reserved.| ijseat.com

Creative Commons License
International Journal of Science Engineering and Advance Technology is licensed under a Creative Commons Attribution 3.0 Unported License.Based on a work at IJSEat , Permissions beyond the scope of this license may be available at http://creativecommons.org/licenses/by/3.0/deed.en_GB.