Robust dynamic provable data possession

Bo Chen, Reza Curtmola

Research output: Contribution to conferencePaperpeer-review

50 Scopus citations


Remote Data Checking (RDC) allows clients to efficiently check the integrity of data stored at untrusted servers. This allows data owners to assess the risk of outsourcing data in the cloud, making RDC a valuable tool for data auditing. A robust RDC scheme incorporates mechanisms to mitigate arbitrary amounts of data corruption. In particular, protection against small corruptions (i.e., bytes or even bits) ensures that attacks that modify a few bits do not destroy an encrypted file or invalidate authentication information. Early RDC schemes have focused on static data, whereas later schemes such as DPDP support the full range of dynamic operations on the outsourced data, including insertions, modifications, and deletions. Robustness is required for both static and dynamic RDC schemes that rely on spot checking for efficiency. However, under an adversarial setting there is a fundamental tension between efficient dynamic updates and the encoding required to achieve robustness, because updating even a small portion of the file may require retrieving the entire file. We identify the challenges that need to be overcome when trying to add robustness to a DPDP scheme. We propose the first RDC schemes that provide robustness and, at the same time, support dynamic updates, while requiring small, constant, client storage. Our first construction is efficient in encoding, but has a high communication cost for updates. Our second construction overcomes this drawback through a combination of techniques that includes RS codes based on Cauchy matrices, decoupling the encoding for robustness from the position of symbols in the file, and reducing insert/delete operations to append/modify operations when updating the RS-encoded parity data.

Original languageEnglish (US)
Number of pages11
StatePublished - 2012
Externally publishedYes
Event32nd IEEE International Conference on Distributed Computing Systems Workshops, ICDCSW 2012 - Macau, China
Duration: Jun 18 2012Jun 21 2012


Other32nd IEEE International Conference on Distributed Computing Systems Workshops, ICDCSW 2012

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering


  • PDP
  • cloud storage
  • dynamic updates
  • remote data checking
  • robustness
  • security


Dive into the research topics of 'Robust dynamic provable data possession'. Together they form a unique fingerprint.

Cite this