ORAM Based Forward Privacy Preserving Dynamic Searchable Symmetric Encryption Schemes

In the cloud era, as more and more businesses and individuals have their data hosted by an untrusted storage service provider, data privacy has become an important concern. In this context, searchable symmetric encryption (SSE) has gained a lot of attention. An SSE scheme aims to protect the privacy of the outsourced data by supporting, at the same time, outsourced search computation. However, the design of an efficient dynamic SSE (DSSE) has been shown to be a challenging task. In this paper, we present two efficient DSSEs that leak a limited amount of information. Both our schemes make a limited use of ORAM algorithms to achieve forward privacy and to minimize the overhead that ORAMs introduce, at the same time. To the best of our knowledge, there is only one other DSSE scheme that offers efficiently forward privacy. Our schemes are parallizable and significantly improve the search and update complexity, as well as the memory access locality.