A coding theory approach to unconditionally secure proof-of-retrievability schemes for cloud storage Douglas Stinson (University of Waterloo). |
---|

There has been considerable
recent interest in
cloud storage wherein a user asks a
server to store a large file. One issue is whether the user can
verify that the server is actually storing the file, and
typically a challenge-response protocol is employed to convince
the user that the file is indeed being stored correctly. The
security of these schemes is phrased in terms of an extractor
which will recover or retrieve the file, given any
proving algorithm that has a sufficiently high success
probability. We investigate proof-of-retrievability (POR)
schemes in the model of unconditional security, where an
adversary has unlimited computational power. In this case
retrievability of the file can be modelled as error-correction
in a certain code. We provide a general analytical framework
for such schemes that yields exact (non-asymptotic) reductions
that precisely quantify conditions for extraction to succeed
as a function of the success probability of a proving
algorithm, and we apply this analysis to several archetypal
schemes. In addition, we provide a new methodology for the
analysis of keyed (unbounded-use) POR schemes in an
unconditionally secure setting, and use it to prove the
security of a modified version of a scheme due to Shacham and
Waters under a slightly restricted attack model, thus
providing the first example of a keyed POR scheme with
unconditional security. This talk is based on joint work with
Maura Paterson and Jalaj. FPS 2012 Program |