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

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 Tramy, a more practical DSSE scheme that allows multiple clients to access the dataset with conjunctive queries. More importantly, it can track malicious servers. Tramy also hides the search pattern and achieves forward and backward privacy. To achieve these, we propose a new primitive called Matrix-based Multi-Point Retrieval (MMPR) to protect the search pattern and introduce a novel data structure—Malice-Defend Bloom Filter (MDBF). This data structure can not only support conjunctive queries, but also enable integrity verification on the server’s response results, thereby significantly enhancing security. Tramy 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, Tramy can effectively resist adaptive adversaries and achieve up to $20\times $ performance improvements.