Leakage Reduced Searchable Symmetric Encryption for Multi-Keyword Queries

Conjunctive keyword queries on untrusted cloud servers represent one of the most common forms of search in encrypted environments. Extensive research has been devoted to developing efficient schemes that support multi-keyword queries. In particular, the Oblivious Cross-Tags (OXT) protocol has received significant attention and is widely regarded as a benchmark in this domain. However, existing schemes fail to simultaneously hide the Keyword-Pair Result Pattern (KPRP) and the conditional Intersection Pattern (IP), potentially leaking additional information to the server. In this work, we propose a novel searchable symmetric encryption (SSE) scheme, referred to as <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Result Hiding Search (RHS)</i>, which aims to minimize result pattern leakage and achieve query result hiding during the index retrieval phase by integrating Private Set Intersection (PSI) techniques. Our scheme enhances privacy by employing PSI for secure membership testing. To improve query efficiency, we shift the expensive complex computation to the offline phase, and utilize efficient pseudorandom functions and hash functions during the online phase. Moreover, we propose a variant of RHS, called vRHS, designed to reduce client-side storage overhead. A simulation-based security proof demonstrates that our scheme is robust against non-adaptive adversaries. Comprehensive experimental evaluation further shows that our approach achieves better security and efficiency trade-offs compared to existing SSE schemes.