Verifiable Conjunctive Dynamic Searchable Symmetric Encryption With Forward and Backward Privacy

Abstract Dynamic searchable symmetric encryption (DSSE) with forward and backward privacy makes it possible to perform search on the outsourced encrypted database efficiently while still allowing updates under acceptable leakage. Current forward and backward private DSSE (FB-DSSE) scheme proposed by Zuo et al. cannot support conjunctive keyword query and the cloud server needs to be honest-but-curious. Recent FB-DSSE scheme supporting conjunctive keyword query proposed by Patranabis et al. cannot verify search results. On the other hand, searchable symmetric encryption scheme proposed by Wang et al. that supports conjunctive keyword query and the verification of search results cannot achieve forward and backward privacy. The problem of constructing a verifiable conjunctive FB-DSSE scheme is still open. In this paper, we propose a verifiable conjunctive dynamic searchable symmetric encryption scheme (VCDSSE). VCDSSE is a FB-DSSE scheme that additionally supports the verification of search results and conjunctive keyword query. We revisit homomorphic MAC to enable efficient verification of search results, adopt the technique of oblivious cross-tags to achieve conjunctive keyword query and utilize state chain to ensure forward and backward privacy. The formal security analysis and performance evaluation demonstrate that VCDSSE is secure and practical as compared with Mitra scheme in terms of search time.