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.

(Joint work with Brent Waters)