Practical dynamic proofs of retrievability

Proofs of Retrievability (PoR), proposed by Juels and Kaliski in 2007, enable a client to store n file blocks with a cloud server so that later the server can prove possession of all the data in a very efficient manner (i.e., with constant computa-tion and bandwidth). Although many efficient PoR schemes for static data have been constructed, only two dynamic PoR schemes exist. The scheme by Stefanov et al. (ACSAC 2012) uses a large of amount of client storage and has a large audit cost. The scheme by Cash et al. (EUROCRYPT 2013) is mostly of theoretical interest, as it employs Oblivious RAM (ORAM) as a black box, leading to increased practical over-head (e.g., it requires about 300 times more bandwidth than our construction). We propose a dynamic PoR scheme with constant client storage whose bandwidth cost is comparable to a Merkle hash tree, thus being very practical. Our construction out-performs the constructions of Stefanov et al. and Cash et al., both in theory and in practice. Specifically, for n outsourced blocks of β bits each, writing a block requires β+O(λ logn) bandwidth and O(β logn) server computation (λ is the se-curity parameter). Audits are also very efficient, requiring β +O(λ2 logn) bandwidth. We also show how to make our scheme publicly verifiable, providing the first dynamic PoR scheme with such a property. We finally provide a very effi-cient implementation of our scheme