Beyond proofs of data possession: Finding defective blocks in outsourced storage

Proofs of Data Possession (PDPs) are protocols that allow a file owner to verify that a file stored at an outsourced server is stored entirely. From a security perspective, it must be difficult for the server to pass the verification protocol if the file is not available. Even though several efficient PDPs exist in the literature, to the best of our knowledge no special algorithms, besides the existing combinatorial approaches have been designed to find what exact blocks of the file are defective. In this article we present an efficient method to find what blocks are defective in a server, even when the server might lie; we show that by taking advantage of the homomorphic properties of existing PDPs, we can improve existing combinatorial methods to find the defective blocks. Our method involves a single invocation of the PDP's verification protocol and an additional communication overhead, which is never larger than the number of blocks of the file regardless of the number of missing blocks. For cases where few blocks have been corrupted, the transmission overhead is proportional to the the number of missing block times the logarithm of the length of the file. This is a significant improvement from existing combinatorial methods which exhibit worse performance than the naive approach (where the result of the PDP for each block is sent independently) as the number of corrupted blocks increases.