Forward and Backward Private Searchable Encryption with SGX

Abstract

Symmetric Searchable Encryption (SSE) schemes enable users to search over encrypted data hosted on an untrusted server. Recently, there has been a lot of interest in forward and backward private SSE. The notion of forward privacy guarantees that updates to the encrypted structure do not reveal their association to any query made in the past. Backward privacy, on the other hand, guarantees that queries do not reveal their association to deleted documents. But strong backward private schemes are known to be inefficient in terms of both communication and computation. One avenue for improvement is leveraging the power of trusted execution environments such as Intel SGX inside the untrusted server to improve some of these inefficiencies. In this work, we propose the first SGX-supported dynamic SSE constructions that are forward-private as well as backward-private. To the best of our knowledge, while there is some work on SGX-supported Oblivious RAM (ORAM) and static SSE, there is no work on SGX-supported dynamic SSE. We propose three constructions that cover all types of backward privacy in literature that are very efficient compared to the state of the art backward private schemes. Our communication complexity is always the number of current documents matching the query and we show that there is no need for 'total obliviousness' in constructions for the strongest notion of backward privacy.