Paper 2009/041

Proofs of Retrievability via Hardness Amplification

Yevgeniy Dodis, Salil Vadhan, and Daniel Wichs

Abstract

Proofs of Retrievability (PoR), introduced by Juels and Kaliski, allow the client to store a file $F$ on an untrusted server, and later run an efficient audit protocol in which the server proves that it (still) possesses the client's data. Constructions of PoR schemes attempt to minimize the client and server storage, the communication complexity of an audit, and even the number of file-blocks accessed by the server during the audit. In this work, we identify several different variants of the problem (such as bounded-use vs. unbounded-use, knowledge-soundness vs. information-soundness), and giving nearly optimal PoR schemes for each of these variants. Our constructions either improve (and generalize) the prior PoR constructions, or give the first known PoR schemes with the required properties. In particular, we \begin{itemize} \item Formally prove the security of an (optimized) variant of the bounded-use scheme of Juels and Kaliski~\cite{JuelsK07}, without making any simplifying assumptions on the behavior of the adversary. \item Build the first unbounded-use PoR scheme where the communication complexity is linear in the security parameter and which does not rely on Random Oracles, resolving an open question of Shacham and Waters~\cite{ShachamW08}. \item Build the first bounded-use scheme with {\em information-theoretic} security. \end{itemize} The main insight of our work comes from a simple connection between PoR schemes and the notion of {\em hardness amplification}, extensively studied in complexity theory. In particular, our improvements come from first abstracting a purely information-theoretic notion of {\em PoR codes}, and then building nearly optimal PoR codes using state-of-the-art tools from coding and complexity theory.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Full version of TCC 2009 paper.
Contact author(s)
wichs @ cs nyu edu
History
2009-01-29: received
Short URL
https://ia.cr/2009/041
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/041,
      author = {Yevgeniy Dodis and Salil Vadhan and Daniel Wichs},
      title = {Proofs of Retrievability via Hardness Amplification},
      howpublished = {Cryptology ePrint Archive, Paper 2009/041},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/041}},
      url = {https://eprint.iacr.org/2009/041}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.