Achieving Searchable Encryption Scheme With Search Pattern Hidden

Searchable Encryption (SE) enables a data owner to outsource encrypted data to an untrusted server while preserving the keyword search functionality. Typically, the server learns whether or not a query has been performed more than once, which is usually called the search pattern. However, such kind of information leakage might be leveraged to break query privacy. To further reduce such type of leakage and provide strong privacy guarantee, Wang et al. proposed a novel SE scheme based on the Paillier encryption scheme in INFOCOM’15. Unfortunately, their scheme cannot perform keyword search successfully, because the additive homomorphic property is not sufficient for their construction. In this article, we first show that why their scheme fails to return the correct search result, and then propose a new SE scheme by adopting a special additive homomorphic encryption scheme to achieve the multiplicative homomorphic property efficiently. Furthermore, we enhance the security on the user side. Specifically, we use random polynomials with an appropriate degree to guarantee that the user cannot learn anything other than the desired search result. Finally, we present a formal security analysis and implement our scheme on a real-world database, which demonstrates that our construction can achieve the desired security properties with good performance.

1 Introduction

Cloud computing is the delivery of on-demand computation and storage resources over the internet in the matter of pay-as-you-go basis. In order to reduce the local maintenance cost, more and more users prefer to outsource their data to the cloud server [8], [9], [10]. However, one of the main challenges for cloud computing is the data privacy, because the cloud server may try to learn as much information about the outsourced data as possible. Although the end-to-end encryption technique can protect the confidentiality of users’ data, it leads to the loss of search ability over the encrypted data.