Shedding Light on Blind Spot of Backward Privacy in Dynamic Searchable Symmetric Encryption

Dynamic searchable symmetric encryption (DSSE) enables users to outsource their data while retaining the capability to search and update on the encrypted database. Although various DSSE schemes have been proposed to achieve higher efficiency and stronger security, many of them incurred information leakages due to the linkability between ciphertexts and queries as side information. The notions of forward and backward privacy are defined to capture such information leakage in DSSE formally. In particular, backward privacy guarantees that queries do not reveal their relationship with the deleted database, which is further classified into four types (Type-I, I^-, II, and III) based on the types of information leakage. In this study, we provide a backward privacy attack that exploits the information leakages and apply it to Type-I^- backward private schemes to lower their security level to Type-III. We then propose a new DSSE framework, which is robust against the proposed attack. We apply our framework to the previous DSSE scheme (Zuo et al., ESORICS 2019) to build the first forward and backward Type-I private DSSE scheme under the backward privacy attack, and demonstrate its efficacy.