Authenticated Query For Outsourced Databases

In the outsourced database model, data owners delegate the data management, query processing and data update to a specialized third-party service provider. By means of relieving data owners from heavy daily responsibilities of data management, outsourced database services have the potential to provide efficient and cost effective services. Therefore, the outsourced database service has been gaining tremendous popularity over the recent years.However, as the service provider and the data owner belong to different market levels and different security management domains, the outsourced data faces the risk of being leaked and tampered with in the process of storage and services, which makes the query results untrustworthy and the user’s privacy cannot be guaranteed. These security risks are the constraints on specialization and market development of data sharing and market development. Therefore, the query authentication and privacy protection of outsourced database services are two essential security issues that need to be addressed.Considering these challenges in outsourced databases, this thesis proposes the authenticated query processing algorithm for three different query types.(1) First and foremost, this thesis designs a framework that achieves both query authentication and privacy preserving goals at one shot under key-value stores. Without involving heavy encryption algorithms, this thesis separates key-value pairs and stores the segments on multiple servers, based on which a filtration-based query processing scheme is proposed. The framework enables users to verify the soundness, completeness and freshness of query results. The system architecture is given, followed by the algorithm designing. Experimental results show the effectiveness and efficiency of the framework under various system settings and workloads.(2) Lastly, in mobile social networking applications, users form a group and query for the Point-Of-Interests(POIs) according to their locations and individual preferences. To address such query scenarios in spatial databases, this thesis formulates two new query types; Multiple User-defined Spatial Queries(MUSQ) and Multiple User-Feeling Spatial Queries(MFSQ). These two queries satisfy the new requirements of users when using spatial databases. The query results are influenced by spatial/non-spatial attributes of POIs as well as users’ specified preferences. Further, this thesis designs the query authentication methods based on MR-tree for MUSQ and MFSQ. Experimental results show the effectiveness and efficiency under various settings and workloads in both frameworks.