# Efficient Volume-Hiding Encrypted Multi-Maps with Support for Conjunctive Queries

Tianci Li, Jiaojiao Wu, Jianfeng Wang

► To cite this version:

Tianci Li, Jiaojiao Wu, Jianfeng Wang. Efficient Volume-Hiding Encrypted Multi-Maps with Support for Conjunctive Queries. 37th IFIP International Conference on ICT Systems Security and Privacy Protection (SEC), Jun 2022, Copenhagen, Denmark. pp.467-485, 10.1007/978-3-031-06975-8_27 hal-05319895

HAL Id: hal-05319895

https://inria.hal.science/hal-05319895v1

Submitted on 17 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
Efficient Volume-Hiding Encrypted
Multi-Maps with Support for Conjunctive
Queries

Tianci Li, Jiaojiao Wu, and Jianfeng Wang(✉)

State Key Laboratory of Integrated Service Networks (ISN), Xidian University,
Xi'an 710071, China
{tcli_134,jiaojiaowujj}@stu.xidian.edu.cn, jfwang@xidian.edu.cn

**Abstract.** Structured Encryption (STE), introduced by Chase and Kamara (ASIACRYPT 2010), enables to perform efficient private queries over an encrypted data structure. Very recently, Kamara and Moataz (EUROCRYPT 2019) formalized the notion of volume-hiding STE to mitigate the volume attack, and presented the first concrete volume-hiding encrypted multi-map (EMM) scheme with densest subgraph transform, which can ensure that the volume of values associated with the queried key is hidden to the adversary. To achieve better performance, Patel et al. (CCS 2019) designed a volume-hiding EMM scheme from cuckoo hash dubbed dprfMM. However, we observe that all the existing volume-hiding EMMs focus only on queries over a single key. Although the state-of-the-art conjunctive queries scheme OXT (CRYPTO 2013) can achieve sub-linear search complexity for conjunctive queries, it reveals the real volumes of the queried keys. Therefore, it is desirable to explore the volume-hiding encrypted multi-maps supporting conjunctive queries. In this paper, we initiate the study of volume-hiding EMM supporting conjunctive queries. We present, to our best knowledge, the first volume-hiding conjunctive EMM scheme OXTMM. Compared with the state-of-the-art volume-hiding single-key EMM scheme dprfMM, our proposed OXTMM can guarantee that the real volume of each key is hidden while supporting efficient conjunctive queries, the query communication overhead is $2\ell$ encrypted key/value pairs together with a succinct data structure. Bloom filter, where $\ell$ is the maximum volume of all keys. In addition, we prove the security of our proposed OXTMM and give a thorough efficiency analysis between our proposal and the existing constructions. Finally we implement OXTMM and compare it with the most efficient scheme OXT. Experiments result demonstrates that OXTMM can achieve volume-hiding conjunctive queries with a moderate efficiency loss.

**Keywords:** Encrypted search · Volume-hiding · Conjunctive queries

# 1 Introduction

Structured Encryption (STE), introduced by Chase and Karama [7], enables the
data owner to outsource an encrypted data structure to an untrusted party, e.g.,

© IFIP International Federation for Information Processing 2022

Published by Springer Nature Switzerland AG 2022

W. Meng et al. (Eds.): SEC 2022, IFIP AICT 648, pp. 467–485, 2022.

https://doi.org/10.1007/978-3-031-06975-8_27
the cloud server, while maintaining the ability to access it. An STE scheme is
secure if it reveals nothing about the structure and queried key beyond the pre-
defined leakage. Encrypted multi-map (EMM) is a classic instance of structured
encryption, which is utilized to achieve optimal search over encrypted data [2, 3, 5].

Searchable Symmetric Encryption (SSE), a special case of STE, is initialed
by Song et al. [29] and well studied in the past two decades [2, 3, 6, 8, 18, 22, 30].
Among that, a line of work has focused on the attack caused by some leak-
ages [4, 14, 25]. Very recently, Kellaris et al. [19] introduced a new data recovery
attack via communication volume (i.e., the number of the matched documents
for a query). Since then, some volume-based attacks on SSE has been presented
[1, 11, 12, 27]. To suppress the volume leakage, Kamara and Moataz [16] initialed
the study on volume-hiding STE and presented the first volume-hiding EMM
scheme with densest subgraph transform. To further reduce the query and stor-
age overhead, Patel et al. [26] introduced an efficient volume-hiding EMM scheme
from cuckoo hash. The main idea is to assign each key/value pair to one of the
two possible positions associated with two tables of cuckoo hash and pad all
remaining empty positions with dummy strings. As a result, the total storage
overhead is very close to $2 \cdot (1 + \alpha)n$ while the query overhead is $2\ell$, where $n$
and $\ell$ refer to the total number of key/value pairs and the maximum volume
length of all keys respectively, and $\alpha > 0$. However, we observe that both the
mentioned solutions focus only on a single key search.

To achieve volume-hiding EMM supporting conjunctive queries, a naive way
is to perform multiple-round single-key queries in a volume-hiding EMM and
obtain the intersection of queries. However, as indicated by [6], it results in too
much search overhead (i.e. all the matched values associated with each queried
key) and leakages (i.e. the encrypted key/value pairs associated with all the
 queried keys). Note that, in an ideal volume-hiding conjunctive EMM, the client
 always receives $\ell$ matched results for each query, and learns the intersection
 values that are satisfied with query criteria. Intuitively, we can obtain volume-
hiding EMM supporting conjunctive queries from secure conjunctive keyword
search SSE. To clarify our technical overview, we provide a brief sketch of the
state-of-the-art conjunctive SSE OXT by Cash et al. [6]. The basic framework
of OXT relies on two new data structures, i.e. TSet and XSet. TSet is respon-
sible to retrieve all the documents matching with the least frequent keyword
of a conjunctive query, while XSet is used to check whether the retrieved docu-
ments from TSet satisfy the query condition. For example, given conjunctive keys
{key₁, key₂, ..., keyₛ}, the client will send a search token for the least frequent key
(named tokkey₁) along with a set of intersection tokens (named xtraps) for the
remaining keys to the server. Then, the server will retrieve the values MM[key₁]
associated with key₁ by tokkey₁ in TSet. After that, the server will obtain xtag
by xtraps and check the existence of xtag in XSet to filter MM[key₁] and obtain
the intersection values MM[key₁] ∩ MM[key₂] ∩ ... ∩ MM[keyₛ]. Finally, the client
can receive the final matching results for the conjunctive query. Nevertheless, we
argue that OXT leaks some response pattern such as the intersection of all the
queried keys and the real volume of key₁, which may suffer from volume-based
attacks. Thus, a natural question arises as follows:
*Is there an efficient volume-hiding EMM scheme supporting conjunctive queries?*

In this paper, we initiate the study on volume-hiding EMM supporting conjunctive queries. That is, the client sends a conjunctive query to the server and receives the matching results satisfying the search criterion, while the server will not learn the real volume for any key.

**Our Contributions.** We present, to our best knowledge, the first volume-hiding conjunctive EMM scheme OXTMM from OXT [6], which eliminates the corresponding volume leakages in OXT. More specifically, we built TSet for all keys in the style of volume-hiding to suppress the volume leakage of the least-frequent key. Note that the server in OXT can check whether the matched documents from TSet contain the remaining keys. It reveals the result pattern (i.e., the number of retrieved documents). To address this issue, we transfer the checkability of XSet from the server to the client. That is, the server is to only generate all the tags *xtag* for the remaining keys in a conjunctive query and send the encrypted message which contains whether the tags *xtag* exist in XSet to the client. To optimize the communication overhead, we adopt the Bloom filter, a succinct data structure, to store all the corresponding message.

To ensure the security of our scheme OXTMM, we introduce its leakage functions and then prove that the STE scheme OXTMM is volume-hiding and adaptively secure, which refers to [6, 22, 26]. Note that there are additional leakages from *xtrap* and *xtag*, different from [26]. Finally, we implement our proposed scheme OXTMM and OXT [6]. Compared with OXT, OXTMM can achieve volume-hiding conjunctive queries with a moderate efficiency loss.

