Practical Robust Dynamic Searchable Symmetric Encryption Supporting Conjunctive Queries
摘要
Dynamic Searchable Symmetric Encryption (DSSE) allows clients to securely update encrypted data, in addition to performing queries. Although researchers developed the first conjunctive SSE with forward and backward privacy in 2021, the proposed scheme cannot fully achieve the desired dynamicity for conjunctive queries. Very recently, an enhanced conjunctive DSSE was presented with new backward privacy for conjunctive queries (i.e., Type- \(\textrm{O}\) ). However, it incurs substantial computational overhead in both update and search operations. Furthermore, how to extend conjunctive DSSE to handle abnormal update operations (e.g., re-insertion of deleted entries) remains a challenging problem. To tackle the above limitations, we propose ROXT, a robust and efficient conjunctive DSSE scheme with forward and enhanced Type- \(\textrm{O}\) backward security. ROXT ensures robustness through a tag verification mechanism based on the Counting Bloom Filter, which accurately identifies valid ciphertexts using locally maintained compressed deletion lists. To enhance efficiency, ROXT integrates a shared cache mechanism with the OXT framework for search optimization. Performance evaluations show that ROXT significantly outperforms the state-of-the-art SDSSE-CQ in both update and search efficiency. Specifically, ROXT achieves a \(3.98\times \) speedup in update latency and improves search efficiency by up to \(106.27\times \) on the client side and \(3.25\times \) on the server side.