International Association
for Cryptologic Research

Recently proposed searchable symmetric encryption (SSE) scheme HXT improves the OXT by avoiding the KPRP leakage at the cost of increasing the storage 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 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 two practical SSE protocols that support conjunctive queries without KPRP leakage. Our first protocol, called ‘Practical Hidden Cross-Tags’ (PHXT), maintains the same storage size as OXT while preserving the same privacy and functionality as HXT. Our second protocol, called ‘Fast Hidden Cross-Tags’ (FHXT), further optimizes the performances of PHXT through eliminating the expensive Diffie-Hellman type operations. Compared with HXT, our FHXT reduces the storage size, server’s computational costs, client’s computational costs, and the communication overhead by 96.09%, 98.44%, 79.54%, and 78.57%, respectively.