Does there exist a proof-of-retrievability scheme that is publicly-verifiable, limited-use, and does not use homomorphic encryption? 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:

Private:


  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.


Public:


  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.




"Proofs of Storage from Homomorphic Identication Protocols" (Ateniese et al)
"Compact Proofs of Retrievability" (Shacham and Waters)
I do not know of any approaches in context of proofs or retrievability (PoRs)/provable data possession (PDP) that use homomorphic encryption. However, many of those schemes employ homomorphic (linear) authenticators/tags for the metadata such that the proofs delivered by the server can be of constant size, i.e., by aggregating single tags.

Now to some misunderstanding regarding the type of verifiability: 

Public verifiability in this context means that the data owner who initially outsources the file is the only entity that can modify the data, but a third party, which is given some public information, can only verify a proof from the server that the data is available, i.e., check that the data is still available/retrievable. 

Consequently, public verifiability always involves some secret that is only known to the data holder (who creates the file and metadata and may modify the stored data and the corresponding tags) and some public information (corresponding to that secret) that can be given to some third party such that it can trigger proofs for availability of the data (but cannot modify/replace the data). Thus, the party in possession of the public information can only check if data is available, but can not modify already stored data in such a way that a proof after modification of the data will still succeed.

As a consequence, MAC based PoRs/PDP schemes, which are essentially the same but have different security models, can never achieve public verifiability as it is defined in this setting, as it would require to share the respective secret (and this allow modifications). The same holds for any secret key only scheme.

Clearly, the use of a privately or publicly verifiable scheme to allow another third entity (distinct form the data holder) to request and verify proofs from the server depend on your trust model. Public verifiability assumes that the third entity is semi trusted, i.e., only trusted to conduct the proofs honestly, but you do not trust the third party that it wont modify the stored data. If you fully trust the third party, i.e., you are sure that it will not modify your data unauthorized, you can also use a privately verifiable scheme and simply give away your secret to the third party. However, this is a quite strong assumption.

Typically, such PoR/PDP schemes are either private verifiable or public verifiable. But there are also protocols which achieve unbounded private and public verifiability at a quite low cost simultaneously (based on the same metadata/tags). You may look here for such a scheme. However, it is based on pairing friendly elliptic curves and may not be that straightforward to understand as you say your knowledge is quite limited.

A very simple and easy to understand privately verifiable but bounded use scheme is presented here, but it does not support public verifiability as discussed above. Nevertheless, it is easy to implement and may be sufficient for your purpose.