[Resource Topic] 2020/048: Practical Searchable Symmetric Encryption Supporting Conjunctive Queries without Keyword Pair Result Pattern Leakage

Welcome to the resource topic for 2020/048

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

Authors: Changshe Ma, Yiping Gu, 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.

ePrint: https://eprint.iacr.org/2020/048

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .