Searchable Encryption for Conjunctive Queries with Extended Forward and Backward Privacy
Authors: Cong Zuo (Beijing Institute of Technology), Shangqi Lai (Monash University/CSIRO Data61), Shi-Feng Sun (Shanghai Jiao Tong University), Xingliang Yuan (The University of Melbourne), Joseph K. Liu (Monash University), Jun Shao (Zhejiang Gongshang University/Zhejiang E-Commerce Key Lab), Huaxiong Wang (Nanyang Technological University), Liehuang Zhu (Beijing Institute of Technology), Shujie Cui (Monash University)
Volume: 2025
Issue: 1
Pages: 440–455
DOI: https://doi.org/10.56553/popets-2025-0024
Abstract: Recent developments in the field of Dynamic Searchable Symmetric Encryption (DSSE) with forward and backward privacy have attracted much attention from both research and industrial communities. However, most DSSE schemes with forward and backward privacy schemes only support single keyword queries, which impedes its prevalence in practice. Although some forward and backward private DSSE schemes with expressive queries (e.g., conjunctive queries) have been introduced, their backward privacy either essentially corresponds to single keyword queries or forward privacy is not comprehensive. In addition, the deletion of many DSSE schemes is achieved by addition paired with a deletion mark (i.e., lazy deletion). To address these problems, we present two novel DSSE schemes with conjunctive queries (termed SDSSE-CQ and SDSSE-CQ-S), which achieve both forward and backward privacy. To analyze their security, we present two new levels of backward privacy (named Type-O and Type-O-, more and more secure), which give a more comprehensive understanding of the leakages of conjunctive queries in the OXT framework. Eventually, the security analysis and experimental evaluations show that the proposed schemes achieve better security with reasonable computation and communication increase.
Keywords: Forward Privacy, Backward Privacy, Dynamic Searchable Symmetric Encryption, Conjunctive Queries
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
