ICDCS 2020-HybrIDX- New Hybrid Index for Volume-hiding Range Queries in Data Outsourcing Services.pdf

波风水门

126

11页

5次

2023-05-31

免费下载

HybrIDX: New Hybrid Index for Volume-hiding

Range Queries in Data Outsourcing Services

Kui Ren

‡

, Yu Guo

†

, Jiaqi Li

‡

, Xiaohua Jia

†

, Cong Wang

†

, Yajin Zhou

‡

, Sheng Wang

, Ning Cao

, Feifei Li

‡

Zhejiang University,

†

City University of Hong Kong,

Alibaba Group,

Hangzhou Mishu Technology.

{kuiren, lijiaqi93, yajin zhou}@zju.edu.cn, y.guo@my.cityu.edu.hk, {congwang, csjia}@cityu.edu.hk,

{sh.wang, lifeifei}@alibaba-inc.com, ncao@hzmstech.com

Abstract—An encrypted index is a data structure that assists

untrusted servers to provide various query functionalities in the

ciphertext domain. Although traditional index designs can pre-

vent servers from directly obtaining plaintexts, the conﬁdentiality

of outsourced data could still be compromised by observing

the volume of different queries. Recent volume attacks have

demonstrated the importance of sealing volume-pattern leakage.

To this end, several works are made to design secure indexes with

the volume-hiding property. However, prior designs only work

for encrypted keyword search. Due to the unpredictable range

query results, it is difﬁcult to protect the volume-pattern leakage

while achieving efﬁcient range queries.

In this paper, for the ﬁrst time, we deﬁne and solve the chal-

lenging problem of volume-hiding range queries over encrypted

data. Our proposed hybrid index framework, called HybrIDX,

allows an untrusted server to efﬁciently search encrypted data

based on order conditions without revealing the exact result

size. It resorts to the trusted hardware techniques to assist

range query processing by moving the comparison algorithm

to trusted SGX enclaves. To enable volume-hiding data retrieval,

we propose to host encrypted ﬁle blocks outside the enclave in an

encrypted volume-hiding structure. Apart from this novel hybrid

index framework, we further customize a result caching method

to obfuscate the results co-occurrence among different queries.

We formally analyze the security strengths and complete the

prototype implementation. Evaluation results demonstrate the

feasibility and practicability of our designs.

I. INTRODUCTION

An encrypted index offers a secure interface for data owners

to outsource private data to an untrusted server, while se-

lectively retrieving data without decryption. It is recognized

as a fundamental component of building privacy-preserving

applications. Early studies on secure index construction mainly

focus on the direction of keyword search [1]–[7]. Along

with the development of data outsourcing paradigm, enabling

efﬁcient range queries over secure indexes has attracted a lot of

attention from both academia and industry [8]–[11]. A typical

example in the encrypted database community [12]–[17] is

ﬁnding all matched ﬁles according to order conditions such as

indexed values or timestamps.

Over the past decade, the demand for designing range-based

indexes has been expected to be addressed by the innovation

of cryptographic techniques, e.g., Order-preserving/revealing

encryption (OPE/ORE) schemes [18]–[27], which allow or-

der comparisons to be performed directly on ciphertexts. In

practice, however, these schemes are developed as crypto-

graphic primitives and can hardly accommodate system-wise

security requirements [28]–[36]. Speciﬁcally, range queries

reveal the different number of return results (i.e., volume-

pattern) and the results co-occurrence pattern. Recent leakage-

abuse attacks [28]–[32] have shown how these leakages can

be exploited to learn sensitive information about the query

content and outsourced data. To mitigate this security concern,

a simple approach is to apply naive padding. However, this

approach would introduce expensive storage overhead because

the result set is padded to the maximum length.

In the literature, only a few recent works [37]–[39] have

started to study practical index designs with the protection

of volume-pattern. In [37], Kamara et al. proposed the ﬁrst

practical volume-hiding encryption scheme by using the multi-

map data structure [38]. The follow-up design [39] utilized

cuckoo hashing and differential privacy to further reduce the

volume and storage overhead. Unfortunately, neither of the

existing schemes can support volume-hiding range queries

because of two challenging issues. Firstly, unlike keyword

search functions, the result size of different range queries

cannot be pre-deﬁned. Clients without pre-knowledge of the

result size have to download all the data in order to hide the

volume-pattern leakage, which demands a large amount of

bandwidth overhead. Secondly, different range queries reveal

the results co-occurrence pattern, which can be exploited for

inferring the plaintext distribution. For example, the result

set associated with the endpoint values must appear in all

the other range query results. By observing the results co-

occurrence among different queries, an attacker can still learn

the result distribution even if the volume-pattern has been well-

protected [28]–[30]. Therefore, how to enable volume-hiding

range queries over encrypted indexes is still challenging and

remains to be fully explored.

In this paper, for the ﬁrst time, we solve the problem of

volume-hiding range queries in the data outsourcing paradigm.

Our proposed hybrid index framework, called HybrIDX, can

effectively address the aforementioned challenges while being

efﬁcient in supporting range queries. To achieve our design

goals on both security and usability, we propose to bring

