Robust remote data checking

Remote data checking protocols, such as provable data possession (PDP) 1, allow clients that outsource data to untrusted servers to verify that the server continues to correctly store the data. Through the careful integration of forward error-correcting codes and remote data checking, a system can prove possession with arbitrarily high probability. We formalize this notion in the robust data possession guarantee. We distill the key performance and security requirements for integrating forward error-correcting codes into PDP and describe an encoding scheme and file organization for robust data possession that meets these requirements. We give a detailed analysis of this scheme and build a Monte-Carlo simulation to evaluate tradeoffs in reliability, space overhead, and performance. A practical way to evaluate these tradeoffs is an essential input to system design, allowing the designer to choose the encoding and data checking protocol parameters that realize robust data possession.