Provable data possession at untrusted stores

By Giuseppe Ateniese, Randal C. Burns, Reza Curtmola, Joseph Herring, Lea Kissner, Zachary N. J. Peterson, Dawn Song. Conference on Computer and Communications Security, 2007

3,442 citations recorded by the source corpus.

We introduce a model for provable data possession (PDP) that allows a client that has stored data at an untrusted 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 proof. 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 storage system. We present two provably-secure PDP schemes that are more efficient than previous solutions, even when compared with schemes that achieve weaker guarantees. In particular, the overhead at the server is low (or even constant), as opposed to linear in the size of the data. Experiments using our implementation verify the practicality of PDP and reveal that the performance of PDP is bounded by disk I/O and not by cryptographic computation.

Subfields: Artificial Intelligence, Information Systems

View Paper: https://www.semanticscholar.org/paper/67708229c4579adabf7a2fbe0178a610d2eff788

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

Pors: proofs of retrievability for large files (2007, methodology): “[3] have considered an elegant application of RSA-based hashing to individual”
Cryptographic Cloud Storage (2010, background): “Proofs of storage were introduced in [2] and [26].”
Controlling data in the cloud: outsourcing computation without outsourcing control (2009, background): “, [7], [49]) the storage server can show a compact proof that it is correctly storing all of the client’s data.”
Data Security and Privacy Protection for Cloud Storage: A Survey (2020, methodology): “[2] and proof of retrievability (POR) model presented by Shacham and Waters [69].”
Toward publicly auditable secure cloud data storage services (2010, background): “Recently, great interest has been shown in ensuring remotely stored data integrity under different system and security models [6] [7] [8] [9] [10] [11] [12] [13] [14] [15].”
Enabling Public Verifiability and Data Dynamics for Storage Security in Cloud Computing (2009, methodology): “Recall that H ( name || i ) or h ( v || i ) should be generated by the client in the veriﬁcation process [1, 2].”
Security and privacy for storage and computation in cloud computing (2014, methodology): “[15] proposed the first construction of dynamic provable data possession, which extended the PDP model in [2] to achieve provable updating stored data using rank-based authenticated skip lists.”
HAIL: a high-availability and integrity layer for cloud storage (2009, methodology): “[2] propose a closely related construction called a proof of data possession (PDP).”
Big data privacy: a technological perspective and review (2016, background): “Therefore, the possibility that an untrusted cloud service provider infers the real frequent item set remains in the method [47].”
Proofs of Storage from Homomorphic Identification Protocols (2009, methodology): “We illustrate the use of our transformations by applying them to a variant of an identification protocol by Shoup, thus obtaining the first unbounded-use PoS based on factoring (in the random oracle model).”
Dynamic provable data possession (2009, methodology): “For example, the PDP scheme of [2] does not store any metadata at the client side.”
The Bouncer Problem: Challenges to Remote Explainability (2019, background): “Motivated by the plethora of oﬀers in the cloud computing domain and the question of quality of service, protocols such as proof of data possession [5], or proof-based veriﬁ-able computation [7], assume that the service provider might be malicious.”
Privacy-Preserving Audit and Extraction of Digital Contents (2008, methodology): “Some ([1], [11], and [23]) allow a third-party audit the data.”
MR-PDP: Multiple-Replica Provable Data Possession (2008, methodology): “Recently, there has been much interest in having clients (that do not have a copy of the data) check that servers have a copy of the data [4, 17, 23, 24].”
DupLESS: Server-Aided Encryption for Deduplicated Storage (2013, methodology): “Our approaches may be used in conjunction with existing mechanisms for availability auditing [13] [41] [51] [70] or file replication across multiple services [26].”
Permacoin: Repurposing Bitcoin Work for Data Preservation (2014, background): “A related vein of literature on Proofs of Data Possession (PDPs) [28] considers proofs that most, but not necessarily all of a file is stored.”
An Efficient Public Auditing Protocol With Novel Dynamic Structure for Cloud Data (2017, background): “[24] noted that the proposed scheme with public auditability in [23] might leak data information.”