together the advancement of both volume-hiding data structure

and trusted hardware to build the desired index construction.

To hide the result size of different range queries, we ﬁrst

propose to utilize the trusted enclave to securely convert any

range query into multiple independent sub-queries with equal

ﬁxed volume. While seemingly inconvenient, this way of query

Untrusted Host

Enc. MM Indexes

Enclave Indexes

Volume-hiding Storage

HybrIDX

Data Applications

Fig. 1: Overview of main HybrIDX components.

processing is actually consistent with the rationale of many

practical applications in information retrieval, which would

on-demand display a subset of query results per round to the

client upon request [40].

In order to concretely achieve the ﬁxed volume for sub-

queries, we explore the volume-hiding storage structure from

the bucketization-based padding method [37] that converts ﬁle

blocks of different values into multiple block ciphertexts with

a ﬁxed length. As directly outsourcing the resulting volume-

hiding ciphertexts cannot support range queries, we devise

a range-based index inside the trusted enclave to indicate

the corresponding encrypted ﬁle blocks, as shown in Fig.1.

Besides, we customize a batch query protocol for our purpose

to retrieve range query results in a volume-hiding manner.

Under this hybrid index framework, we then consider how

to further mitigate the co-occurrence pattern leakage among

different range queries. Particularly, we propose a secure

caching method that caches retrieved results inside the enclave

and refreshes them periodically. With the assistance of an

enclave-based caching method, not only can we efﬁciently

obfuscate the co-occurrence leakage among different queries,

but also we can avoid high communicational cost between

the client and servers for indexes refresh. We believe the

proposed hybrid index design provides useful guidelines and

new insights on designing secure indexes for modern data

outsourcing services. The main contributions of this paper can

be summarized as follows:

• We present HybrIDX, the ﬁrst hybrid index framework

that enabling volume-hiding range queries over encrypted

data. It stores encrypted ﬁle blocks of indexed values

in the form of volume-hiding structure and conducts

efﬁcient range comparisons inside the enclave.

• We carefully tailor a secure batch query protocol and a

result caching method for volume-pattern protection and

co-occurrence pattern obfuscation.

• We provide thorough analysis investigating security and

efﬁciency guarantees of the proposed designs. By char-

acterizing and analyzing the leakage proﬁles from both

the index construction and the query protocol, we prove

the security of our schemes.

• We implement the system prototype and conduct a com-

prehensive evaluation. The experiment results show that

Similar insight has also been utilized by prior art Oblix [41], but for ranked

keyword search that is different from our focus on range queries.

TABLE I: Security characterization of representative

schemes for secure range query operations

Primitives

Query

Efﬁciency

Leakage Protection

Order

Result

Pattern

Access

Pattern

Volume

Pattern

OPE

ROPF [23] O(log m) BS 7 7 7

Ideal-OPE [24] O(log m) AS 7 7 7

POPE [22] O(log m) BS 7 7 7

ORE

CLWW [20] O(m) AS 7 7 7

Lewi-Wu [18] O(m) AS 7 7 7

PHORE [19] O(m) AS 7 7 7

Enclave

HardIDX [42] O(log m) 3 3 7 7

Opaque [43] O(log m) N/S 3 3 7

ZeroTrace [44] O(log n) N/S 3 3 7

Oblix [41] O(log

n) N/S 3 3 3

∗

EnclaveDB [45] O(log m) 3 3 3 7

HybrIDX O(log m) 3 3 3 3

1 3

∗

: result may be lossy.

2 BS: before search ⊂ AS: after search.

3 n: number of total records; m: number of indexed values, n >> m.

4 N/S: the feature may be potentially supported, but not explicitly handled.

our range query protocol can fetch all matched results

within a short latency, and achieve better query efﬁciency

compared with existing cryptographic solutions.

The rest of this paper is organized as follows. Section II

introduces background knowledge and related work involved

in our designs. Section III presents our system architecture

and threat assumptions. Section IV introduces our system

design. Our security analysis is conducted in Section V, and

an extensive array of evaluation results is shown in Section VI.

Finally, we conclude the paper in Section VII.

II. RELATED WORK

A. Encrypted Range Queries

Searchable encryption (SE) scheme for secure range queries

has been an active research area in the past decade [18]–

[27]. To make a clear comparison, we have summarized the

representative solutions and compiled their security features in

Table I. The early studies, known as order-preserving encryp-

tion (OPE) [23], can preserve the original orders of plaintexts

by using a random order-preserving function (ROPF). Thus, an

untrusted server is able to make numeric comparisons between

ciphertexts as if it had operated on plaintexts. However,

orders are directly leaked from OPE ciphertexts, which make

OPE ciphertexts suffer from the sorted attacks [34]. In [24],

Popa et al. proposed an ideal OPE scheme (Ideal-OPE) by

encrypting values via standard encryption, but it requires

multiple interactions for client-side comparison. To mitigate

the order leakage, the notion of order-revealing encryption

(ORE) was proposed [26]. ORE ciphertext has no particular

order, while order relations are revealed during dedicated com-

parison protocols [18]–[20]. However, ORE schemes would

of 11

免费下载

关注

评论