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.