Generic Efficient Dynamic Proofs of Retrievability

Together with its great advantages, cloud storage brought many interesting security issues to our attention. Since 2007, with the first efficient storage integrity protocols Proofs of Retrievability (PoR) of Juels and Kaliski, and Provable Data Possession (PDP) of Ateniese et al., many researchers worked on such protocols.

The difference among PDP and PoR models were greatly debated. The first DPDP scheme was shown by Erway et al. in 2009, while the first DPoR scheme was created by Cash et al. in 2013. We show how to obtain DPoR from DPDP, PDP, and erasure codes, making us realize that even though we did not know it, we could have had a DPoR solution in 2009.

We propose a general framework for constructing DPoR schemes that encapsulates known DPoR schemes as its special cases. We show practical and interesting optimizations enabling better performance than Chandran et al. and Shi et al. constructions. For the first time, we show how to obtain constant audit bandwidth for DPoR, independent of the data size, and how the client can greatly speed up updates with O(ln) local storage (where n is the number of blocks, and l is the security parameter), which corresponds to ~ 3MB for 10GB outsourced data, and can easily be obtained in today's smart phones, let alone computers.