Keyword-pair result pattern hiding structured encryption for Boolean queries

Publication Type

Journal Article

Publication Date

5-2025

Abstract

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.

Keywords

Multi-keyword Boolean query, searchable symmetric encryption, structured encryption, prime number hash

Discipline

Information Security

Publication

IEEE Transactions on Information Forensics and Security

Volume

20

Issue

1

First Page

8449

Last Page

8461

ISSN

1556-6013

Identifier

10.1109/TIFS.2025.3594578

Publisher

Institute of Electrical and Electronics Engineers

Additional URL

https://doi.org/10.1109/TIFS.2025.3594578

This document is currently not available here.

Share

COinS