Towards Efficient Provable Data Possession.
Jia Hao Xu, Ee‐Chien Chang · IACR Cryptology ePrint Archive · 2011
Provable Data Possession (PDP) allows data owner to periodically and remotely audit their data stored in a cloud storage, without retrieving the file and without keeping a local copy. Ateniese et al. (CCS 07) proposed the first PDP scheme, which is very efficient in communication and storage. However their scheme requires a lot of group exponentiation operations: In the setup, one group exponentiation is required to generate a tag per each data block. In each verification, (equivalently) (m + `) group exponentiations are required to generate a proof, where m is the size of a data block and ` is the number of blocks accessed during a verification. This paper proposed an efficient PDP scheme. Compared to Ateniese et al. (CCS 07), the proposed scheme has the same complexities in communication and storage, but is more efficient in computation: In the setup, no group exponentiations are required. In each verification, only m group exponentiations are required to generate a proof. The security of the proposed scheme is proved under Knowledge of Exponent Assumption and Factoriztion Assumption. 1 Overview Ateniese et al. [ABC07] proposed the first Provable Data Possession (PDP for short) scheme. Their scheme is very efficient in communication and storage: the size of a proof is independent on the number of blocks accessed during a verification and the storage overhead due to authentication tags is a fraction of the size of the original data. However, their scheme requires a large number of modular exponentiation in both setup phase and verification phase, and is thus relative expensive in computation. In this paper, we will propose a new PDP construction named POS, which requires no modular exponentiation in the setup phase and a smaller number of group exponentiations in verification phase, without sacrificing in communication or storage aspects. We remark that both Ateniese et al. [ABC07, ABC11] and the proposed scheme in this paper support only private key verification. ∗This is the full version of the PDP scheme described in the Appendix of Cryptology ePrint Archive, Report 2011/362. This fraction is a configurable system parameter.