【免费】ACM论文：数据持有性验证1资源-CSDN文库

需积分: 0 79 浏览量 2022-08-03 13:37:09 上传评论收藏 722KB PDF 举报

在当前数字化时代，数据安全与隐私保护已经成为至关重要的议题，特别是在使用第三方存储服务时。"ACM论文：数据持有性验证1"探讨了一个名为“可证明数据拥有性”（Provable Data Possession, PDP）的模型，该模型旨在解决在不信任的服务器上存储数据时，如何验证服务器是否真实地保存了原始数据，而无需完整地检索这些数据。 PDP模型的核心在于通过随机选取数据块来生成概率性的持有性证明，这种方法大大降低了输入/输出(I/O)的成本。客户端只需要维护少量的元数据，就能验证这些证明。挑战/响应协议则只传输固定量的小数据，以最小化网络通信，使得PDP模型适用于处理大型分布式存储系统中的海量数据。论文提出了两个安全且高效的PDP方案，它们比先前的解决方案更为优越，即使与那些提供较弱保证的方案相比也是如此。特别地，这些方案在服务器端的开销是低的（甚至是常数级），而不是线性依赖于数据的大小。实验证明了PDP在实际应用中的可行性，并揭示了PDP的性能主要受到磁盘I/O的限制，而非加密计算。传统的数据验证方法往往在访问数据时检查其真实性，但这对于长期存档系统并不足够。存档存储服务器通常需要保证即使数据很少被访问，也能确保数据的完整性。这种持有性验证可以防止服务器对数据的篡改或删除行为，因为一旦数据丢失或损坏，再进行恢复可能为时已晚。 PDP的实现方式通常包括以下几个步骤： 1. 数据上传：客户端将数据分块并加密，同时生成数据的哈希值。 2. 存储证明：服务器接收数据后，根据PDP模型随机选择一部分数据块的哈希值并保存。 3. 验证请求：客户端发送随机挑战（即部分数据块的哈希值列表）给服务器。 4. 证明响应：服务器返回挑战所对应的加密数据块的解密后的哈希值。 5. 验证过程：客户端对比收到的哈希值与原始的哈希值，确认数据的完整性。此论文的工作对于云存储、分布式存储以及任何依赖于远程服务器的数据安全应用都具有重大意义。通过PDP，用户可以在不完全依赖服务器诚实性的情况下，对数据的完整性进行持续监控，从而增强数据的可靠性。这不仅提升了数据安全性，也为大数据时代的合规性和审计提供了有力工具。

资源详情

资源评论

资源推荐

Provable Data Possess ion at Untrus ted Stores

∗

Giuseppe Ateniese

†

Randal Burns

†

Reza Curtmola

†

Joseph Herring

†

Lea Kissner

‡

Zachary Pet erson

†

Dawn Song

Abstract

We introduce a model for provable data possession (PDP) that allows a client that has stored

data at an unt rusted server to verify that the server possesses the original data without retrieving

it. The model generates probabilistic proofs of possession by sampling random sets of blocks

from the server, which drastically reduces I/O costs. The client maintains a constant amount

of metadata to verify the pro of. The challenge/response protocol transmits a small, constant

amount of data, which minimizes network communication. Thus, the PDP model for remote

data checking supports large data sets in widely-distributed stora ge systems.

We present two provably-secure PDP schemes that are more eﬃcient than previous solutions,

even when compared with schemes that achieve weaker gua rantees. In particular, the overhead

at the server is low (or even constant), as opposed to linear inthesizeofthedata. Experiments

using our implementation verify the practicality of PDP and reveal that the p erformance of

PDP is b ounded by disk I/O and not by cryptographic computation.

1Introduction

Verifying the authenticity of data has emerged as a critical issue in storing data on untrusted

servers. It arises in peer-to-peer storage systems [29, 35],networkﬁlesystems[30,26],long-term

archives [32], web-service object stores [48], and databasesystems[31]. Suchsystemsprevent

