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 |