Practical non-interactive searchable encryption with forward and backward privacy

Shi-Feng Sun, Ron Steinfeld, Shangqi Lai, Xingliang Yuan, Amin Sakzad, Joseph K. Liu, Surya Nepal, Dawu Gu

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

49 Citations (Scopus)


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 publicationProceedings 2021, 28th Network and Distributed System Security Symposium
EditorsDavid Balenson
Place of PublicationReston VA USA
PublisherThe Internet Society
Number of pages18
ISBN (Electronic)1891562665, 9781891562662
Publication statusPublished - 2021
EventUsenix Network and Distributed System Security Symposium 2021 - Online, San Diego, United States of America
Duration: 21 Feb 202125 Feb 2021 (Proceedings)


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

Cite this