How can I repeatedly prove I have data another has seen without sending the data and without the other storing the data?

Question

I would like to know if this is theoretically possible, or impossible, and if possible, if there is any algorithm/protocol to accomplish this...

I want another entity, lets call them the Auditor, to be able to see a piece of data, store something smaller that's derived from that data (I might not know what it is), and then I want to be able to prove to the Auditor repeatedly that I still have that piece of data without having to send the data itself.

• If we relax the last requirement I could just send the data every time and the Auditor could verify the hash.
• If we relax the 'repeatedly' requirement the Auditor could store a salted hash without telling me the salt, and then later give me the salt and ask for the salted hash back, but that only works one time since afterwards I could just remember the salted hash, throw away the data, and still fool the Auditor.
• If we relax the 'derived' requirement the Auditor could store its own copy of the data and do a simple challenge-response protocol.
• ... but I haven't been able to figure out how to do it without relaxing any of these requirements.

THANKS!

Answer 1

What you are describing is a particular type of "Provable Data Possession." There have been a number of papers in this area recently (try googling it). A closely related concept is "Proof of Retrievability."

If I recall correctly, the protocols in the paper I cited above have all the properties you are interested in. It may not be the first paper to achieve them (I believe this one is) but anyways, sometimes having the right term to search for is a good head start.

Answer 2

I will just add few comments to the excellent answer and links provided by PulpSpy above which might help you getting the more correct paper from the pool of thousands of paper written in this area, both by theoreticians and practitioners.

If you want to have a proof that prove the possession of any bit of the data file, then the paper of Atienese et al. cited by PulpSpy doesn't work (they work for more practial scenario and are very fast). Naor and Ruthblum, actually, gave the protocol in The Complexity of Online Memory Checking for proving data possession at any granularity. They called it memory checkers. They also relaxed the notion of memory checkers to prove the result for something called authenticator, which can be seen in the same vein as the definition of Proof of Data Possession and Proof of Retrievability, first defined by Juels and Karlinski in Pors: proofs of retrievability for large files. Incidentally, both the papers came in the same conference, presented one after the other. The work of Atienese et al. was later shown to possess the stronger notion of Proof of Retrievability by Waters and Shacham in Compact Proof of Retrievability.

The literature for this problem is very old and Naor and Ruthblum has a very detailed literature survey in their paper. You may find the reference therein quiet useful. For recent works, there has been quiet a few works on this area.