Exploiting Hidden Information Leakages in Backward Privacy for Dynamic Searchable Symmetric Encryption

Dynamic searchable symmetric encryption (DSSE) enables searches over encrypted data as well as data dynamics such as flexible data addition and deletion operations. A major security concern in DSSE is how to preserve forward and backward privacy, which are typically achieved by removing the linkability between the newly added data and previous queries, and between the deleted data and future queries, respectively. After information leakage types were formally defined for different levels of backward privacy (i.e., Type-I, II, III), many backward private DSSE schemes have been constructed under the definitions. However, we observed that the backward privacy can be violated by leveraging additional secondary leakage, which is typically leaked in specific constructions of schemes in spite of their theoretical guarantees. In this paper, in order to understand the security gap between the theoretical definitions and practical constructions, we conduct an in-depth analysis of the root cause for the secondary leakage, and demonstrate how it can be abused to violate Type-II backward privacy (e.g., the exposure of the deletion history) of DSSE constructions in practice. We then propose a novel Type-II backward private DSSE scheme based on Intel SGX, which is resilient to the secondary leakage abuse attack. According to the comparative analysis of our scheme with the state-of-the-art SGX-based DSSE schemes, Bunker-B (EuroSec’19) and SGX-SE1 (ACNS’20), our scheme shows higher efficiency in terms of the search latency with a negligible utility loss under the same security level (cf. Bunker-B) while showing similar efficiency with a higher security level (cf. SGX-SE1). Finally, we formally prove that our scheme guarantees Type-II backward privacy.