storage servers from misrepresenting or modifying data by providing authenticity checks when

accessing data.

However, archival storage requires guarantees about the authenticity of data on storage, namely

that storage servers possess data. It is insuﬃcient to detectthatdatahavebeenmodiﬁedordeleted

when accessing the data, because it may be too late to recover lost or damaged data. Archival

storage servers retain tremendous amounts of data, little ofwhichareaccessed. Theyalsohold

data for long periods of time during which there may be exposure to data loss from administration

errors as the ph ysical implementation of storage evolves, e.g.,backupandrestore,datamigration

to new systems, and changing memberships in peer-to-peer systems.

Archival network storage presents unique performance demands. Given that ﬁle data are large

and are stored at remote sites, accessing an entire ﬁle is expensive in I/O costs to the storage

server and in transmitting the ﬁle across a network. Reading an entire arc hive, even periodically,

∗

This is the full version of the paper that appears in Proceedings of the 14th ACM Conference on Computer and

Communications Security(CCS 2007) [3].

†

Department of Computer Science, Johns Hopkins University – {ateniese, randal, crix}@cs.jhu.edu,

jrh@jhu.edu, zachary@cs.jhu.edu

‡

Google, Inc. – leak@cs.cmu.edu

University of California Berkeley/Carnegie Mellon University – dawnsong@cs.berkeley.edu

greatly limits the scalability of network stores. (The growth in storage capacity has far outstripped

the growth in storage access times and bandwidth [44]). Furthermore, I/O incurred to establish

data possession interferes with on-demand bandwidth to store and retrieve data. We conclude that

clients need to be able to verify that a server has retained ﬁledatawithout retrieving the data from

the server and without having the server access the entire ﬁle.

Previous solutions do not meet these requirements for proving data possession. Some schemes

[20] provide a weaker guarantee by enforcing storage complexity:Theserverhastostoreanamount

of data at least as large as the client’s data, but not necessarily the same exact data. Moreover, all

previous techniques require the server to access the entire ﬁle, which is not feasible when dealing

with large amounts of data.

We deﬁne a model for provable data p ossession (PDP) that provides probabilistic proof that a

third party stores a ﬁle. The model is unique in that it allows the server to access small portions of

the ﬁle in generating the proof; all other techniques m ust access the entire ﬁle. Within this model,

we give the ﬁrst provably-secure scheme for remote data checking. The client stores a small O(1)

amount of metadata to verify the server’s proof. Also, the scheme uses O(1) bandwidth

.The

challenge and the response are each slightly more than 1 Kilobit. We also present a more eﬃcient

version of this scheme that proves data possession using a single mo dular exponentiation at the

server, even though it provides a weaker guarantee.

Both schemes use homomorphic veriﬁable tags.Becauseofthehomomorphicproperty,tags

computed for multiple ﬁle blocks can be combined into a singlevalue. Theclientpre-computes

tags for each block of a ﬁle and then stores the ﬁle and its tags with a server. At a later time,

the client can verify that the server possesses the ﬁle by generating a random challenge against a

randomly selected set of ﬁle blocks. Using the queried blocksandtheircorrespondingtags,the

server generates a proof of possession. The client is thus convinced of data possession, without

actually having to retrieve ﬁle blocks.

The eﬃcient PDP scheme is the fu ndamental construct un derlying an archival introspection

system that we are d eveloping for the long-term preservationofAstronomydata. Wearetaking

possession of multi-terabyte Astronomy databases at a University library in order to preserv e the

information long after the research projects and instruments used to collect the data are gone. The

database will b e replicated at multiple sites. Sites includeresource-sharingpartnersthatexchange

storage capacity to ach ieve reliability and scale. As such, the system is subject to freeloading in

which partners attempt to use storage resources and contribute none of their own [20]. The location

and physical implementation of these replicas are managed independently by each partner and will

