April 24, 2012 | C. Chris Erway, Alptekin K"upc"u, Charalampos Papamanthou, Roberto Tamassia
Dynamic Provable Data Possession (DPDP) extends the Provable Data Possession (PDP) model to support dynamic updates to stored data. The original PDP scheme applies only to static files, but DPDP allows for efficient updates, maintaining the same or better probability of detecting server misbehavior. The proposed DPDP schemes use authenticated dictionaries based on rank information, achieving a performance change from O(1) to O(log n) for file operations. Experiments show minimal overhead, with a 1GB file requiring 415KB proof size and 30ms computational overhead. The schemes are applied to outsourced file systems and version control systems. DPDP I uses a rank-based authenticated skip list, while DPDP II employs RSA trees for improved detection probability. Both schemes provide logarithmic computation and communication complexity, with DPDP I maintaining the same detection probability as original PDP. The DPDP I construction uses a rank-based authenticated skip list, enabling efficient authenticated operations on files at the block level. The scheme is secure under standard assumptions and allows for efficient verification of file integrity. The DPDP II scheme uses RSA trees for improved detection probability but requires higher server computation. The schemes are evaluated for security and efficiency, with DPDP I providing O(log n) expected update and query times, and O(1) client storage. The security of the schemes is proven under collision-resistant hash functions and factoring assumptions.Dynamic Provable Data Possession (DPDP) extends the Provable Data Possession (PDP) model to support dynamic updates to stored data. The original PDP scheme applies only to static files, but DPDP allows for efficient updates, maintaining the same or better probability of detecting server misbehavior. The proposed DPDP schemes use authenticated dictionaries based on rank information, achieving a performance change from O(1) to O(log n) for file operations. Experiments show minimal overhead, with a 1GB file requiring 415KB proof size and 30ms computational overhead. The schemes are applied to outsourced file systems and version control systems. DPDP I uses a rank-based authenticated skip list, while DPDP II employs RSA trees for improved detection probability. Both schemes provide logarithmic computation and communication complexity, with DPDP I maintaining the same detection probability as original PDP. The DPDP I construction uses a rank-based authenticated skip list, enabling efficient authenticated operations on files at the block level. The scheme is secure under standard assumptions and allows for efficient verification of file integrity. The DPDP II scheme uses RSA trees for improved detection probability but requires higher server computation. The schemes are evaluated for security and efficiency, with DPDP I providing O(log n) expected update and query times, and O(1) client storage. The security of the schemes is proven under collision-resistant hash functions and factoring assumptions.