双云盲存储：实现高效带宽利用

需积分: 9 183 浏览量更新于2024-09-11 收藏 1.61MB PDF 举报

"这篇文档是关于Multi-Cloud Oblivious Storage的研究，由Emil Stefanov（UC Berkeley）和Elaine Shi（University of Maryland）共同撰写。他们提出了一种两云无感知存储（2-Cloud Oblivious RAM, ORAM）系统，该系统能够在客户端与云端之间实现2.6倍的带宽成本降低。通过将ORAM分散到两个或更多不合作的云端，可以将带宽消耗转移到云端之间的通信，从而显著降低客户端到云端的带宽需求，这对于带宽有限的客户端如家庭或移动互联网连接来说具有实际意义。此外，作者还提供了全面实现的2-Cloud ORAM系统的实证结果，报告了在Amazon EC2和Microsoft Azure上的真实世界部署情况。研究领域包括管理计算和信息系统中的安全与保护，主要涉及算法和安全关键词。" 在当前的云计算环境中，存储外包已经成为一个日益增长的行业，它免除了用户维护内部基础设施的负担。然而，这种外包带来了数据隐私和安全的问题。Oblivious RAM（ORAM）是一种技术，旨在确保即使数据存储在外部（例如云服务提供商处），也能保证访问模式的隐私，防止服务提供商获取任何关于数据访问模式的信息。传统的ORAM方案通常对客户端的带宽要求较高，这可能成为其广泛应用的瓶颈。 Multi-Cloud Oblivious Storage是为解决这一问题提出的解决方案。通过在多个非合作的云服务提供商之间分散ORAM，系统能够显著降低客户端的带宽消耗。文中提到的2-Cloud ORAM系统在两个云之间分配数据，使得大部分高带宽的通信发生在云服务器之间，而不是直接与客户端交互。这样的设计不仅降低了客户端的网络负载，还能充分利用云服务商之间的丰富带宽资源，使得ORAM对于那些带宽受限的环境（如家庭或移动设备）变得更加实用。为了验证这一概念的可行性，作者提供了完整的2-Cloud ORAM系统实现，并在Amazon EC2和Microsoft Azure两大主流云平台上进行了实际部署和性能测试。这些实验结果提供了关于系统性能、效率和可靠性的实际证据，有助于进一步推动ORAM技术在多云环境中的应用。 Multi-Cloud Oblivious Storage是针对云存储隐私保护的一项重要创新，通过优化带宽利用，使ORAM技术更适合带宽有限的环境，同时增强了数据的安全性和用户的隐私。这项研究对于云服务提供商和依赖云存储的用户来说具有重要的理论和实践价值，促进了云存储服务在保护用户隐私方面的进步。

The partitioning framework [31]

// Divide the ORAM into

√

N partitions of size O(

√

N).

Read(u):

• Look up position map and determine that u is assigned to

partition p.

• If u is not found in eviction caches:

– ReadPartition(p, u)

Else if u is found in local eviction caches:

– ReadPartition(p, ⊥) //read dummy

• Pick a random partition p

, add the block identiﬁed by u to

the eviction caches, and logically assign u to partition p

• Call Evict ν times where ν > 1 is the eviction rate.

Write(u, B):

Same as Read(u), except that the block written to the eviction

cache is replaced with the new block.

Evict:

• Pick a random partition p.

• If a block B exists in the eviction cache assigned to partition

p, call WritePartition(p, B).

• Else, call WritePartition(p, ⊥), where ⊥ represents a

dummy block.

Figure 1: The SSS partitioning framework [31]. Our

construction uses this framework to express ORAM Read

and Write operations in terms of the ReadPartition and

WritePartition operations of our multi-clouds construc-

tion.

A background eviction process evicts blocks from the evic-

tion cache back to the server in an oblivious manner. With

every data access, randomly select 2 partitions for eviction.

If a block exists in the eviction cache assigned to the chosen

partition, evict a real block; otherwise, evict a dummy block

to prevent leakage.

2.2 Partition ORAM

Each partition is a fully functional ORAM in itself. Our

partition ORAM construction is based on the partition ORAM

of the SSS construction [31], which is a variant of the origi-

nal hierarchical construction [11], but with various optimiza-

tions geared towards maximal practical performance.

Each partition consists of L :=

log N + 1 levels, where

level i ∈ {0, 1, . . . , L − 1} can store at more 2

real blocks,

and 2

or more dummy blocks. We refer to the largest level,

i.e., level L − 1, as the top level.

