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

Juan Camilo Corena, Anirban Basu, Shinsaku Kiyomoto, Yutaka Miyake, Tomoaki Ohtsuki

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish
Title of host publication2014 IEEE Global Communications Conference, GLOBECOM 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781479935116
Publication statusPublished - 2014 Feb 9
Event2014 IEEE Global Communications Conference, GLOBECOM 2014 - Austin, United States
Duration: 2014 Dec 82014 Dec 12

Publication series

Name2014 IEEE Global Communications Conference, GLOBECOM 2014


Other2014 IEEE Global Communications Conference, GLOBECOM 2014
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Computer Networks and Communications
  • Communication


Dive into the research topics of 'Beyond proofs of data possession: Finding defective blocks in outsourced storage'. Together they form a unique fingerprint.

Cite this