Practical Searchable Symmetric Encryption Supporting Conjunctive Queries Without Keyword Pair Result Pattern Leakage

Abstract

The research of searchable symmetric encryption (SSE) has been focused on the trade-off between security, performance, and functionality. Recently proposed Hidden Cross-Tags (HXT) protocol improves the Oblivious Cross-Tags (OXT) by avoiding the leakage of `Keyword Pair Result Pattern' (KPRP), at the cost of increasing the storage size by two orders of magnitude. In this paper, we reconsider the principle of designing SSE protocols to prevent KPRP leakage. At first, we introduce a new primitive called subset membership check (SMC), where a set is encrypted such that its subset membership can be checked only through a protocol between Sender and Tester. The holistic security of SMC requires that nothing is revealed other than the membership of a subset after each execution of the protocol. We propose a hash-based SMC implementation with efficient computation, communication, and storage. Secondly, based on the hash-based SMC, we present a practical SSE protocol that supports conjunctive queries without KPRP leakage. Our SSE protocol, called `Practical Hidden Cross-Tags' (PHXT), maintains the same storage size as OXT while preserving the same privacy and functionality as HXT. Compared with HXT, our PHXT reduces the storage size and the communication overhead by 91.29%, 64.29%, respectively, without degrading the computational efficiency.

Keywords

• Conjunctive query
• encrypted bloom filter
• holistic security
• keyword pair result pattern
• searchable symmetric encryption
• subset membership check