Tramy: A Multi-Client Dynamic Searchable Symmetric Encryption With Malicious Servers Tracking for Conjunctive Queries

Abstract

Dynamic Searchable Symmetric Encryption (DSSE) enables efficient searches over encrypted data but often suffers from search pattern leakage, allowing adversaries to infer sensitive information. While schemes using Oblivious RAM (ORAM) mitigate leakage, their high cost hinders large-scale applications. Dory adopts a multi-server architecture with distributed point functions (DPFs) to reduce leakage and improve performance. However, a key limitation of this architecture is the lack of a mechanism to track and hold malicious servers accountable. Although Dory assumes malicious servers, it does not provide a way to monitor their behavior or enforce accountability. This represents an important challenge for the system. Moreover, Dory only supports single-keyword queries and works in the single-client setting, which limits its practicality. We propose <monospace>Tramy</monospace>, a more practical DSSE scheme that allows multiple clients to access the dataset with conjunctive queries. More importantly, it can track malicious servers. <monospace>Tramy</monospace> also hides the search pattern and achieves forward and backward privacy. To achieve these, we propose a new primitive called <monospace>M</monospace>atrix-based <monospace>M</monospace>ulti-<monospace>P</monospace>oint <monospace>R</monospace>etrieval (<monospace>MMPR</monospace>) to protect the search pattern and introduce a novel data structure—<monospace>M</monospace>alice-<monospace>D</monospace>efend <monospace>B</monospace>loom <monospace>F</monospace>ilter (<monospace>MDBF</monospace>). This data structure can not only support conjunctive queries, but also enable integrity verification on the server’s response results, thereby significantly enhancing security. <monospace>Tramy</monospace> supports precise authorization for multiple clients and constructs an access mechanism for multi-client scenarios. Finally, comprehensive benchmark tests show that, compared to the state-of-the-art, <monospace>Tramy</monospace> can effectively resist adaptive adversaries and achieve up to <inline-formula> <tex-math notation="LaTeX">$20\times $ </tex-math></inline-formula> performance improvements.