Study On Approximate Nearest Neighbor Search Over Encrypted Data In Cloud Computing

With the coming of the era of big data, nearest neighbor retrieval technology has an increasingly important role in the field of multimedia and other computer fields. Massive data applications need for nearest neighbor search in large data sets. In another words, it is to find out the most similar object with a given query object. However, the traditional nearest neighbor queries are affected by the "dimension disaster" in high dimensional space, their performance fell sharply along with the increase of data dimension. To address above problem, approximate nearest neighbor is proposed. The locality sensitive hashing technique is the state-of-the-art of the ANN search, which is widely studied and applied. However, more problems occur to the information security increasingly. In some area requiring high security, the search and utilization of the data information must be based on high security. Thus, the combination between the encryption technology and retrieval technology is required. And a huge storage capacity is needed to store mass data. Till now, these algorithms both at home and abroad support only ANN search over plaintext without considering confidentiality of information and resource-constrained of users.With the rapid development of cloud computing, more and more clients with limited resources outsource the private data to the cloud server for storing. Therefore, under the circumstance of the cloud, encryption technology can solve above two problems. Till now, the research in the area of the ANN technology and searchable encryption based on the encrypted database both at home and abroad are mature, whereas the ANN search over encrypted data is expected to have more development. To obtain both confidentiality and efficiency of retrieval is always the goal of the searchable encryption schemes. Therefore, retrieving information what clients need from the ciphertext accurately and quickly has become a pressing problem.According to this problem, based on the key technology of ANN search, a new secure and efficient ANN search scheme over encrypted data is constructed, which is based on SortingKeys-LSH (LSH) and mutable order-preserving encryption (mOPE). The core problem of ANN search over ciphertexts is how to build safe and efficient ciphertext index, which not only meets the security needs of index, but also satisfies the demand of efficient retrieval. The main points of this paper are as follows:1. The paper studies the existing and different ANN search schemes and focused on the schemes based on LSH, and then summarizes the disadvantages of the existing schemes.2. Based on the semi-honest server model, in the paper, we propose a secure and efficient ANN search scheme over encrypted data. In our construction, we exploit SK-LSH to generate indexes locally. While data and indexes should be outsourced to the cloud in encrypted form, which complicates computations on the encrypted data. Then, we encrypt LSH indexes using mOPE for efficient ANN search.3. Through rigorous security analysis, we show that our proposed scheme is secure under the proposed model, while correctly realizing the goal of secure ANN search over encrypted data.