The notion of Multi-Key Searchable Encryption (MKSE) enables data owners to outsource their data into a cloud server, while supporting fine-grained data sharing with the authorized users. Note that the traditional MKSE is vulnerable to data leakage. That is, the malicious data owner may collude with the server and recover the search queries of authorized users. Recently, Hamlin et al. (PKC’18) presented a new MKSE construction that can ensure data privacy between data owner and authorized users, where the share key is generated depending on data owner, authorized user and the specific document. However, their scheme cannot support verifiable search in the case of the malicious cloud server. In this paper, we propose a new verifiable MKSE (VMKSE) scheme by leveraging Garbled Bloom Filter, which can simultaneously support verifiability of search result and secure data sharing in multi-user setting. Compared to the state-of-the-art solution, the proposed scheme is superior in efficiency and verifiability. The experiment results demonstrate the efficiency of our scheme.

Encrypted conjunctive search enables server to perform efficient conjunctive query over encrypted data while guaranteeing data and query privacy. The well-known Oblivious Cross-Tags (OXT) protocol (by Cash et al. in CRYPTO 2013) is the first to realize efficient conjunctive search with some well-defined leakage, such as the keyword pair result pattern (KPRP) leakage and the cross-query intersection result pattern (IP) leakage. To mitigate the potential threats brought by the leakage, much effort has been made to reduce the information leaked by OXT. However, it is still open to achieve encrypted conjunctive search without revealing both KPRP and IP, while preserving high-efficiency. Encrypted multi-map is a crucial primitive for designing searchable encryption with optimal search complexity. In this paper, we present the first non-interactive encrypted conjunctive multi-map, Doris, without KPRP and IP leakage. To this end, we design a novel data structure for performing conjunctive query, that enables the client to generate "encrypted" label/value pairs without interaction. Then, we introduce a new cryptographic primitive dubbed Symmetric Subset Predicate Encryption, which supports checking if one set is entirely contained within another without leaking any information than the subset predicate. Finally, we implement Doris and provide a detailed comparison with the most related works HXT (by Lai et al. in CCS 2018) and ConjFilter (by Patel et al. in ASIACRYPT 2021). The experimental results demonstrate that Doris can achieve a speedup of 6× and 1.07× compared to HXT and ConjFilter in search latency respectively for 2 labels querying, while increasing to 42× and 1.1× respectively for 10 labels, even with a stronger security guarantee.

The primitive of Searchable Symmetric Encryption (SSE) allows a server to perform search directly over encrypted documents. Recently, forward secure SSE (FSSE) has attracted significant attention due to its secure property for document update. That is, it can prevent the server from learning whether the newly updated document contains previously queried keywords. Most of the existing FSSE schemes are designed for single keyword search. For the case of conjunctive keyword search, prior dedicated FSSE constructions either require inefficient tools or suffer from significant leakage (i.e., it leaks the documents matching each queried keywords). To deal with this challenge, we propose a general framework to design efficient conjunctive keyword FSSE schemes without significant leakage: a basic scheme FOXT-B and an enhanced one FOXT-E. Specifically, in our basic scheme, we combine XSet structure in the Oblivious Cross-Tags protocol (CRYPTO 2013) with a single keyword FSSE to support conjunctive keyword search. However, this simple combination is limited to support document update. That is, the user cannot perform search until all the keyword-document pairs in a document have been updated. To support flexible keyword-document update, we design a new XSet for our enhanced scheme, in which the user can perform search at any time. Finally, we present a formal security analysis and implement our schemes on a real-world database, which demonstrates that our proposed schemes can achieve the desired security goals with practical efficiency.

Secure join queries over encrypted databases, the most expressive class of SQL queries, have attracted extensive attention recently. The state-of-the-art JXT (Jutla et al. ASIACRYPT 2022) enables join queries on encrypted relational databases without pre-computing all possible joins. However, JXT can merely support join queries over two tables (in encrypted databases) with some high-entropy join attributes. In this paper, we propose an equi-join query protocol over two tables dubbed JXT+, that allows the join attributes with arbitrary names instead of JXT requiring the identical name for join attributes. JXT+ reduces the query complexity from O(\ell_1 \cdot \ell_2) to O(\ell_1) as compared to JXT, where \ell_1 and \ell_2 denote the numbers of matching records in two tables respectively. Furthermore, we present JXT++, the first equi-join queries across three or more tables over encrypted databases without pre-computation. Specifically, JXT++ supports joins of arbitrary attributes, i.e., all attributes (even low-entropy) can be candidates for join, while JXT requires high-entropy join attributes. In addition, JXT++ can alleviate sub-query leakage on three or more tables, which hides the leakage from the matching records of two-table join. Finally, we implement and compare our proposed schemes with the state-of-the-art JXT. The experimental results demonstrate that both of our schemes are superior to JXT in search and storage costs. In particular, JXT+ (resp., JXT++) brings a saving of 49% (resp., 68%) in server storage cost and achieves a speedup of 51.7× (resp., 54.3×) in search latency.