Proofs of Retrievability via Fountain Code

Sumanta Sarkar and Reihaneh Safavi-Naini (University of Calgary, Canada)

Proofs of Retrievability (PoR) allows a verifier to check the integrity of its data stored at some remote untrusted cloud storage through an interactive challenge-response protocol with the storage (prover). An unbounded-use PoR scheme allows to run unbounded number of challenge-response interactions. Constructions of PoR scheme aim to minimize the communication complexity in the challenge-response protocol, the storage overhead and computation of responses. The security of a PoR scheme is formalized by showing the existence of an extractor which retrieves the file from an erasing adversary that can pass the challenge-response protocol with some reasonable probability. The extractor decodes the file by collecting the correct responses from the prover. In this paper, we modify the unbounded-use PoR scheme of Shacham and Waters (2008) to have faster computation of responses which uses XORing of data blocks. In our scheme, responses are the encoded symbols of a Fountain code and they are verified by using homomorphic linear authenticators. The number of data blocks that are challenged is probabilistic, which is $O(\log l)$ on the average case and $O(l)$ in the worst case, where $l$ is the security parameter. Response computation becomes faster if the number of challenged blocks is small.

FPS 2012 Program