IJBTT

Spatial Query Authentication using Merkle QuadTree

	International Journal of Engineering Trends and Technology (IJETT)
	© 2018 by IJETT Journal
	Volume-59 Number-4
	Year of Publication : 2018
	Authors : J Linita Lyle, Ani Sunny
	DOI :  10.14445/22315381/IJETT-V59P234

Citation 

J Linita Lyle, Ani Sunny"Spatial Query Authentication using Merkle QuadTree", International Journal of Engineering Trends and Technology (IJETT), V59(4),186-191 May 2018. ISSN:2231-5381. www.ijettjournal.org. published by seventh sense research group

Abstract
With the increasing popularity of location-based services and the excessive use of smart phones and GPS enabled devices, the practice of outsourcing spatial data to third party service providers has grown rapidly over the past few years. Meanwhile, the fast arising trend of cloud storage and cloud computing services has provided a flexible and cost-effective platform for hosting data from businesses and individuals, further enabling many location-based applications. However, in this database outsourcing paradigm, the authentication of the query results at the client remains a challenging problem. This paper presents a novel method for authentication of query results based on the ideas of Authentication Data Structures. The idea of Merkle Hash Tree is adopted which allows a client to verify the correctness and completeness of the result set. A novel authentication scheme is suggested based on the concepts of Merkle Hash Tree and quadtree for verifying the authenticity of outsourced spatial databases.

Reference
[1] B. Hore, S. Mehrotra, and G. Tsudik, “A Privacy-Preserving Index for Range Queries,” Proc. 30th Int’l Conf. Very Large Data Bases (VLDB’04), pp. 720-731, Aug. 2004.
[2] Chung-Min Chen, Andrzej Cichocki, Allen McIntosh, Euthimios Panagos, “Privacy-Protecting Index for Outsourced Databases”, In Proc. of ICDE Workshops 2013, pp. 83-87.
[3] D. Wu, G. Cong, and C. S. Jensen. A framework for efficient spatial web object retrieval. VLDB J., 21(6):797–822, 2012.
[4] Dongxi Liu, Shenlu Wang, “Programmable Order-Preserving Secure Index for Encrypted Database Query” In Proceedings of 2012 IEEE Fifth International Conference on Cloud Computing, pp. 502-509, 2012.
[5] E. Mykletun, M. Narasimha, and G. Tsudik, “Authentication and integrity in outsourced databases,” In Proc. of ACM Trans. On Storage, vol. 2, 2006, pp. 107-138.
[6] G. Cong, C. S. Jensen, and D. Wu. Efficient retrieval of the top-k most relevant spatial web objects. In VLDB, pages 337–348, 2009.
[7] H. Hacigumus, S. Mehrotra, and B. Iyer, “Providing Database as a Service,” Proc. IEEE 18th Int’l Conf. Data Eng. (ICDE), Feb. 2002.
[8] H. Pang, J. Zhang, and K. Mouratidis. Scalable Verification for Outsourced Dynamic Databases. PVLDB, 2(1):802–813, 2009.
[9] Hu, L., Ku, W., Bakiras, S., Shahabi, C.: Spatial query integrity with voronoi neighbors. IEEE Trans. Knowl. Data Eng. 25(4), 863–876 (2013)
[10] Li Feifei, Marios H, George K, “Dynamic Authenticated Index Structures for Outsourced Database” In Proc. of ACM SIGMOD’06. Chicago, Illinois, 2006, pp. 121-132
[11] R. C. Merkle. A certified digital signature. In CRYPTO, pages 218–238, 1989.
[12] R. J. Morteza Noferesti, Mohammad Ali Hadavi, "A Signature-based Approach of Correctness Assurance in Data Outsourcing Scenarios," ICISS 2011, India, pp. 374-378.
[13] R. Zhang, J. Sun, Y. Zhang and C. Zhang, "Secure Spatial Top-k Query Processing via Untrusted Location-Based Service Providers," in IEEE Transactions on Dependable and Secure Computing, vol. 12, no. 1, pp. 111-124, Jan.-Feb. 2015.
[14] Schnitzer, B., Leutenegger, S.: Master-client R-trees: a new parallel R-tree architecture. In: SSDBM, pp. 68–77 (1999)
[15] Viet Hung Nguyen, Tran Khanh Dang, Nguyen Thanh Son , Josef Küng, “Query Assurance Verification for Dynamic Outsourced XML Databases”, Second International Conference on Availability, Reliability and Security (ARES`07), 2007, pp. 689 - 696.
[16] Y. Yang, S. Papadopoulos, D. Papadias, and G. Kollios. Authenticated Indexing for Outsourced Spatial Databases. VLDB J., 18(3):631–648, 2009.
[17] Y. Yang, S. Papadopoulos, D. Papadias, and G. Kollios. Spatial Outsourcing for Location-based Services. In ICDE, pages 1082– 1091, 2008.
[18] Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Comput. Surv. 38(2), 1–56 (2006)

Keywords
Database Outsourcing, Security Authentication, Spatial Database.