## 1.1 Related Work

Structured Encryption [7], introduced by Chase and Kamara, can be widely used in outsourced encrypted data structures, such as encrypted graph [23], encrypted relational database [15]. As a special case of structured encryption, searchable encryption was intialized by Song et al. [29] and has been well-studied in terms of security [2, 8, 30], functionality [6, 18], and performance [24].

Golle et al. [10] proposed the first conjunctive SSE scheme with linear search complexity. To achieve sub-linear SSE schemes with supporting conjunctive queries, Cash et al. [6] designed a new conjunctive SSE protocol named OXT with sub-linear search complexity, where they introduced an additional data structure XSet to store all the pairs of keywords and identifiers of documents containing them. As a result, its search complexity is only depended on the number of results matching the least frequent queried keyword. Subsequently, Lai et al.[22] proposed a primitive, called hidden vector encryption, to construct a new conjunctive SSE scheme with result pattern hiding. To further improve security in the malicious server, Wang et al. [32] developed the verifiable SSE-conjunctions scheme, which is based on the accumulator.
Another line of structured encryption is to disclose as few leakages as possible due that some “reasonable” leakages may be used to launch some leakage-abuse attacks [4, 14, 25]. In these years, Kellaris et al. [19] developed a novel attack for range queries by exploiting volume leakages, called volume attack. To deal with volume leakages, Kamara et al. [16] firstly discussed the volume-hiding property and then introduced the volume-hiding schemes for multi-maps. Their scheme can achieve the storage overhead $\Theta(n)$ and search overhead $\ell \cdot \log n$ by planted densest subgraph, where $\ell$ is the maximum volume length and $n$ is the total number of key/value pairs in a multi-map. To reduce the storage and search overhead, Patel et al. [26] considered the volume-hiding encrypted multi-map schemes based on cuckoo hash with a stash [21] and delegatable PRF [20]. Their scheme, named dprfMM, can achieve the storage overhead $2(1 + \alpha)n$ and search overhead $2 \cdot \ell$, where $\alpha > 0$ is a constant number. To enrich functionality, Ren et al. [28] introduced a volume-hiding scheme with support for range queries based on trusted hardware. After that, more and more works focus on the volume-hiding property [9, 13, 31].

# 2 Preliminaries

In this section, we briefly review the volume-hiding scheme and then introduce the detailed security definition for volume-hiding EMM.

## 2.1 Volume-Hiding Encrypted Multi-Maps

Patel et al. [26] presented an efficient volume-hiding EMM scheme from delegatable PRF and cuckoo hash, dubbed dprfMM, which can support asymptotically optimal storage as well as query complexity. We here recall the detailed description of dprfMM as follows:

- dprfMMözup(1$^{\lambda}$, MM): The client adopts the security parameter $\lambda$ to generate private keys $K_E, K_D \in \{0, 1\}^{\lambda}$ for IND-CPA encryption function and delegatable PRF (dPRF), $F = (F.GenTok, F.Eval)$ [20] respectively. Two cuckoo hash tables $T_1, T_2$ of size $(1 + \alpha)n$ and a local stash are initialized, where $n$ is the total number of key/value pairs in the multi-map and $\alpha$ is a constant number. After that, each key/value pair in the multi-map MM is inserted into one of two tables by cuckoo hash with a stash, and delegatable PRF is used to determine the location associated with the key/value pair (cf. Line 5–28). Note that the key/value pairs which cannot be inserted into the cuckoo hash tables after $d \log n$ evictions, are placed into the local stash. After that, each empty location in two tables will be filled with the dummy and then encrypted, while others will be encrypted. Finally, the encrypted cuckoo hash tables will be sent to the server. The private keys $K \leftarrow (K_E, K_D, Stash)$ are held in the client.

- dprfMM quer( K, key): To perform a single-key query on key, the client generates the search token $tok_{key}$ by the private key $K$ and the delegatable PRF, then send it to the server.
<caption>**Algorithm 1.** The Construction of dprfMM</caption>

**Setup(1<sup>λ</sup>, MM)**
1: $K_D, K_E \leftarrow \{0, 1\}^\lambda$
2: MM = $\{(key_i, \vec{v}_i)\}$, where $i \in [m]$
3: $T_1, T_2 \leftarrow \phi$, where $|T_1| = |T_2| = (1+\alpha)n$ and $n = \Sigma_{i \in [m]} |\vec{v}_i|$
4: Stash $\leftarrow \phi$
5: **for** $i \in [m]$ and $j \in [[\vec{v}_i]]$ **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;count $\leftarrow 0, tmp \leftarrow false$
7: &nbsp;&nbsp;&nbsp;&nbsp;**while** count $< d \log n$ **do**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $t \in [1, 2]$ **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pos $\leftarrow F_{K_D}(key_i||j||t)$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $T_t[\text{pos}] = \text{null}$ **then**
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$T_t[\text{pos}] \leftarrow (i, j)$
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp $\leftarrow true$
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Break
14: &nbsp;&nbsp;&nbsp;&nbsp;**else**
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(i', j') $\leftarrow T_t[\text{pos}]$
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$T_t[\text{pos}] \leftarrow (i, j)$
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(i, j) $\leftarrow (i', j')$
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;count $\leftarrow count + 1$
19: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
20: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
21: &nbsp;&nbsp;&nbsp;&nbsp;**if** tmp $= true$ **then**
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Break
23: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
24: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
25: &nbsp;&nbsp;&nbsp;&nbsp;**if** count $= d \log n$ **then**
26: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Stash $\leftarrow (key_i, \vec{v}_i[j])$
27: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
28: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
29: &nbsp;&nbsp;&nbsp;&nbsp;**if** $|\text{Stash}| > f(n)$ **then**
30: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Abort
31: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
32: &nbsp;&nbsp;&nbsp;&nbsp;**for** $t \in [1, 2]$ and $u \in [[T_t]]$ **do**
33: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $T_t[u] = \text{null}$ **then**
34: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$T_t[u] \leftarrow \text{Enc}(K_E, \perp)$
35: &nbsp;&nbsp;&nbsp;&nbsp;**else**
36: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(i, j) $\leftarrow T_t[u]$

- dprfMM.Reply(*tok*<sub>*key*</sub>, *EMM*): After receiving the token *tok*<sub>*key*</sub>, the server generates 2ℓ locations by delegatable PRF and then returns results (i.e. *CT*<sub>*key*</sub>) associated with these locations.

- dprfMM.Result(*K*, *key*, *CT*<sub>*key*</sub>): Upon receiving *CT*<sub>*key*</sub>, the client uses the private key *K*<sub>*E*</sub> to decrypt each encrypted key/value pair in *CT*<sub>*key*</sub> and puts the values associated with *key* into *R*<sub>*key*</sub>. Except that, client also needs to query *key* in the local stash and put the values associated with *key* to *R*<sub>*key*</sub>. Finally, the client obtains the values *R*<sub>*key*</sub> associated with the queried key.
## 2.2 Structured Encryption

In this section, we review definitions of structured encryption [17, 26] to analyze the security of our scheme. The aim of designing an STE scheme is to protect the security of the data owner to perform operations in the third untrusted party without leaking any information about data structure beyond what we define.

**Definition 1** (non-interactive, STE for MMs). A non-interactive STE scheme $\sum_{STE} = (\text{Setup}, \text{Query})$ is defined as following algorithms:

* $(K, \text{EMM}) \leftarrow \text{Setup}(1^{\lambda}, \text{MM}) : \text{It inputs the security parameter } \lambda \text{ as well as a multi-map MM. It outputs a private key } K \text{ for the client, and an encrypted multi-map EMM for the server.}$