evolve over time. Partners may even outsource storage to third-party storage server providers [23].

Eﬃcient PDP schemes will ensure that the computational requirements of remote data checking

do not unduly burden the remote storage sites.

We implemented our more eﬃcient scheme (E-PDP)andtwootherremotedatacheckingproto-

cols and evaluated their performance. Experiments show thatprobabilisticpossessionguarantees

make it pr actical to verify possession of large data sets. With sampling, E-PDP veriﬁes a 64MB

ﬁle in about 0.4 seconds as compared to 1.8 seconds without sampling. Further, I/O bounds the

performance of E-PDP;itgeneratesproofsasquicklyasthediskproducesdata. Finally, E-PDP is

185 times faster than the previous secure protocol on 768 KB ﬁles.

Storage overhead and network overhead are constant in the size of the ﬁle, but depend on the chosen security

parameter.

client

client generates

metadata (

) and

modifed ﬁle (

)

client store

server store

input ﬁle

no server

processing

(a) Pre-process and store

client

(1) client generates a

random challenge

client store

server store

(3) client veriﬁes

server's proof

server

(2) server computes

proof of possession

0/1

(b) Verify server possession

Figure 1: Protocol for provable data possession.

Contributions. In this paper we:

formally deﬁne protocols for pr ovable data possession (PDP)thatprovideprobabilisticproof

that a third party stores a ﬁle.

in t roduce the ﬁrst provably-secure and practical PDP schemes that guaran tee data possession.

implement one of our PDP schemes and show experimentally thatprobabilisticpossession

guarantees mak e it practical to v erify possession of large data sets.

Our PDP schemes provide data format independence,whichisarelevantfeatureinpractical

deployments (more details on this in the remarks of Section 4.3), and put no restriction on the

number of times the client can challenge the server to prove data possession. Also, a variant of our

main PDP scheme oﬀers public veriﬁability (described in Section 4.3).

Note. Apreliminaryversionofthispaperthatappearsintheproceedings of CCS 2007 [3] contained

an error in the security proof: We erroneously made an assumption that does not hold when the

parameter e is public

.Asaresult,wehavesimpliﬁedtheschemeande is now part of the secret

key . Keeping e secret aﬀects only the public veriﬁability feature, which is n o longer provided by

our main PDP scheme. This feature allows anyone, not just the data owner, to challenge the server

for data possession. However, we show how to achieve public veriﬁability by simply restricting the

size of ﬁle blocks (see the end of Section 4.3).

Paper Organization. The rest of the paper is organized as follows. In Section 2, we describe a

framework for provable data possession, emphasizing the features and parameters that are relevant

for PDP. Section 3 overviews r elated work. In Section 4, we introduce homomorphic veriﬁable tags,

followed by deﬁnitions for PDP schemes and then we give our constructions (S-PDP and E-PDP).

We supp ort our theoretical claims with exp eriments that showthepracticalityofourschemesin

Section 5 and conclude in Section 6.

2ProvableDataPossession(PDP)

We describe a framework for provable data p ossession. This provides background for related

work and for the speciﬁc description of our schemes. A PDP protocol (Fig. 1) checks that an

outsourced storage site retains a ﬁle, which consists of a collection of n blo cks. The client C (data

owner) pre-processes the ﬁle, generating a piece of metadatathatisstoredlocally,transmitstheﬁle

We assumed that gcd(e, |M

∗

− M|)=1withoverwhelmingprobability. However,thisturnedouttobefalse

when e is public.

[20] [20]-Wagner [17, 19] [41] [40] S-PDP E-PDP

(MHT-SC) (B-PDP)

Data possession No No Yes Yes Yes

∗

Yes Yes

Supports sampling No No No No No

†

Yes Yes

Type of guarantee deterministic

probabilistic /

probabilistic

deterministic

Server block access O(n) O(log n) O(n) O(n) O(n) O(1) O(1)

Server computation O(n) O(1) O(n) O(1) O(n) O(1) O(1)

