Research On Privacy-Preserving Keyword Search Techniques In Cloud Environments

With the scale and user quantity of data services growing vigorously,it becomes difficult for data owners to provide data services in local servers. More and more data owners are motivated to outsource their data services to the cloud for cost-savings.However, directly outsourcing such data services will cause serious privacy concerns.The private information in the data may be obtained illegally by adversaries or even by the cloud provider for some commercial profits, which violates data privacy. With the rapid development of Internet technologies, data services based on keyword search have been widely employed in real-life applications. Therefore, how to provide various keyword-search-based data services in cloud environments while ensuring privacy preserving becomes an important problem.To enable diversified keyword search services with better user experience in cloud environments, this thesis focuses on the privacy issues for three important types of keyword search techniques, and solves the privacy-preserving problems of keyword similarity ranked search, spatial keyword queries and nearest keyword search on graphs. The main contributions of this thesis are as follows:(1) To enable privacy-preserving keyword similarity ranked search in cloud,we propose a privacy-preserving top-k keyword similarity search scheme.We first create similarity keyword sets based on the edit distance and keyword relevancy to support the keyword similarity ranked search. Then, with the encryption of similarity keyword sets and relevancy, we construct a new efficient tree-based secure index. Based on this secure index,we further propose a privacy-preserving top-k keyword similarity search algorithm,which can support keyword similarity ranked search over textual data without privacy leakage.Analysis shows the validity and security of the proposed scheme, and experimental results illustrate the proposed scheme can achieve high efficiency.(2) To enable privacy-preserving spatial keyword queries in cloud, we propose a privacy-preserving top-k spatial keyword query scheme. We first construct a secure index based on the unified encryption over spatio-textual data. To achieve efficient queries over the secure index, we further propose an anchor-assisted position determination algorithm and a position-distinguished trapdoor generation algorithm to support the spatio-textual similarity computation in ciphertext. In addition, to satisfy the performance requirements for large scale spatio-textual data processing, we propose a keyword-based secure pruning method to improve the efficiency during the query processing. Analysis shows the validity and security of the proposed scheme, and experimental results illustrate the proposed scheme can achieve high efficiency and scalability.(3) To enable the privacy-preserving keyword search on graphs, we propose a prvicy-preserving nearest keyword search scheme on outsourced graphs.We first construct a secure two-level index based on the encryption of shortest distance trees and the keywords on the graph. Then, to protect the privacy information in search requests,we further propose a trapdoor generation algorithm based on the privacy-preserving set operations. Leveraging the secure two-level index and trapdoors, we propose a privacy-preserving nearest keyword search algorithm, which can support efficient nearest keyword search on graph data without privacy violation. Analysis demonstrates the validity and security of the proposed scheme, and experimental results show the efficiency of the proposed scheme.