Volume-Hiding Forward and Backward Private Dynamic Searchable Symmetric Encryption for Conjunctive Queries

Searchable symmetric encryption for conjunctive queries allows for locating encrypted files that contain multiple keywords while safeguarding query privacy. The update capability of dynamic searchable symmetric encryption (DSSE) for conjunctive queries further enhances its applicability in real-world scenarios. Unfortunately, leakage-abuse attacks and volumetric-injection attacks (Zhang et al., USENIX Security 2023) demonstrate update information can be leveraged to compromise query privacy. Although many DSSE schemes are proposed to resist existing attacks, none support conjunctive queries with volume-hiding, forward and backward privacy. To address this, we first present a scalable bitmap index and refines security definitions to support conjunctive queries. Then we introduce two new schemes with volume-hiding, forward and backward private DSSE for conjunctive queries: VFBDSSE-CQ and SVFBDSSE-CQ. VFBDSSE-CQ offers fast updates for frequently changing data, while SVFBDSSE-CQ lowers client storage at the cost of slower updates, fitting large keyword datasets. Both schemes are proven to meet volume-hiding, forward and backward privacy. Finally, experimental results demonstrate that VFBDSSE-CQ achieves up to 200× faster performance on Enron Email and 600× faster on Chicago Crime, while SVFBDSSE-CQ achieves up to 200× and 3000× faster performance, compared to ODXT (Patranabis et al., NDSS 2021).