Authentication Of Spatial Polynomial Function Query

With the development of network communication technology,all kinds of industry have accumulated a large amount of data.How to use these huge amounts of data efficiently and safely to provide more convenience for people has become an important problem.Data outsourcing service gradually becomes an essential mode of the Internet service.Under this scenario,the data owners mandate the data to data service providers to provide users efficient and professional Internet services.In the data outsourcing service scenario,the data owners and the data service providers are in different security management domains.And it is difficult to establish reliable trust relationship among each other.In particular,data service providers may modify service content without authorization because of enterprise interests.For example,in the location-based nearby merchants query service,to earn the advertising fee,the service provider may place the information of the paid merchant in the top of query result instead of sorting strictly according to the distance of the target location by near and far.Generally,assume that the data providers follow the semi-honesty model,i.e.,the data service providers will enforce the communication protocol strictly,but they will cheat users and provide incorrect query results.Ensuring that users can access trusted services based on original data is the core of the problem of query service authenticity verification.The location-based query can be expressed by the spatial polynomial function.In this paper,we study the authenticity verification method of the spatial polynomial function query to make that users can receive the query results and verify the soundness,correctness,and completeness of them,i.e.,the query results are based on the original data of data owners while satisfying the query condition,and has not been tampered and omitted.The main works of this paper are listed as follows:(1)We give a formal description of spatial polynomial query and give the description of query authenticity verification,and then we define the task target of query authenticity verification.We design an authentication data structure of query based on MR-Tree and Voronoi Diagram.At last,we analyze the performance of the proposed data structure.(2)To settle the problem of SUM(the sum of space polynomial)query,we design the query and verification object generation algorithm of verifiable SUM query and query results verification method.(3)To settle the problem of MAX(the max of space polynomial)query,we design the query and verification object generation algorithm of verifiable MAX query and query results verification method.(4)We design refined experiments for the verification methods mentioned in(2)and(3).The experiment results verify the performance of the proposed verification methods in communication cost and computational cost.