2020-1_HybrIDX New Hybrid Index for Volume-hiding Range Queries in Data Outsourcing Services _Kui Ren.pdf

Solo

139

11页

4次

2022-01-27

免费下载

HybrIDX: New Hybrid Index for Volume-hiding

Range Queries in Data Outsourcing Services

Kui Ren

‡

,YuGuo

†

, 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 assisting

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 volume 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 results outside the enclave in an encrypted multi-

maps manner. Apart from this novel hybrid index design, we

further customize a bulk refresh mechanism to enable access-

pattern obfuscation. 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 server-side decryption. It is

recognized as a fundamental component of building privacy-

preserving applications. Early studies on secure index con-

struction 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 at-

tracted a lot of attention from both academia and industry [8]–

[12]. A typical example in the encrypted database commu-

nity [13]–[18] is ﬁnding all matched records 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 [19]–[28], which allow order

comparisons to be performed directly on ciphertexts. In prac-

tice, however, these schemes are developed as cryptographic

primitives and can hardly accommodate system-wise security

requirements [29]–[36]. Speciﬁcally, different queries reveal

the associations between the query tokens and the number of

return results (i.e., volume-pattern). An attacker can determine

the indexed value relations by observing the distribution of

the result size. Recent leakage-abuse attacks [29]–[31] have

shown how the volume-pattern leakage can be exploited to

learn sensitive information about the queries and outsourced

data. To mitigate this leakage concern, a simple approach is to

apply naive padding. However, this approach would introduce

expensive storage overhead because the result set of each index

entry 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, the results (i.e., access-pattern)

of different range queries have multiple unique intersections,

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 intersections of different range query results, an attacker

can still learn the data distribution even if the volume-pattern

has been well-protected. 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 applied cryptography 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 with large result size into multiple independent sub-

2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS)

DOI 10.1109/ICDCS47774.2020.00014

Authorized licensed use limited to: Ant Financial. Downloaded on January 13,2022 at 03:26:33 UTC from IEEE Xplore. Restrictions apply.

Untrusted Host

Enc. MM Indexes

Data Applications

Enclave Indexes

HybrIDX

Fig. 1: Overview of main HybrIDX components.

queries with smaller but equal ﬁxed volume. While seemingly

inconvenient, this way of query processing is actually con-

sistent with the rationale of many practical applications in

information retrieval, which would on demand display a partial

result set to the client upon request [40].

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

queries, we explore the existing volume-hiding encryption

scheme from the multi-map data structure [37] to convert

result sets of different values into multiple block ciphertexts

with ﬁxed length (Fig.1: Enc.MM). As directly outsourcing

the resulting multi-map indexes cannot support secure range

queries, we devise a range-based index (Fig.1: Enclave) inside

the enclave platform to indicate the corresponding multi-map

indexes and 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 access-pattern leakage among different

range queries. Particularly, we propose a secure bulk refresh

mechanism that caches retrieved results inside the enclave and

refresh them periodically. With the assistance of an enclave-

based refresh mechanism, not only can we efﬁciently obfuscate

the access-pattern leakage among different queries, but also we

can avoid high communicational cost between the client and

servers. 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 data records of indexed values in the form

of multi-maps and conducts efﬁcient range comparisons

inside the enclave.

• We carefully tailor a secure batch query protocol and

a bulk refresh mechanism enabling volume-hiding result

retrieval and access-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 [24] O(log m) BS  

Ideal-OPE [25]

O(log m) AS  

POPE [23]

O(log m) BS  

ORE

CLWW [21] O(m) AS 

Lewi-Wu [19]

O(m) AS 

PHORE [20]

O(m) AS 

Enclave

HardIDX [42] O(log m)   

Opaque [43]

O(log m) N/S  

ZeroTrace [44]

O(log n) N/S  

Oblix [41]

O(log

n) N/S 

∗

EnclaveDB [45] O(log m)   

HybrIDX O(log m)   

1 

∗

: 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 [19]–

[28]. 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) [24], 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 [33]. In [25],

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 [27]. ORE ciphertext has no particular

order, while order relations are revealed during dedicated com-

parison protocols [19]–[21]. However, ORE schemes would

Authorized licensed use limited to: Ant Financial. Downloaded on January 13,2022 at 03:26:33 UTC from IEEE Xplore. Restrictions apply.

of 11

免费下载

关注

评论