Paper 2008/073

Compact Proofs of Retrievability

Hovav Shacham and Brent Waters


In a proof-of-retrievability system, a data storage center must prove to a verifier that he is actually storing all of a client's data. The central challenge is to build systems that are both efficient and provably secure -- that is, it should be possible to extract the client's data from any prover that passes a verification check. All previous provably secure solutions require that a prover send O(l) authenticator values (i.e., MACs or signatures) to verify a file, for a total of O(l^2) bits of communication, where l is the security parameter. The extra cost over the ideal O(l) communication can be prohibitive in systems where a verifier needs to check many files. We create the first compact and provably secure proof of retrievability systems. Our solutions allow for compact proofs with just one authenticator value -- in practice this can lead to proofs with as little as 40 bytes of communication. We present two solutions with similar structure. The first one is privately verifiable and builds elegantly on pseudorandom functions (PRFs); the second allows for publicly verifiable proofs and is built from the signature scheme of Boneh, Lynn, and Shacham in bilinear groups. Both solutions rely on homomorphic properties to aggregate a proof into one small authenticator value.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Extended abstract to appear in Proc. Asiacrypt 2008.
storageretrievabilityhomomorphic authenticators
Contact author(s)
hovav @ cs ucsd edu
2011-01-12: last of 7 revisions
2008-02-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hovav Shacham and Brent Waters},
      title = {Compact Proofs of Retrievability},
      howpublished = {Cryptology ePrint Archive, Paper 2008/073},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.