Practical non-interactive searchable encryption with forward and backward privacy

Shifeng Sun, Ron Steinfeld, Shangqi Lai, Xingliang Yuan, Amin Sakzad, Joseph Liu, Surya Nepal, Dawu Gu

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


In Dynamic Symmetric Searchable Encryption (DSSE), forward privacy ensures that previous search queries cannot be associated with future updates, while backward privacy guarantees that subsequent search queries cannot be associated with deleted documents in the past. In this work, we propose a generic forward and backward-private DSSE scheme, which is, to the best of our knowledge, the first practical and non-interactive Type-II backward-private DSSE scheme not relying on trusted execution environments. To this end, we first introduce a new cryptographic primitive, named Symmetric Revocable Encryption (SRE), and propose a modular construction from some succinct cryptographic primitives. Then we present our DSSE scheme based on the proposed SRE, and instantiate it with lightweight symmetric primitives. At last, we implement our scheme and compare it with the most efficient Type-II backward-private scheme to date (Demertzis et al., NDSS 2020). In a typical network environment, our result shows that the search in our scheme
outperforms it by 2 􀀀 11 under the same security notion.
Original languageEnglish
Title of host publication28th Annual Network and Distributed System Security Symposium, NDSS 2021
EditorsAhmad-Reza Sadeghi, Farinaz Koushanfar
Place of PublicationSan Diego CA USA
PublisherInternet Society
Number of pages18
ISBN (Electronic)1891562665
Publication statusPublished - 2021
EventUsenix Network and Distributed System Security Symposium 2021 - Online, United States of America
Duration: 21 Feb 202125 Feb 2021


ConferenceUsenix Network and Distributed System Security Symposium 2021
Abbreviated titleNDSS 2021
Country/TerritoryUnited States of America
Internet address

Cite this