* $\text{MM}[\psi(\mathbf{key})] \leftarrow \text{Query}(K, \psi(\mathbf{key}), \text{EMM}) : \text{It inputs the private key } K, \text{ a query } \psi(\mathbf{key}) \text{ as well as an encrypted multi-map EMM. The output is } \text{MM}[\psi(\mathbf{key})] \text{ matching the query } \psi(\mathbf{key})$.

In STE, the security of a structured encryption scheme is determined by two leakage functions, $\mathcal{L}_{\text{Setup}}$ and $\mathcal{L}_{\text{Query}}$. In Setup phase, a structured encryption scheme for multi-maps leaks no information about its construction beyond the leakage information $\mathcal{L}_{\text{Setup}}$. In Query protocol, the communication between the client and server leaks no information about the structure and the queries beyond the leakage information $\mathcal{L}_{\text{Query}}$. Then we move on to formally introduce the security notion.

**Definition 2** Let $\Sigma = (\text{Setup, Query})$ be the non-interactive structured encryption scheme for multi-maps. And we consider the following experiments that $\mathcal{A}$ is a stateful semi-honest PPT adversary and $\mathcal{S}$ is a stateful PPT simulator, $\mathcal{L}_{\text{Setup}}$ and $\mathcal{L}_{\text{Query}}$ are leakage functions.

In the real game $\textbf{Real}_{\Sigma, \mathcal{A}}(1^{\lambda})$, there are two PPT players, i.e. an adversary $\mathcal{A}$ and a challenger $\mathcal{C}$, as follow:

1. The adversary $\mathcal{A}$ chooses a multi-map MM to send to the challenger $\mathcal{C}$.

2. Upon receiving the multi-map MM, $\mathcal{C}$ executes $(K, \text{EMM}) \leftarrow \text{Setup}(1^{\lambda}, \text{MM})$ to get private key $K$ and returns the encrypted multi-map EMM to $\mathcal{A}$.

3. The adversary $\mathcal{A}$ adaptively chooses a polynomial number of queries $(q_0, ..., q_{\text{ploy}(\lambda)})$ to send to $\mathcal{C}$.

4. For each query $q_i$, the challenger $\mathcal{C}$ interacts with the adversary $\mathcal{A}$ by Query protocol.

5. After the experiment, $\mathcal{A}$ outputs a bit.

In the ideal game $\textbf{Ideal}_{\Sigma, \mathcal{A}, \mathcal{S}}(1^{\lambda})$, there are two PPT players, i.e. an adversary $\mathcal{A}$ and a simulator $\mathcal{S}$, as follow:

1. The adversary $\mathcal{A}$ chooses a multi-map MM.

2. By receiving $\mathcal{L}_{\text{Setup}}(\text{MM})$, the simulator $\mathcal{S}$ returns an encrypted multi-map EMM to $\mathcal{A}$.
3. The adversary $\mathcal{A}$ adaptively chooses a polynomial number of queries $(q_0, ..., q_{ploy}(\lambda))$.

4. For each query $q_i$, the simulator $\mathcal{S}$ interacts with the adversary $\mathcal{A}$ by using $\mathcal{L}_{Query}(MM, q_0, ..., q_{i-1})$.

5. After the experiment, $\mathcal{A}$ outputs a bit.

The non-interactive STE scheme is adaptively $(\mathcal{L}_{Setup}, \mathcal{L}_{Query})$-secure for all PPT adversaries $\mathcal{A}$ if there is a PPT simulator $\mathcal{S}$:

$$|\Pr[\mathbf{Real}_{\Sigma, \mathcal{A}}(1^{\lambda}) = 1] - \Pr[\mathbf{Ideal}_{\Sigma, \mathcal{A}, \mathcal{S}}(1^{\lambda}) = 1]| < \text{negl}(\lambda)$$

## 2.3 Leakage Functions for Conjunctive Queries

In this section, we review typical leakage functions for conjunctive queries schemes [6,22]. Note that a conjunctive query $\psi(\mathbf{key})$ for structured encryption consists of a set of search keys, i.e. $\mathbf{key} = (key_1, ..., key_s)$, where $\psi$ is a boolean formula. Without loss of generality, we consider that each conjunctive query consists of $s$ search keys. And we call that stem is the first search key and xterm is the other search key in the conjunctive query. For a set of conjunctive queries $\mathbf{q} = (fk, xk_2, ..., xk_s)$, there are a sequence of sters $fk$ as well as a list of xterms $(xk_2, ..., xk_s)$.

- **Domain Size (dsize)**: it reports the number of total key/value pairs in a multi-map MM. That is $dsize(MM) = n$.

- **Query Equality (qeq)**: it reports whether the same stem is performed in two queries. That is a two-dimensional table M for given a set of keys, where $M[i][j] = 1$ if and only if $fk[i] = fk[j]$.

- **Response Length (rlen)**: it reports the number of values for the queried stem in a multi-map MM. That is $rlen(MM, fk[i]) = |MM(fk[i])|$.

- **Maximum Response Length (mrlen)**: it reports the maximum number of values for a key in a multi-map MM. That is $mrlen(MM) = l$.

- **Result Pattern (rp)**: it reports the intersection of all the search keys in a conjunctive query. That is an array R, where $R[i] = MM(fk[i]) \cap \bigcap_{j=2}^{s} MM(xk_j[i])$.

- **Conditional Intersection Pattern (ip)**: it reports the intersection of two different conjunctive queries. That is a four-dimensional table IM where $IM[i, j, p, q] = MM(fk[i]) \cap MM(fk[j])$ if $i \neq j, p \neq q$ and $xk_p[i] = xk_q[j]$.

Thus, the aim of our volume-hiding STE-conjunctions scheme is to eliminate the leakage of response length and result pattern.

## 2.4 Volume-Hiding Leakage Functions

In this section, we recall the volume-hiding leakage function, which is defined in [26]. Note that we modify the query protocol to adapt to our volume-hiding scheme with support for conjunctive queries.
**Definition 3** We consider the game $VHG_{\eta}^{A,\mathcal{L}}$ which consists of the leakage $\mathcal{L} = (\mathcal{L}_{Setup}, \mathcal{L}_{Query})$, the adversary $\mathcal{A}$, the challenger $\mathcal{C}$ as well as a constant $\eta \in \{0, 1\}$.

- Given the number of total key/value pairs $n$ and maximum volume length $\ell$, the adversary $\mathcal{A}$ can produce two different signatures $S_0 = \{(key_i, \ell_0(key_i))\}_{i \in [m]}$ and $S_1 = \{(key_i, \ell_1(key_i))\}_{i \in [m]}$ with the same $n$ and $\ell$.

- Given two signatures $S_0$ and $S_1$, the challenger $\mathcal{C}$ randomly selects $S_\eta$ to generate a multi-map $MM_\eta$, which is filled with randomly chosen key/value pairs. And then an encrypted multi-map is obtained by $MM_\eta$. After that, the challenger $\mathcal{C}$ sends $\mathcal{L}_{Setup}$ to $\mathcal{A}$.

- The adversary $\mathcal{A}$ chooses different conjunctive keys $(\psi(\mathbf{key}_1), ..., \psi(\mathbf{key}_p))$ for queries. And then, the challenger $\mathcal{C}$ will return $\mathcal{L}_{Query}$ to $\mathcal{A}$.

- Eventually, $\mathcal{A}$ outputs a bit $b \in \{0, 1\}$.

The leakage function $\mathcal{L} = (\mathcal{L}_{Setup}, \mathcal{L}_{Query})$ is volume-hiding when it can satisfy

$$p_0^{A,\mathcal{L}}(n, \ell) = p_1^{A,\mathcal{L}}(n, \ell)$$

for all adversaries $\mathcal{A}$ and $n \ge \ell \ge 1$, where $p_{\eta}^{A,\mathcal{L}}(n, \ell)$ denotes the probability that the adversary $\mathcal{A}$ outputs '1' during the game $VHG_{\eta}^{A,\mathcal{L}}$. Note that the adversary can only choose the queried keys and obtain the response in the query phase.

