Paper 2016/748

A Generic Dynamic Provable Data Possession Framework

Mohammad Etemad and Alptekin Küpçü

Abstract

Ateniese et al. introduced the Provable Data Possession (PDP) model in 2007. Following that, Erway et al. adapted the model for dynamically updatable data, and called it the Dynamic Provable Data Possession (DPDP) model. The idea is that a client outsources her files to a server, and later on challenges the server to obtain a proof that her data is kept intact. During recent years, many schemes have been proposed for this purpose, all following a similar framework. We analyze in detail the exact requirements of dynamic data outsourcing schemes regarding security and efficiency, and propose a general framework for constructing such schemes that encompasses existing DPDP-like schemes as different instantiations. We show that a dynamic data outsourcing scheme can be constructed given black-box access to an implicitly-ordered authenticated data structure (that we define). Moreover, for blockless verification efficiency, a homomorphic verifiable tag scheme is also needed. We investigate the requirements and conditions these building blocks should satisfy, using which one can easily check applicability of a given building block for dynamic data outsourcing. Finally, we provide a comparison among different building blocks.