Dynamic provable data possession
Chris Erway, Alptekın Küpçü, Charalampos Papamanthou et al. · Proceedings of the ACM Conference on Computer and Communications Security · 2009
We consider the problem of efficiently proving the integrity of data stored at untrusted servers. In the provable data possession (PDP) model, the client preprocesses the data and then sends it to an untrusted server for storage, while keeping a small amount of meta-data. The client later asks the server to prove that the stored data has not been tampered with or deleted (without downloading the actual data). However, the original PDP scheme applies only to static (or append-only) files.We present a definitional framework and efficient constructions for dynamic provable data possession (DPDP), which extends the PDP model to support provable updates to stored data. We use a new version of authenticated dictionaries based on rank information. The price of dynamic updates is a performance change from O(1) to O(logn) (or O(nelog n), for a file consisting of n blocks, while maintaining the same (or better, respectively) probability of misbehavior detection. Our experiments show that this slowdown is very low in practice (e.g. 415KB proof size and 30ms computational overhead for a 1GB file). We also show how to apply our DPDP scheme to outsourced file systems and version control systems (e.g. CVS).
Cited by 897 works. doi:10.1145/1653662.1653688
Authors
References
- Riemann's Hypothesis and tests for primality
- OceanStore
- Short Signatures from the Weil Pairing
- A Digital Signature Based on a Conventional Encryption Function
- Provable data possession at untrusted stores
- Skip lists: a probabilistic alternative to balanced trees
- Pors
- Compact Proofs of Retrievability
- Scalable and efficient provable data possession
- Plutus: Scalable Secure File Sharing on Untrusted Storage