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 keyword search functionality. Typically, the server learns whether or not a query has been performed more than once, which is called the search pattern. However, such kind of information leakage might be leveraged to break query privacy. To 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 paper, 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.