Towards Efficient and Strong Backward Private Searchable Encryption with Secure Enclaves

Dynamic searchable symmetric encryption (DSSE) can enable a cloud server to search and update over the encrypted data. Recently, forward and backward privacy in DSSE receive wide attention due to the rise in a number of emerging attacks exploiting the leakage in data update operations. Forward privacy ensures newly added data is not related to queries issued in the past, whilst backward privacy ensures previously deleted data is not revealed in the queries. Unfortunately, achieving strong forward and backward privacy, i.e., only revealing insertion timestamps of search results, requires the adoption of oblivious data structures, which incur heavy computation and communication overhead at both the client and server-side. In this paper, we resort to secure enclaves, aka Intel SGX, to tackle the above problem. Specifically, we propose Maiden, the first strong backward-private DSSE scheme without relying on ORAM. Our key idea is to keep track of the states of updates and the deletion information inside the secure enclave to prevent the leakage from the server. To speed up, we further leverage a compressed data structure to maintain a sketch of addition operations in the enclave to facilitate the fast generation of search tokens of non-deleted data. We conduct formal security analysis and perform comprehensive evaluations on both synthetic and real-world datasets. Our results confirm that Maiden outperforms the prior work.