Abstract: Dynamic Symmetric Searchable Encryption (DSSE) has become one of the most important primitives for data privacy protection in recent years. It allows clients to efficiently retrieve and update encrypted data stored in cloud servers. Only a small amount of strictly defined leakage is disclosed to the server, such as search pattern, access pattern, update pattern, and volume pattern. However, a growing number of studies have found that some powerful adversaries can exploit DSSE leakage to carry out specific attacks that undermine the privacy of data and retrieval. In the past, Private Information Retrieval, Oblivious Random Access Machine and storage padding are often used to compress or even eliminate the leaked information. These technologies can provide better security, but they are difficult to be applied because of the high complexity of computation, communication and storage. In order to achieve a better balance between safety and efficiency, this paper proposes the following ideas: We first introduce a meaningful security concept-differential privacy and propose a new padding method, differential privacy padding(DPP), which can reduce the storage load while ensuring the security. Then a Dynamic search update scheme called “MDSSE” is proposed in the multi-server mode. Through DPP apply to our scheme, volume, update and search pattern hiding are realized. The forward privacy and back privacy security are guaranteed at the same time. For the security proof of the scheme, we extend the definition of update history and propose a differential Update history DP-Update which is suitable for this scheme. Experimental results show that our scheme can resist leakage and abuse attacks, it also provides high storage and communication efficiency.

Key words: dynamic symmetric searchable encryption (DSSE), differential privacy, multi-server setting, forward privacy, leakage-hiding