Secure Similarity Search Over Encrypted Non-Uniform Datasets

Searchable symmetric encryption (SSE) enables a user to outsource a private dataset to a cloud server in encrypted form while retaining the ability to search over the encrypted outsourced data. The existing SSE schemes improve the search and safety performances from different perspectives. However, almost none of the existing SSE schemes considers the data distribution issues. We find that when the dataset is not distributed uniformly, the search quality based on the conventional methods decreases. Therefore, the existing SSE schemes cannot guarantee high search quality when faced with non-uniform datasets. In addition, most existing SSE solutions cannot hide the distribution of the query set. In this article, we design a S\ecure similarity search over Encrypted Non-uniform and high-dimensional Datasets (SEND) with a novel way to enhance security. The basic idea is to combine SSE with locality-sensitive hashing (LSH). Unlike earlier schemes, SEND uses selective hashing, which has better performance for non-uniform datasets. Also, we present a novel approach to hide the distribution of the query set, which makes SEND more secure. Our experimental results indicate SEND achieves a high search quality of recall and precision, and it is proven secure against adaptively chosen query attacks in the standard model.

Automated summary

This article presents a method called SEND for secure similarity search over encrypted non-uniform and high-dimensional datasets. By combining SSE with locality-sensitive hashing and utilizing selective hashing and query set distribution hiding techniques, SEND achieves high search quality in terms of recall and precision, and is proven secure against adaptively chosen query attacks in the standard model.