# 3 Volume-Hiding EMM Supporting Conjunctive Queries

In this section, we first give a high-level idea of our volume-hiding EMM scheme supporting conjunctive queries OXTMM. In the following, we further present it in detail.

## 3.1 High-Level Idea

To design volume-hiding EMM supporting conjunctive queries, our starting point is to suppress volume-related leakages information from the state-of-the-art conjunctive SSE scheme OXT. More concretely, we first need to hiding the real volume of the least frequent key (i.e., $key_1$) in a conjunctive query. To this end, what we need to do is insert a multi-map $MM = \{(key, \vec{v})\}$ into the cuckoo hash tables (i.e., TSet) while padding all the remaining locations with dummies. As a result, all queries over either single or conjunctive keys will return $2\ell$ search results. Furthermore, we focus on how to obfuscate the exact number of the documents that satisfy the conjunctive query condition. Specifically, recalling that the server in OXT builds an additional data structure called XSet and stores all $(key, \vec{v}[j])_{j \in |MM[key]|}$ for all document identities (i.e., $\vec{v}[j]$) and key contained in $\vec{v}[j]$. By this way, the server can retrieve the final result for conjunctive query condition by checking whether $(key_i, \vec{v}[j])_{i \in [2,s]}$ in XSet. We argue that it is necessary to avoid the mentioned leakage in volume-hiding conjunctive queries setting. For this purpose, we store all Hash($K_H, key || \vec{v}[j]$) with $K_H$ to cuckoo hash table. As a result, the server will no longer distinguish the real hash value from dummies and send all the $4\ell(s-1)$ hash values to the client. In addition, we insert all the hash values into the bloom filter to optimize the response overhead.
## 3.2 The Concrete Construction

Our proposed OXTMM adopts (1) the cuckoo hash with a stash, where $\alpha$, $d$ are the constants for table size and the maximum number of evictions respectively, (2) a bloom filter which consists of an array BF as well as $c$ hash functions $\{H_q\}_{q \in [c]}$, (3) a group $G$ with prime order $p$ as well as the generator $g$, (4) hash functions $h$ that outputs values in range $[(1 + \alpha)n]$ and Hash that outputs values in $\mathcal{Y}$, (5) the PRF $F_p$ with range $Z_p^*$, (6) a volume-hiding single-key scheme dprfMM [26], depicted in Sect. 2.1.

