Biblio

Using erasure codes increases consumption of network traffic and disk I/O tremendously when systems recover data, resulting in high latency of degraded reads. In order to mitigate this problem, we present an adaptive storage scheme based on data access skew, a fact that most data accesses are applied in a small fraction of data. In this scheme, we use both Local Reconstruction Code (LRC), whose recovery cost is low, to store frequently accessed data, and Hitchhiker (HH) code, which guarantees minimum storage cost, to store infrequently accessed data. Besides, an efficient switching algorithm between LRC and HH code with low network and computation costs is provided. The whole system will benefit from low degraded read latency while keeping a low storage overhead, and code-switching will not become a bottleneck.

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 computation 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 (EUROCRYPT 2013) is mostly of theoretical interest, as it employs Oblivious RAM (ORAM) as a black box, leading to increased practical overhead (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 outperforms the constructions of Stefanov et. al. and Cash et. al., both in theory and in practice. Specifically, for n outsourced blocks of beta bits each, writing a block requires beta+O(lambdalog n) bandwidth and O(betalog n) server computation (lambda is the security parameter). Audits are also very efficient, requiring beta+O(lambda^2log n) 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 efficient implementation of our scheme.