Research Of Secure Query Mechanism On Encrypted Structured Data

The widely use of cloud computing makes data outsourcing be a new kind of trend. Organizations and individuals are inclined to outsource the storage and management of data to a cloud in order to save on hardware investments and reduce maintenance cost. Only authorized users are allowed to access the data. However, the remote placement of the data brings security concerns. The data outsourcing may include some private information and the data owner prefer to prevent the server from learning the content of the database. Hence, the data must be encrypted before uploading to the server. When a user wants to retrieve the data, he/she also have to encrypt his/her query to make the server learn nothing about it. Unfortunately, traditional encryption methods that aims at providing “unbreakable” protection are often not adequate because they do not support the execution of applications such as database queries on the encrypted data and existing solutions bring too much calculation overhead and communication cost.In this paper, we focus on two significant problems called secure range query and secure knearest neighbor(SkNN) search and propose solutions respectively that aim at protecting data privacy in outsourcing environment. The main contributions are as follows.Secure range query under location based service that the server returns spatial points fall inside the limit a user specified. We utilize a new encryption algorithm called comparable encryption(CE) that the magnitude of two plaintext can be determined with only ciphertext. Using comparable encryption and KD tree structure, we construct the Secure KD(SKD) tree index structure and implement secure range query on it. Benefit from the property of comparable encryption and the mechanism of KD tree that split the space using super rectangle, the whole query process require only one round trip and reduce CPU time of the user end.The SkNN method focus on dataset in high dimensional space. The server and the user are both seen as adversaries. We utilize product quantization(PQ) and inverted file system(IVF) to build index structure for high dimensional vectors. The distance table stored at the user end is encrypted by Paillier homomorphic encryption algorithm to prevent information disclosure. So the computation of the similarity of two vectors is executed at user end and the decryption process is performed by the server. The computation cost of the user end is low enough and the padding and scrambling methods are used to improve security. The communication cost is optimized by quadratic coarse quantization.At last, our solutions provide compromise between security and efficiency and are verified by both theoretical analysis and performance study on real datasets. The comparison with the state of art technology show the advantages of our methods.