Dynamic Similarity Search Over Encrypted Data

More and more intensive data needs to be stored and calculated with the advent of the information.The traditional way of data storage and management can no longer meet the needs of large-scale data.It is a tendency that outsourcing data on cloud servers to ease local maintenance and management overhead for more and more enterprises and individuals.However,private data's security and privacy will be seriously threatened if storing private data on a semi-honest cloud server directly.The easiest and straightforward choice is to encrypt the private data using symmetric encryption before outsourcing it to the cloud,which protects data from illegal accessing but causes the operations on the ciphertext become more complicated and time-consuming,such as the most basic search operations,thought.Driven by such demands,plenty of searchable encryption solutions that allows users to search over encrypted data directly while maintaining the confidential of database and queries have come into being.The traditional searchable encryption scheme is designed for static database.After the index is established,the real-time additions and deletions of data are difficult.To remedy this problem,some dynamically searchable encryption schemes providing the ability of update have been proposed.The file-injection attacks proposed recently emphasizes the importance of forward security in dynamic searchable encryption.In order to prevent such kind of attacks,some schemes hide the information about the newly added files matching the previous queries or not at the expense of efficiency.On the other hand,most forward secure dynamic searchable encryption schemes are designed for processing precise search instead of similarity search.Based on the above points,this paper proposes and implements a forward secure dynamic similarity search scheme with optimal search and update complexity over encrypted data for semi-honest servers.Firstly,due to most of the proposed dynamic searchable encryption schemes not supporting similarity search,we make use of a state-of-the-art algorithm called Locality Sensitive Hashing(LSH),which is widely used to solve Approximate Nearest Neighbor(ANN)search problem on high dimensional data.The features in the data set are quantized with LSH algorithm,and the nearer distance data is mapped to the same hash value with a high probability.The quantized hash values are used to construct a dynamic searchable encryption scheme.On the other hand,by combining the forward index and inverted index to construct a dual dictionary that ensures efficient retrieval capability and allows to update data explicitly and in real time.The update efficiency and security are significantly improved compared to previous works.In addition,our scheme provide forward security by reencrypting the data in the secure index with a new key to invalidate the original query token.Then,limit the conditions for updating the key to reduce the number of updates while ensuring forward security,and the adverse effect of the update on the search efficiency is weaken,thereby effectively improving the search efficiency.The dual dictionary data structure effectively solves the contradiction between searching features and updating the database and avoids the security risk of sending the key to the semi-honest server directly.We update the secure index when appropriate with a new key to achieve efficient forward security.Finally,the locality sensitive hashing algorithm is applied to dynamic searchable encryption scheme to implement similarity search.The theoretical analysis clarifies the complexity of the scheme and proves the correctness of the scheme that is adaptive forward secure as well.Next,the scheme was applied to a real mail data set and the performance of the experiment was evaluated.The results of multiple experiments show that this scheme is very effective in practice and is suitable for efficient similarity search and dynamic update of data in real encrypted data environment.