Keyword-Pair Result Pattern Hiding Structured Encryption for Boolean Queries

Cash et al. [CRYPTO2013] proposed the oblivious cross-tags (OXT) protocol to enable highly scalable searchable symmetric encryption (SSE) with support for Boolean queries. More recently, Lai et al. [CCS2018] introduced the hidden cross-tags (HXT) protocol, an enhancement of OXT designed to eliminate “keyword-pair result pattern” (KPRP) leakage in conjunctive queries. However, while HXT prevents KPRP leakage in conjunctive queries, it suffers from low efficiency and remains vulnerable to KPRP leakage in disjunctive queries. In this paper, we propose the first efficient structured encryption scheme for Boolean queries (STE-BQ) that eliminates KPRP leakage for both disjunctive and conjunctive multi-keyword queries. Our approach introduces a novel index construction method based on prime number aggregation, which significantly reduces the number of comparisons required in multi-keyword searches, thereby improving efficiency. Security analysis confirms that STE-BQ satisfies CQA2-security. Experimental evaluations further demonstrate that STE-BQ achieves optimal performance in conjunctive query processing. While its disjunctive query time is slightly slower than that of OXT, STE-BQ is the only scheme that fully eliminates KPRP leakage for both conjunctive and disjunctive queries.