Client computation O(1) O(1) O(1) O(1) O(1) O(1) O(1)

Communication O(1) O(log n) O(1) O(1) O(n) O(1) O(1)

Client stora ge O(1) O(1) O(1) O(n) O (1) O(1) O(1)

Table 1: Features and parameters (per challenge) of various PDP schemes when the server misbehaves by

deleting a fraction of an n-block ﬁle (e.g.,1%ofn). The server and client computation is expressed as the

total cost of performing modular exponentiation operations. For simplicity, the security parameter is not

included as a factor for the relevant costs.

∗

No security proof is given for this scheme, so assurance of data possession is not conﬁrmed.

†

The client can ask proof for select symbols inside a block, butcannotsampleacrossblocks.

to the server S,andmaydeleteitslocalcopy.Theserverstorestheﬁleandresponds to challenges

issued by the client. Storage at the server is in Ω(n)andstorageattheclientisinO(1),conforming

to our notion of an outsourced storage relationship.

As part of pre-processing, the client ma y alter the ﬁle to be stored at the server. The client

may expand the ﬁle or include additional metadata to be storedattheserver. Beforedeletingits

local copy of the ﬁle, the client may execute a data possessionchallengetomakesuretheserver

has successfully stored the ﬁle. Clients may encrypt a ﬁle prior to out-sourcing the storage. For

our purposes, encryption is an orthogonal issue; the “ﬁle” may consist of encrypted data and our

metadata does not include encryption keys.

At a later time, the client issues a challenge to the server to establish that the server has retained

the ﬁle. The client requests that the server compute a function of the stored ﬁle, which it sends

back to the client. Using its local metadata, the client veriﬁes the response.

Threat mo del. The server S must answer challenges from the client C;failuretodosorepresents

adataloss.However,theserverisnottrusted: Eventhoughthe ﬁle is totally or partially missing,

the serv er may try to convince the client that it possesses theﬁle. Theserver’smotivationfor

misbehavior can be diverse and includes reclaiming storage by discarding data that has not been

or is rarely accessed (for monetary reasons), or hiding a datalossincident(duetomanagement

errors, hardware failure, compromise by outside or inside attacks etc). The goal of a PDP scheme

that achieves probabilistic proof of data possession is to detect server misbehavior when the server

has deleted a fraction of the ﬁle.

Requirements and Parameters. The important performance parameters of a PDP scheme

include:

Computation complexity: The computational cost to pre-process a ﬁle (at C), to generate a

proof of p ossession (at S)andtoverifysuchaproof(atC);

Block access complexity: The number of ﬁle blocks accessed to generate a proof of possession

剩余24页未读，继续阅读

评论收藏

内容反馈

xhmoon

粉丝: 19
资源: 328

ACM论文：数据持有性验证1

评论0

最新资源

ACM论文：数据持有性验证1

评论0

一篇ACM上的文章

ACM论文：数据可恢复性证明1

一种分布式存储系统环境下的数据持有性验证方法.pdf

ACM 期刊：Candidate Multilinear Maps

ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛

ACM论文（信息学奥赛中国国家队）

云存储中的数据持有性证明研究综述

一个改进的混合云环境下协同的可证明数据持有方案 (2013年)

ACM系列论文模板-ACMART

ACM 期刊：A Framework for Scientific Discovery through Video Games

ACM SIGCOMM 2014论文集

ACM最佳论文2006-2009.rar

上海交大ACM算法模板：数据结构与算法实现

ACM经典试题：最小差值对Minimum Difference Pair+编程知识+技术开发

acm国家集训队1999年论文合集

ACM数学论文

acm国家集训队论文

ACM:NOI:CSP比赛经验.txt

ACM国家集训队论文集

ACM国家队论文

acm 经典数据结构

2013USENIX和ACM等精品论文20篇

ACM:NOI:CSP比赛经验分享&代码程序.zip

最新资源