We extend the client’s position map to store the position

tuple (p, `, oﬀset) for each block, where p is the partition, `

is the level, and oﬀset denotes the oﬀset within the level.

Read. To read a block, the client ﬁrst reads its position

map and ﬁnd out the position (p

∗

, `

∗

, oﬀset

∗

) of the block.

Then, the client reads one block from each level of partition

p. For level ` = `

∗

, the client reads the block at oﬀset

∗

For other levels, the client reads a random unread dummy

block. If the block is found in the client’s eviction cache,

one dummy block is read from each level.

Write. Writing back a block to a partition causes a reshuf-

ﬂing operation. Speciﬁcally, let 0, 1, . . . , ` denote consecu-

tively ﬁlled levels such that level `+1 is empty. Writing back

a block B causes levels 0, 1, . . . , ` to be reshuﬄed into level

` + 1. In the single-cloud SSS construction, the reshuﬄing

is done by having the client download all blocks, permute

them, re-encrypt them, and then write them back to the

server.

3. BASIC TWO-CLOUD CONSTRUCTION

IN THE SEMI-HONEST MODEL

We ﬁrst explain a scheme that is secure when both clouds

are semi-honest. Then, in Section 4, we explain how to

use our commutative checksum-encryption construction to

achieve security against one malicious cloud (without know-

ing which one might be malicious).

3.1 Intuition

Reducing ORAM shuﬄing overhead. In existing single-

cloud ORAM schemes [30–32, 35], a major source of the

client bandwidth overhead stems from shuﬄing. Periodi-

cally, the client has to download a subset of data blocks

from the cloud, permute them, re-encrypt them locally, and

write them back.

In our multi-cloud ORAM construction, we delegate the

shuﬄing work to the two clouds to minimize client-cloud

bandwidth usage. For example, cloud S

shuﬄes a subset

of blocks, adds a layer of encryption (i.e., an “onion layer”),

and sends them to S

. Later when the client needs to read

from that subset of blocks, it fetches them from S

. In this

way, while cloud S

knows the permutation used in the shuf-

ﬂing, it does not see which blocks the client requests from

later. In contrast, while S

sees which shuﬄed blocks the

client requests later, it has no knowledge of the permutation

applied by S

. As a result, neither cloud learns any infor-

mation about the client’s logical (i.e., “unshuﬄed”) access

pattern. The details of inter-cloud shuﬄing are described in

Section 3.5.2.

Note that it is necessary for security to add onion encryp-

tion layers after every shuﬄe: if a block B gets shuﬄed from

to S

and then back to S

, we do not want S

to be able

to link the two occurrences of the same block B based on

the block’s data. In the full online version [29], we intro-

duce a background onion removal process to avoid adding

an unbounded number of onion layers to a block.

Reducing ORAM read overhead. Existing single-cloud

ORAM schemes can also incur signiﬁcant bandwidth over-

head for reading a data block in-between shuﬄings [30–32,

35]. For example, the client may need to read one or more

blocks from O(log N ) levels in a hierarchy.

In our multi-cloud construction, we are able to signiﬁ-

cantly reduce the bandwidth overhead for reading a block

by doing the following. The client requests a set of (already

shuﬄed) blocks from S

. S

then randomly permutes them

with a permutation known only by S

and the client, and

then S

sends them to S

. Finally, the client requests and

downloads only a single block from S

by providing S

with

the permuted index of the requested block. The details of

reading a block from multiple clouds are described in Sec-

tion 3.5.1.

3.2 Data Layout on Clouds

Our scheme leverages the partitioning framework as de-

scribed in Section 2.1. We divide our ORAM into O(

√

partitions each of capacity O(

√

N). Each partition is di-

vided into L = O(log N ) levels, and each level resides on

one of the two clouds. Which level resides on which cloud

249

剩余11页未读，继续阅读

sinat_25132317

粉丝: 0
资源: 2

双云盲存储：实现高效带宽利用

不经意传输 OT Efficient 1-Out-of-n Oblivious Transfer Schemes论文实现

Practical quantum all-or-nothing oblivious transfer protocol

Privacy Enforced Multi-Authority based Access ControlEnforcement Mechanism in DaaS

2取1不经意传输协议的数学原理试试呢么

oblivious transfer

neural oblivious decision ensembles for deep learning on tabular data

is not member of

PSI的安全性被证明了吗

boost的select

catboost预测

最新资源

不经意传输 OT　Efficient 1-Out-of-n Oblivious Transfer Schemes论文实现