<table><caption>**Algorithm 2.** The Setup of OXTMM</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Setup(1<sup>λ</sup>, MM)</td><td>26: count ← count + 1<br>27: end if<br>28: end for<br>29: if tmp = true then<br>30: Break<br>31: end if<br>32: end while<br>33: if count = d log n then<br>34: Stash ← (key<sub>i</sub>, v&#773;<sub>i</sub>[j])<br>35: end if<br>36: end for<br>37: if |Stash| > f(n) then<br>38: Abort<br>39: end if<br>40: for t ∈ [1, 2] and u ∈ [|T<sub>t</sub>|] do<br>41: if T<sub>t</sub>[u] = null then<br>42: T<sub>t</sub>[u] ← {0, 1}<sup>Y</sup><br>43: else<br>44: (i, j) ← T<sub>t</sub>[u]<br>45: T<sub>t</sub>[u] ← Hash(K<sub>H</sub>, key<sub>i</sub> || v&#773;<sub>i</sub>[j])<br>46: end if<br>47: end for<br>48: K<sub>T</sub> ← (K<sub>I</sub>, K<sub>Z</sub>, K<sub>X</sub>, K<sub>H</sub>, Stash)<br>49: XMM ← (T<sub>1</sub>, T<sub>2</sub>)<br>50: EXMM ← (EMM, XMM)<br>51: return (K<sub>T</sub>; EXMM)</td></tr><tr><td>1: K<sub>I</sub>, K<sub>Z</sub>, K<sub>X</sub>, K<sub>H</sub> ← {0, 1}<sup>λ</sup></td><td></td></tr><tr><td>2: MM = {(key<sub>i</sub>, v&#773;<sub>i</sub>)}, where i ∈ [m]</td><td></td></tr><tr><td>3: T<sub>1</sub>, T<sub>2</sub> ← φ, where |T<sub>1</sub>| = |T<sub>2</sub>| = (1 + α)n and n = Σ<sub>i∈[m]</sub>|v&#773;<sub>i</sub>|</td><td></td></tr><tr><td>4: Stash, xlist, YMM ← φ</td><td></td></tr><tr><td>5: for i ∈ [m] and j ∈ [|v&#773;<sub>i</sub>] do</td><td></td></tr><tr><td>6: xv ← F<sub>p</sub>(K<sub>I</sub>, v&#773;<sub>i</sub>[j])</td><td></td></tr><tr><td>7: z<sub>k</sub> ← F<sub>p</sub>(K<sub>Z</sub>, key<sub>i</sub> || j)</td><td></td></tr><tr><td>8: y ← xv · z<sub>k</sub><sup>-1</sup></td><td></td></tr><tr><td>9: xlist[i][j] ← g<sup>xv · F<sub>p</sub>(K<sub>X</sub>, key<sub>i</sub>)</sup></td><td></td></tr><tr><td>10: YMM ← (key<sub>i</sub>, v&#773;<sub>i</sub>[j], y)</td><td></td></tr><tr><td>11: end for</td><td></td></tr><tr><td>12: (K, EMM) ← dprfMM Gibbey(1<sup>λ</sup>, YMM)</td><td></td></tr><tr><td>13: for i ∈ [m] and j ∈ [|v&#773;<sub>i</sub>] do</td><td></td></tr><tr><td>14: count ← 0, tmp ← false</td><td></td></tr><tr><td>15: while count &lt; d log n do</td><td></td></tr><tr><td>16: for t ∈ [1, 2] do</td><td></td></tr><tr><td>17: pos ← h(xlist[i][j]||t)</td><td></td></tr><tr><td>18: if T<sub>t</sub>[pos] = null then</td><td></td></tr><tr><td>19: T<sub>t</sub>[pos] ← (i, j)</td><td></td></tr><tr><td>20: tmp ← true</td><td></td></tr><tr><td>21: Break</td><td></td></tr><tr><td>22: else</td><td></td></tr><tr><td>23: (i', j') ← T<sub>t</sub>[pos]</td><td></td></tr><tr><td>24: T<sub>t</sub>[pos] ← (i, j)</td><td></td></tr><tr><td>25: (i, j) ← (i', j')</td><td></td></tr></tbody></table>

**Setup(1<sup>λ</sup>, MM):** The client takes as input the security parameter $\lambda$, and generates the private keys $(K_I, K_Z, K_X, K_H)$. Then two cuckoo tables $T_1, T_2$ with size $(1 + \alpha)n$ as well as a stash *Stash* are initialized, where $n$ refers to the total number of key/value pairs in a multi-map. Similar to the construction of OXT, the blinded value $y$ and the tag *xtag* will be computed and then pushed into
YMM $\leftarrow (key_i, \vec{i}[j], y)$ and $xlist \leftarrow xtag$ (cf. Line 5–11), respectively. Then, the client generates an encrypted multi-map EMM and a private key $K$ by invoking dprfMM.setup for the multi-map YMM. Note that the blinded value $y$ is not encrypted and only stored with its relevant encrypted key/value pair in dprfMM.setup. And each key/value pair should be put into the EMM while not in the local stash to ensure the integrity of search results for the first search key. Thus, we need to replace the way of storing into a stash with randomly reselecting dPRFs after $d \log n$ evictions in dprfMM.setup. After that, similar to the construction of dprfMM, each key/value pair will be inserted into a location in two cuckoo tables or the local stash (cf. Line 13–36). However, the different point is that each location is determined by the xtag (i.e. xlist[i][j]), which is constructed as in OXT. And then, each empty location in two tables will be filled with dummies, while others are hashed. Finally, the client holds the private key $K_T \leftarrow (K, K_I, K_Z, K_X, K_H, Stash)$ and sends the encrypted multi-map EXMM $\leftarrow (T_1, T_2, EMM)$.

<table><caption>**Algorithm 3.** The Query of OXTMM</caption><tr><td>Query(K<sub>T</sub>, ψ(key), EXMM)</td><td>24: for q ∈ [c] do</td></tr><tr><td>Client:</td><td>25: BF[H<sub>q</sub>(XMM[pos<sub>t'</sub>])] ← 1</td></tr><tr><td>1: (K, K<sub>I</sub>, K<sub>Z</sub>, K<sub>X</sub>, K<sub>H</sub>, Stash) ← K<sub>T</sub></td><td>26: end for</td></tr><tr><td>2: (key<sub>1</sub>, key<sub>2</sub>, ..., key<sub>s</sub>) ← ψ(key)</td><td>27: end for</td></tr><tr><td>3: tok<sub>key<sub>1</sub></sub> ← dprfMM quer( K, key<sub>1</sub>)</td><td>28: end for</td></tr><tr><td>4: xtoken ← φ</td><td>29: return (CV<sub>key<sub>1</sub></sub>, BF, {H<sub>q</sub>}<sub>q∈[c]</sub>)</td></tr><tr><td>5: for j ∈ [l] do</td><td>Client:</td></tr><tr><td>6: η<sub>key<sub>1</sub></sub> ← F<sub>p</sub>(K<sub>Z</sub>, key<sub>1</sub>||j)</td><td>30: (K, K<sub>I</sub>, K<sub>Z</sub>, K<sub>X</sub>, K<sub>H</sub>, Stash) ← K<sub>T</sub></td></tr><tr><td>7: for k ∈ [2, s] do</td><td>31: (key<sub>1</sub>, key<sub>2</sub>, ..., key<sub>s</sub>) ← ψ(key)</td></tr><tr><td>8: xtoken[j][k] ← g<sup>η<sub>key<sub>1</sub></sup> F<sub>p</sub>(K<sub>X</sub>, key<sub>k</sub>)</td><td>32: R<sub>key<sub>1</sub></sub>, MR<sub>key</sub> ← φ</td></tr><tr><td>9: end for</td><td>33: R<sub>key<sub>1</sub></sub> ← dprfMM result(K, CV<sub>key<sub>1</sub></sub>)</td></tr><tr><td>10: end for</td><td>34: for val ∈ R<sub>key<sub>1</sub></sub> do</td></tr><tr><td>11: return (tok<sub>key<sub>1</sub></sub>, xtoken)</td><td>35: tmp ← true</td></tr><tr><td>Server:</td><td>36: for k ∈ [2, s] and q ∈ [c] do</td></tr><tr><td>12: EY<sub>key<sub>1</sub></sub>, CV<sub>key<sub>1</sub></sub> ← φ</td><td>37: xkv ← Hash(K<sub>H</sub>, key<sub>k</sub>||val)</td></tr><tr><td>13: (K, K<sub>I</sub>, K<sub>Z</sub>, K<sub>X</sub>, K<sub>H</sub>, Stash) ← K<sub>T</sub></td><td>38: if BF[H<sub>q</sub>(xkv)] ≠ 1 then</td></tr><tr><td>14: (EMM, XMM) ← EXMM</td><td>39: if (key<sub>k</sub>, val) ∉ Stash then</td></tr><tr><td>15: (key<sub>1</sub>, key<sub>2</sub>, ..., key<sub>s</sub>) ← ψ(key)</td><td>40: tmp ← false</td></tr><tr><td>16: BF ← 0<sup>b</sup>, {H<sub>q</sub>}<sub>q∈[c]</sub> : {0, 1}<sup>y</sup> → [b]</td><td>41: Break</td></tr><tr><td>17: EY<sub>key<sub>1</sub></sub> ← dprfMM reply (tok<sub>key<sub>1</sub></sub>, EMM)</td><td>42: end if</td></tr><tr><td>18: for j ∈ [l] and t ∈ [1, 2] do</td><td>43: end if</td></tr><tr><td>19: (e, y) ← EY<sub>key<sub>1</sub></sub> [j][t]</td><td>44: end for</td></tr><tr><td>20: CV<sub>key<sub>1</sub></sub> ← e</td><td>45: if tmp = true then</td></tr><tr><td>21: for k ∈ [2, s] and t' ∈ [1, 2] do</td><td>46: MR<sub>key</sub> ← val</td></tr><tr><td>22: xtag ← xtoken[j][k]<sup>y</sup></td><td>47: end if</td></tr><tr><td>23: pos<sub>t'</sub> ← h(xtag||t')</td><td>48: end for</td></tr><tr><td></td><td>49: return MR<sub>key</sub></td></tr></table>
**Query**($K_T$, $\psi$(**key**), EXMM): To perform a conjunctive query on $\psi$(**key**), the client starts to generate the token $tok_{key_1}$ associated with the first key by invoking dprfMM.Quality, and intersection tokens $xtoken$ which are constructed as in OXT. And then, the client sends ($tok_{key_1}$, $xtoken$) to the server. Upon receiving search tokens ($tok_{key_1}$, $xtoken$), the server randomly chooses hash functions and initializes a bloom filter of size $b = 1.44 \log_2(1/P_e) \cdot (4\ell \cdot (s-1))$, where $P_e$ is the false probability. After that, in EMM, $2\ell$ tuples $(e, y)$ are obtained by $2\ell$ locations, which are calculated by $tok_{key_1}$ with dprfMM.Reply. In these tuples, the encrypted key/value pairs $e$ are stored into $CV_{key_1}$ and blinded values $y$ are used to get $xtag$ with $xtoken$, similar to OXT. Subsequently, each $xtag$ is mapped into two locations in XMM and its corresponding hash values $XMM[h(xtag||t')]_{t' \in [1,2]}$ are obtained. Note that the server cannot determine which hash values can meet the requirement for search keys in our volume-hiding scheme. Thus, all the hash values should be sent back to the client. In order to reduce communication cost, each hash value will be inserted into the bloom filter BF. Finally, the encrypted key/value pairs $CV_{key_1}$ and the bloom filter BF with its hash functions $\{H_q\}_{q \in [c]}$ will be sent to the client. After receiving search results for the conjunctive query, the client will get values *val* associated with the first search key in $CV_{key_1}$ by invoking dprfMM.Result. Next, the client will generate hash values for the value *val* with the other search keys. Finally, its all hash values will be tested whether they exist in the bloom filter BF or their key/value pairs exist in the local stash *Stash*. If they can satisfy either of these two requirements, *val* will be put into $MR_{key}$. And the client obtains intersection results $MR_{key}$ for all queried keys.

## 3.3 Security Analysis

To analyze the security of our scheme OXTMM, we depict its leakage $\mathcal{L} = (\mathcal{L}_{Setup}, \mathcal{L}_{Query})$. In the setup phase, it reveals the number of total key/value pairs because of $2(1+\alpha)n$ encrypted key/value pairs and blinded values as well as hash values respectively, i.e. $\mathcal{L}_{Setup} = \text{dsize}(\text{MM}) = n$. For queries in an encrypted multi-map, it reveals the query equality and maximum volume length because of observing the search token and search results. Except that, conditional intersection pattern is also leaked, i.e. $\mathcal{L}_{Query} = (qeq, mrlen, ip)$.

To show the security of OXTMM, it requires to prove that our scheme OXTMM is adaptively $\mathcal{L}$-secure and has the volume-hiding property, where $\mathcal{L} = (\mathcal{L}_{Setup}, \mathcal{L}_{Query})$ is the leakage function for setup and query phases. Thus, there are two parts for the security proof, described below:

**Theorem 1** For constants $\alpha > 0$ and $f(n) = \omega(1)$, the STE scheme OXTMM is adaptively $\mathcal{L}$-secure for multi-maps, where $\mathcal{L} = (\text{dsize}, (qeq, mrlen, ip))$.

*Proof.* To prove that OXTMM is adaptively secure, we construct a simulator which consists of Setup and Query, shown in Algorithm.4. For all adversaries $\mathcal{A}$, we prove that the probability the real game **Real**$_{\Sigma, \mathcal{A}}(1^{\lambda})$ outputs '1' can be negligibly different from the probability the ideal game **Ideal**$_{\Sigma, \mathcal{A}, \mathcal{S}}(1^{\lambda})$ outputs '1', where $\Sigma$ is the OXTMM scheme and $\mathcal{S}$ is a simulator. Because our scheme
<table><caption>**Algorithm 4.** Simulator of OXTMM</caption><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>S.SimSetup(1<sup>λ</sup>, dsize)</td><td>5: if key<sub>i,1</sub> = key<sub>j,1</sub> then<br>6: State[ψ(<b>key<sub>j</sub></b>)][key<sub>j,1</sub>]<br>7: ← State[ψ(<b>key<sub>i</sub></b>)][key<sub>i,1</sub>]<br>8: if key<sub>j,k</sub> ∈ ψ(<b>key<sub>i</sub></b>) then<br>9: State[ψ(<b>key<sub>j</sub></b>)][key<sub>j,k</sub>]<br>10: ← State[ψ(<b>key<sub>i</sub></b>)][key<sub>j,k</sub>]<br>11: end for</td><td></td></tr><tr><td>1: n ← dsize<br>2: t<sub>s</sub> = 2 · (1 + α) · n<br>3: EMM, XMM ← φ, with the same size t<sub>s</sub><br>4: for i = 0 to t<sub>s</sub> do<br>5: e<sup>$</sup> ← {0, 1}<sup>λ</sup><br>6: y<sup>$</sup> ← Z<sub>p</sub><sup>*</sup><br>7: EMM[i] ← (e, y)<br>8: XMM[i] ← {0, 1}<sup>λ</sup><br>9: end for<br>10: EXMM ← (EMM, XMM)<br>11: return (⊥, EXMM)</td><td>12: end if<br>13: end for<br>14: if State[ψ(<b>key<sub>j</sub></b>)][key<sub>j,1</sub>] = null then<br>15: State[ψ(<b>key<sub>j</sub></b>)][key<sub>j,1</sub>] ← {0, 1}<sup>λ</sup><br>16: end if<br>17: for k = 2 to s do<br>18: if State[ψ(<b>key<sub>j</sub></b>)][key<sub>j,k</sub>] = φ then<br>19: (r<sub>1</sub>, ..., r<sub>l</sub>) ← $G<br>20: State[ψ(<b>key<sub>j</sub></b>)][key<sub>j,k</sub>] ← (r<sub>1</sub>, ..., r<sub>l</sub>)<br>21: end if<br>22: end for<br>23: return (State, State[ψ(<b>key<sub>j</sub></b>)])</td><td></td></tr><tr><td>S.SimQuery(1<sup>λ</sup>, qeq, mrlen, ip)</td><td>1: Using qeq(ψ(<b>key<sub>1</sub></b>), ..., ψ(<b>key<sub>j</sub></b>)) to analyze<br>ψ(<b>key<sub>j</sub></b>)<br>2: key<sub>j,1</sub>, ..., key<sub>j,s</sub> ← ψ(<b>key<sub>j</sub></b>)<br>3: for i = 1 to j − 1 do<br>4: key<sub>i,1</sub>, ..., key<sub>i,s</sub> ← ψ(<b>key<sub>i</sub></b>)</td><td></td></tr></tbody></table>

OXTMM is based on dprfMM, the security proof of OXTMM is similar to that of dprfMM [26]. Details can be found as below:

- $Game_0$ is identical to $Real_{\Sigma, A}(1^{\lambda})$.

- $Game_1$ replaces the PRF with a random function.

- $Game_2$ replaces the blinded values and tags with random values.

- $Game_3$ removes the cuckoo hash algorithm from OXTMM.setup.

- $Game_4$ replaces the hash functions with random functions.

- $Game_5$ replaces the encryption function Enc in dprfMM.setup with a random function.

- $Game_6$ replaces the outputs of random functions with uniformly picked random values.

- $Game_7$ replaces the dPRF in dprfMM with a random function.

Note that $Game_0$ and $Game_1$ are hardly distinguished by the security of PRFs. $Game_1$ and $Game_2$ are based on Diffie-Hellman assumption. $Game_2$ and $Game_3$ can be distinguished with negligible probability when $f(n) = \omega(1)$ in cuckoo hash with a stash. $Game_3$ and $Game_4$ are indistinguishable, based on the security of hash functions. $Game_4$ and $Game_5$ are computed indistinguishable by the security of encryption schemes. $Game_5$ and $Game_6$ are distinguished with negligible probability because of the outputs of identical distributions. $Game_6$ and $Game_7$ are computed indistinguishable by the security of dPRF [20]. Finally, we can obtain $Game_7$, which is identical to $Ideal_{\Sigma, A,S}(1^{\lambda})$.

**Theorem 2** The leakage function $\mathcal{L} = (dsize, (qeq, mrlen, ip))$ for the STE scheme OXTMM is volume-hiding.
Proof. To prove that the leakage function $\mathcal{L} = (dsize, (qeq, mrlen, ip))$ for OXTMM is volume-hiding, the adversary constructs two multi-map signatures of the same size $n$ and maximum volume length $\ell$ to the challenger. And the challenger randomly chooses a multi-map signature to generate an encrypted multi-map as well as a hashed multi-map and then interacts with the adversary. In OXTMM scheme, the setup leakage $\mathcal{L}_{Setup}$ consists of data size $dsize(MM) = n$. As for the query leakage $\mathcal{L}_{Query}$, it consists of the maximum volume length $mrlen(MM) = \ell$ as well as query equality $qeq$ and conditional intersection pattern $ip$. Note that the leakage of data size $dsize$ as well as maximum volume length $mrlen$ are identical in two multi-map signatures, and query equality $qeq$ is independent of the construction of a multi-map. As for conditional intersection pattern, it is only leaked to the challenger but not to the adversary. For a conjunctive query, there are two kinds of tokens to send to the challenger. The one is a token associated with the first search key, which is used to retrieve $2\ell$ encrypted key/value pairs to realize volume-hiding. It is identical to dprfMM [26]. And the others are $\ell \cdot (s - 1)$ intersection tokens, which are used to retrieve a bloom filter. And the bloom filter always contains $4(s - 1)\ell$ values which are independent of the volume of any key for hiding result pattern. Thus, the volume of all the queried keys can be hidden. Consequently, we can obtain that OXTMM is a volume-hiding scheme.

## 3.4 Efficiency Analysis

In this section, we theoretically compare our scheme OXTMM with the traditional conjunctive queries scheme (i.e. OXT) and volume-hiding scheme (i.e. dprfMM) in terms of server storage, token complexity, query complexity and functionality.

<table><caption>**Table 1.** Efficiency and functionality comparison</caption><thead><tr><th>STE scheme</th><th>Server storage</th><th>Token complexity</th><th>Response complexity</th><th>Volume-hiding</th><th>Conjunctive queries</th></tr></thead><tbody><tr><td>OXT [6]</td><td>st · m + (ev + y + x)n</td><td>tk + (s - 1)ℓ(key)xt</td><td>ℓ(ψ(key))ev</td><td>✗</td><td>✓</td></tr><tr><td>dprfMM [26]</td><td>2ekv(1 + α)n</td><td>tk</td><td>2ℓ · ekv</td><td>✓</td><td>✗</td></tr><tr><td>OXTMM</td><td>2(ekv + y + h)(1 + α)n</td><td>tk + (s - 1)ℓ · xt</td><td>2ℓ · ekv + BF(s, ℓ)</td><td>✓</td><td>✓</td></tr></tbody></table>

$st$: the stag in TSet; $ev$: an encrypted value; $ekv$: an encrypted key/value pair; $y$: the blinded value; $x$: the xtag in XSet; $h$: the hash value; $m$: the number of total keys; $n$: the number of total key/value pairs; $tk$: a search token; $xt$: the intersection tokens; $s$: the number of conjunctive keys; $\ell$: the maximum volume length; $\ell(key)$: the volume length associated with the key; $\psi(key)$: conjunctive search keys; $\alpha$: a constant for cuckoo hash, where $\alpha > 0$; $BF(s, \ell)$: a bloom filter which contains $4\ell(s - 1)$ values.

For server storage, it exists the extra values to perform auxiliary calculations in an STE-conjunctions scheme while the dummy values to pad in a volume-hiding scheme. Thus, in a volume-hiding scheme with support for conjunctive queries, it is necessary to add some extra and dummy values, which leads to much storage overhead but is indispensable. For token complexity, there is only
one token in a volume-hiding single-key query while some additional intersection
tokens for maintaining the privacy of other search keys in a conjunctive query. To
perform conjunctive queries, our scheme also needs intersection tokens which are
similar to an SSE-conjunctions scheme. The difference is that the volume length
of the first search key should be hidden, which causes many tokens in our scheme.
For response complexity, it only returns the intersection values associated with
all search keys in a conjunctive query while 2$\ell$ values in a volume-hiding single-
key query. To achieve the volume-hiding property, it is inevitable to pad dummy
values to maintain the same length in each query, which leads to more query
overhead than previous SSE-conjunctions schemes. And to suppress result pat-
tern, auxiliary values will be sent to the client to filter out the real values for all
search keys in a conjunctive query, which results in some expenses for response
complexity. In our scheme, there is some extra overhead, which is needed for
achieving volume-hiding and conjunctive queries.

4 Performance Evaluation

In this section, we compare the performance of our proposed scheme OXTMM
with the SSE-conjunctions scheme OXT [6]. We firstly describe the setup for two
experiments and then evaluate the overhead of setup and query phase.

4.1 Experiment Setup

We evaluate the performance of our scheme by adopting the same machine for
the players, i.e. the client and the server. The experimental machine is equipped
with Ubuntu PC operating system, Core(TM) i9-11900K and 3.50 GHz.

**Parameters.** In both experiments, we adopt multi-maps of size $n \in \{2^{13}, 2^{14}, 2^{15}, 2^{16}, 2^{17}\}$ with the maximum volume length $\ell \in \{2^5, 2^6, 2^7, 2^8, 2^9\}$, and the number of conjunctive search keys $s \in \{2, 3, 4, 5, 6\}$. To construct our proposed scheme, similar to [26], we choose the parameter $\alpha = 0.3$ for cuckoo hash with a stash. That is, cuckoo hash tables are filled with $2.6n$ entries. And for each insert operation, the entry will be stored into the local stash after $5 \log n$ evictions. To reach negligible false probability for the bloom filter, we choose 20 hash functions to map an entry to the filter.

**Primitives.** In two experiments, we implement the PRFs and hash functions by SHA-256. And we implement delegatable PRFs by constructing GGM tree [20]. For each key/value pair, it will be encrypted by AES and then a 32-byte ciphertext is obtained. For a single value, it only outputs a 16-byte ciphertext.

## 4.2 Evaluation and Comparison

**Setup Cost:** We start to evaluate the overhead of Setup phase in two schemes, which consists of storage and time overhead, shown in Fig. 1 and Fig. 2.

In OXT scheme, the storage overhead consists of two parts, i.e. TSet and XSet. Similar to OXT, the storage overhead of OXTMM is also composed of
<figure><img src="image_3.png" /><figcaption>Fig. 1. Setup storage comparison</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2. Setup time comparison</figcaption></figure>

two parts, i.e. EMM and XMM. However, the different point is that two parts
in OXTMM are constructed by the idea of the volume-hiding scheme dprfMM,
while TSet is constructed by inverted index and XSet is a collection in OXT.
For a multi-map of size *n*, an encrypted multi-map of size 2.6*n* will be generated
in dprfMM. Thus, our proposed scheme OXTMM needs more storage space than
OXT does, shown in Fig. 1. And in the aspect of time overhead, OXTMM is
slightly more than OXT, shown in Fig. 2. The reason is that, compared with
OXT, the extra elements in OXTMM are constructed by SHA-256 or AES, which
is much more efficient than exponential operation in both schemes.

**Query Cost:** In a volume-hiding STE scheme supporting conjunctive queries, there are two factors to affect the query overhead, i.e. the maximum volume length and the number of search keys. Thus, we then evaluate the overhead of query phase in these two schemes from the above two aspects, shown in Fig. 3, 4, 5 and 6.

To evaluate the impact of the maximum volume length, we select the first
search key in a conjunctive query as the key with the maximum volume length
and maintain the number of search keys as well as the same intersection results.
Due to the increase of maximum volume length associated with the first search
key, it leads to much more search token overhead in both schemes. Except for
the increase of search token, it also causes much more search results and the size
of the bloom filter in our volume-hiding scheme OXTMM, while not in OXT. In
a volume-hiding scheme, it needs to return search results of the same volume
length to avoid the volume attack. In a static multi-map, the server only returns
search results of the maximum volume length. And we construct OXTMM by
the volume-hiding scheme dprfMM. Thus, for query size overhead, the increase
of volume length does a more impact in OXTMM than that in OXT, shown in
Fig. 3. In the volume-hiding scheme dprfMM, for each single key query, it returns
2ℓ search results. Thus it needs 2ℓ blinded values y to obtain xtags by exponential
operations in OXTMM while ℓ blinded values y in OXT. And it can be seen that
the query time overhead in OXTMM is much more than that in OXT, shown in
Fig. 4.
<figure><img src="image_5.png" /><figcaption>Fig. 3. Query size with volume length</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 4. Query time with volume length</figcaption></figure>

To evaluate the impact of the number of search keys, we choose the first search key as the key with the maximum volume length and maintain the intersection results. Due to the increase of the number of search keys, it also leads to the increase of search token while not affects the search results in both schemes. However, except for search results, it also returns the bloom filter which is filled with hash values associated with *xtag* in OXTMM. And *xtags* are generated by the search token *xtoken* with the blinded values *y*. Thus, the bloom filter is also influenced by the number of search keys. As shown in Fig. 5, the number of search keys is much more influential in OXTMM than that in OXT. As the increase of search token, it needs much more time to calculate more *xtag* by exponential operations in both schemes. Since OXTMM is based on dprfMM, it needs 2*ℓ* blinded values *y* to obtain 2*ℓ* *xtags* while *ℓ* *xtags* in OXT. Except for the time overhead of exponential operations, it also needs time to obtain 4*ℓ*(*s* − 1) hash values and insert them into the bloom filter, which does not exist in OXT. Therefore, it takes more time to perform a conjunctive query in OXTMM than that in OXT, shown in Fig. 6.

<figure><img src="image_7.png" /><figcaption>Fig. 5. Query size with the number of keys</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 6. Query time with the number of keys</figcaption></figure>
# 5 Conclusions

In this paper, we propose an efficient volume-hiding scheme with support for conjunctive queries, dubbed OXTMM. We start from OXT [6] and suppress leakages which may lead to volume attacks. We first replace TSet with dprfMM [26] and then return $2\ell$ search results with a bloom filter which contains the corresponding intersection values. Our proposed scheme OXTMM is the first to achieve volume-hiding supporting conjunctive queries at the expense of some reasonable overhead. However, OXTMM is just suitable for static database, so how to design dynamic volume-hiding EMM supporting conjunctive queries remains a challenging problem.

**Acknowledgements.** This work is supported by the National Nature Science Foundation of China (No. 62072357), the Key Research and Development Program of Shaanxi (No. 2022KWZ-01) and the Fundamental Research Funds for the Central Universities (No. JB211503).

# References

1. Blackstone, L., Kamara, S., Moataz, T.: Revisiting leakage abuse attacks. In: NDSS 2020, San Diego, California, USA, 23–26 February 2020, p. 1175. The Internet Society (2020). https://www.ndss-symposium.org/ndss-paper/revisiting-leakage-abuse-attacks/

2. Bost, R.: $\Sigma\alpha\rho\alpha\Sigma$: Forward secure searchable encryption. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) CCS 2016, Vienna, Austria, 24–28 October 2016, pp. 1143–1154. ACM (2016). https://doi.org/10.1145/2976749.2978303

3. Bost, R., Minaud, B., Ohrimenko, O.: Forward and backward private searchable encryption from constrained cryptographic primitives. In: CCS 2017, Dallas, TX, USA, 30 October - 03 November 2017, pp. 1465–1482. ACM (2017). https://doi.org/10.1145/3133956.3133980

4. Cash, D., Grubbs, P., Perry, J., Ristenpart, T.: Leakage-abuse attacks against searchable encryption. In: CCS 2015, Denver, CO, USA, 12–16 October 2015. pp. 668–679. ACM (2015). https://doi.org/10.1145/2810103.2813700

5. Cash, D., Jaeger, J., Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M., Steiner, M.: Dynamic searchable encryption in very-large databases: Data structures and implementation. In: NDSS 2014, San Diego, California, USA, 23–26 February 2014. The Internet Society (2014). https://www.ndss-symposium.org/ndss2014/dynamic-searchable-encryption-very-large-databases-data-structures-and-implementation

6. Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Rosu, M.-C., Steiner, M.: Highly-scalable searchable symmetric encryption with support for boolean queries. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 353–373. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_20

7. Chase, M., Kamara, S.: Structured encryption and controlled disclosure. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 577–594. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_33
8. Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: CCS 2006, Alexandria, VA, USA, 30 October - 3 November 2006, pp. 79–88. ACM (2006). https://doi.org/10.1145/1180405.1180417

9. Demertzis, I., Papadopoulos, D., Papamanthou, C., Shintre, S.: SEAL: attack mitigation for encrypted databases via adjustable leakage. In: USENIX Security 2020, 12–14 August 2020, pp. 2433–2450. USENIX Association (2020). https://www.usenix.org/conference/usenixsecurity20/presentation/demertzis

10. Golle, P., Staddon, J., Waters, B.: Secure conjunctive keyword search over encrypted data. In: Jakobsson, M., Yung, M., Zhou, J. (eds.) ACNS 2004. LNCS, vol. 3089, pp. 31–45. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24852-1_3

11. Grubbs, P., Lacharité, M., Minaud, B., Paterson, K.G.: Pump up the volume: practical database reconstruction from volume leakage on range queries. In: CCS 2018, Toronto, ON, Canada, 15–19 October 2018, pp. 315–331. ACM (2018). https://doi.org/10.1145/3243734.3243864

12. Gui, Z., Johnson, O., Warinschi, B.: Encrypted databases: new volume attacks against range queries. In: CCS 2019, London, UK, 11–15 November 2019, pp. 361–378. ACM (2019). https://doi.org/10.1145/3319535.3363210

13. Gui, Z., Paterson, K.G., Patranabis, S., Warinschi, B.: Swisse: system-wide security for searchable symmetric encryption. IACR Cryptol. ePrint Arch., p. 1328 (2020). https://eprint.iacr.org/2020/1328

14. Islam, M.S., Kuzu, M., Kantarcioglu, M.: Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In: NDSS 2012, San Diego, California, USA, 5–8 February 2012. The Internet Society (2012). https://www.ndss-symposium.org/ndss2012

15. Kamara, S., Moataz, T.: SQL on structurally-encrypted databases. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11272, pp. 149–180. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03326-2_6

16. Kamara, S., Moataz, T.: Computationally volume-hiding structured encryption. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 183–213. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_7

17. Kamara, S., Moataz, T., Ohrimenko, O.: Structured encryption and leakage suppression. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 339–370. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_12

18. Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: CCS 2012, Raleigh, NC, USA, 16–18 October 2012, pp. 965–976. ACM (2012). https://doi.org/10.1145/2382196.2382298

19. Kellaris, G., Kollios, G., Nissim, K., O'Neill, A.: Generic attacks on secure outsourced databases. In: CCS 2016, Vienna, Austria, 24–28 October 2016, pp. 1329–1340. ACM (2016). https://doi.org/10.1145/2976749.2978386

20. Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: CCS 2013, Berlin, Germany, 4–8 November 2013, pp. 669–684. ACM (2013). https://doi.org/10.1145/2508859.2516668

21. Kirsch, A., Mitzenmacher, M., Wieder, U.: More robust hashing: Cuckoo hashing with a stash. SIAM J. Comput. 39(4), 1543–1561 (2009). https://doi.org/10.1137/080728743

22. Lai, S., et al.: Result pattern hiding searchable encryption for conjunctive queries. In: CCS 2018, Toronto, ON, Canada, 15–19 October 2018, pp. 745–762. ACM (2018). https://doi.org/10.1145/3243734.3243753
23. Meng, X., Kamara, S., Nissim, K., Kollios, G.: GRECS: graph encryption for approximate shortest distance queries. In: Ray, I., Li, N., Kruegel, C. (eds.) CCS 2015, Denver, CO, USA, 12–16 October 2015, pp. 504–517. ACM (2015). https://doi.org/10.1145/2810103.2813672

24. Miers, I., Mohassel, P.: IO-DSSE: scaling dynamic searchable encryption to millions of indexes by improving locality. In: NDSS 2017, San Diego, California, USA, 26 February - 1 March 2017. The Internet Society (2017). https://www.ndss-symposium.org/ndss2017/ndss-2017-programme/io-dsse-scaling-dynamic-searchable-encryption-millions-indexes-improving-locality/

25. Naveed, M., Kamara, S., Wright, C.V.: Inference attacks on property-preserving encrypted databases. In: CCS 2015, Denver, CO, USA, 12–16 October 2015, pp. 644–655. ACM (2015). https://doi.org/10.1145/2810103.2813651

26. Patel, S., Persiano, G., Yeo, K., Yung, M.: Mitigating leakage in secure cloud-hosted data structures: volume-hiding for multi-maps via hashing. In: CCS 2019, London, UK, 11–15 November 2019, pp. 79–93. ACM (2019). https://doi.org/10.1145/3319535.3354213

27. Poddar, R., Wang, S., Lu, J., Popa, R.A.: Practical volume-based attacks on encrypted databases. In: EuroS&P 2020, Genoa, Italy, 7–11 September 2020, pp. 354–369. IEEE (2020). https://doi.org/10.1109/EuroSP48549.2020.00030

28. Ren, K., et al.: Hybridx: new hybrid index for volume-hiding range queries in data outsourcing services. In: ICDCS 2020, Singapore, 29 November - 1 December 2020, pp. 23–33. IEEE (2020). https://doi.org/10.1109/ICDCS47774.2020.00014

29. Song, D.X., Wagner, D.A., Perrig, A.: Practical techniques for searches on encrypted data. In: SP 2000, Berkeley, California, USA, 14–17 May 2000, pp. 44–55. IEEE Computer Society (2000). https://doi.org/10.1109/SECPRI.2000.848445

30. Sun, S., et al.: Practical backward-secure searchable encryption from symmetric puncturable encryption. In: CCS 2018, Toronto, ON, Canada, 15–19 October 2018, pp. 763–780. ACM (2018). https://doi.org/10.1145/3243734.3243782

31. Wang, J., Chow, S.S.M.: Simple storage-saving structure for volume-hiding encrypted multi-maps. In: Barker, K., Ghazinour, K. (eds.) DBSec 2021. LNCS, vol. 12840, pp. 63–83. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81242-3_4

32. Wang, J., Chen, X., Sun, S.-F., Liu, J.K., Au, M.H., Zhan, Z.-H.: Towards efficient verifiable conjunctive keyword search for large encrypted database. In: Lopez, J., Zhou, J., Soriano, M. (eds.) ESORICS 2018. LNCS, vol. 11099, pp. 83–100. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98989-1_5