Downgrading Backward Privacy of Searchable Encryption

Searchable encryption allows users to outsource ciphertext with search capability. Although many searchable encryption schemes aiming at providing high efficiency with provable security have been proposed, traditional searchable encryption schemes have been also exploited by numerous types of attacks causing sensitive information leakage among the ciphertexts and queries. In order to deter such leakage of linkable information between the ciphertexts and queries, forward and backward-private searchable encryption schemes have been proposed. Especially, backward privacy is divided into three categories (Type-I, II, III) on the basis of the security level, which are determined by the types of leaked information during the protocol execution. In this paper, we introduce a novel backward privacy downgrade attack on the existing searchable encryption schemes. In order to demonstrate the efficacy of our attack, we show the backward privacy of the previous scheme, MITRA, can be downgraded from Type-II to Type-III.