Efficient and secure multi-functional searchable symmetric encryption schemes

摘要

There is an increasing trend for data owners to outsource their data to an untrusted cloud provider. Besides providing the storage for the data, the service provider could allow the data owner or authorized clients to search over the data. To guarantee the data secure, the owner must encrypt his or her data before sending to the cloud. However, traditional encryption does not allow searching without decrypting the data. Searchable symmetric encryption is one approach that allows users to search over the encrypted data. For data applications, various different functional search have been proposed, such as wildcard search, similarity keyword search and fuzzy keyword search. Moreover, dynamic addition and removal of files should be supported in practice. However, to our knowledge, there does not exist a searchable symmetric encryption scheme that can support many properties such as more than three functions in all the aforementioned operations. In this paper, we propose an efficient multi-functional searchable symmetric encryption scheme that can support wildcard search, similarity search (including hamming distance and edit distance), fuzzy keyword search and disjunctive keyword search simultaneously. In the new scheme, the trapdoor changes with various search requests and it enumerates all possibilities of the keyword of the trapdoor. Moreover, we use an array instead of a matrix to reduce the storage, and the scheme can be constructed efficiently in terms of both computational and space complexity. Our scheme is based on the Bloom filter, and it is secure against non-adaptive chosen keyword attack. With the dynamic technique for the inverted index, our scheme can support dynamic operation such as addition and removal of data files, which can also be secure against adaptive chosen keyword attack. Copyright (C) 2015 John Wiley & Sons, Ltd.