Suppose Bob wants to give Alice a large file, in such a way that:

  • Bob cannot keep the file, but is able to use it to precompute anything he needs before he gives it to Alice
  • Bob must be able to challenge Alice periodically, and Alice can only successfully answer the challenge if and only if she is in possession of the file at the time the challenge is made (no shortcuts are permitted)
  • The challenge cannot consist of Alice sending Bob the file for him to check (each challenge must consist of an exchange of small, constant-size messages)

The naive approach is for Bob to generate a bunch of random nonces $N_0, N_1, \cdots$ and precompute $S_i = HMAC(N_i, file)$ and for the challenge to consist of sending the next $N_i$ and expecting back the corresponding $S_i$, but this has the downside that you can only prepare finitely many challenges in advance (Bob needs to get to the file to make some more) and Bob's space usage is proportional to the number of prepared challenges.

Can we do better? Is there an on-line protocol for this that doesn't require precomputing challenges in advance?

Basically I'm looking for a way to challenge a device to prove that it has access to a specific, potentially unbounded in size, piece of information (which the challenger only knows by some unique identifier and some kind of fingerprint) at the exact time the challenge is made without having to send the entirety of it over.



This is called a proof of retrievability or provable data possession (slightly different definitions for these two concepts). You will find many papers discussing constructions. Two of the most cited papers in this area are:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.