Research On Security Of Index Structure Of Outsourced Spatial Database

Spatial database, which is widely used in the production of social life, is the sum of application-related geospatial data which the Geographic Information System stores in computer physical storage media. In order to save operational costs of the data, companies in increasing numbers choose to outsource their spatial database to a third party operator to manage and maintain today. We call this type of database outsourced spatial database. The Location-based Geographic Information System(GIS) not only brings convenience to people, but also brings great challenges to the protection of information privacy which people concern about. On the one hand, traditional means of privacy protection simply encrypts data and index structure such as KD-tree and R-tree and uses client-server-based several interactive query processing protocol to process query requests, in order to hide the user’s physical location and other sensitive data. However, after encrypted, the indexing structure and data field of the database on the third-party servers may be unsafe too. Although database encryption methods to some extent can better protect data privacy, there still exists serious problem of data privacy leaks. For example, according to the traces of I/O operation of range queries and the logical relationship of accessed the disk pages and the plaintext, hacker can deduce the user query content. On the other hand, while server suffers from the invasion of hackers, it may return incorrect answers to users. Once the hackers recognize the organization of data on the server, data on the server can be logically replaced. And the answers to be returned may be incomplete.From the perspective of privacy, authenticity and integrity of outsourced spatial database, this thesis includes the following aspects:(1) By constructing security measure of encrypted KD-tree, we demonstrated the risk of user privacy data leakage from the perspective of theory and practice, and provide people with important reference and basis to design more secure and efficient data index structures. Experimental results show that even if the KD-tree has been encrypted, there still exists the possibility of leakage of user privacy data.(2) We propose a protocol based on random access called RAccess. Experimental results show that the RAccess method we proposed can effectively enhance the security of the encrypted KD- tree, greatly reducing the risk of leakage of private data.(3) We introduce some approach for authenticating k Nearest Neighbor(kNN) query results such as signature chain, collaborative computation of digest and hiding non-answer points. And we propose an R-tree-based kNN query authentication approach. Experimental results indicate that the R-tree-based authentication of kNN query approach we proposed is feasible and effective.