I find myself wanting to test out a practical implementation of a proof-of-retrievability scheme, simply out of curiosity. These schemes seem to be divided into two variations, publicly-verified and privately-verified. Here's a brief explanation of the problem:
Alice sends a very large file to Bob.
Bob agrees to store the file for Alice in exchange for $5 per month.
Alice is suspicious of Bob's intentions, and suspects that Bob could delete all or part of the file and fool her into paying $5 per month, without Bob holding up his end of the agreement. Therefore, Alice wants to conduct periodic random audits to verify that Bob is in fact storing all of the file, as agreed upon.
Alice could download the entire file from Bob, and then verify the hash of the file against one that was recorded earlier. However this would waste a lot of bandwidth, and also take a lot of time, since the file is very large.
Instead, Alice would like a more efficient interactive audit protocol, in which she chooses a random subset of the contents of the file, and Bob must be able to correctly respond with an answer that is based off of those parts of the file. Since Bob doesn't know which parts of the file will be needed in the future to pass the audit, Bob is forced to store the entire file, or he will fail the next audit. Since Bob is storing the entire file, it is reasonable to say that Bob is holding up his end of the agreement.
Same as the above, except we have a third party, Carol, who also wants to audit Bob to verify that he is storing Alice's file. Carol might have more limited information about the file, for example, Carol might never have actually seen Alice's file. However Carol still needs to be able to perform the audit.
I have looked at two papers on this subject (see below) and it seems like a simple but inefficient privately-verifiable scheme is possible using MACs. More efficient schemes seem to use complicated "homomorphic linear authenticators" and fountain codes. It also seems like these more advanced schemes allow an unlimited number of challenge-response verifications to be performed in the future.
Unfortunately my understanding of this subject is limited, so my goal is to piece together a working implementation of a simple scheme that does not require advanced knowledge of cryptography. That said, I am most interested in the public verification aspect of proof-of-retrievability schemes, and it seems like the simple scheme using MACs is only privately verifiable. It also seems like there is a trade-off between the algorithm's efficiency and complexity.
So my question is, if we relax the requirement of being able to perform an unbounded number of verifications, and we also relax the requirement of using resources efficiently, is it still possible to produce a proof-of-retrievability scheme which is both publicly-verifiable and simple in construction?
Any additional information about this would also be appreciated.