Cryptology ePrint Archive: Report 2020/048

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

Changshe Ma and Yiping Gu and Hongfei Li

Abstract: 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.

Category / Keywords: searchable symmetric encryption, subset membership check, holistic security, encrypted bloom filter, keyword pair result pattern, conjunctive query.

Date: received 16 Jan 2020

Contact author: changshema at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200117:082707 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]