Objective: A verifier wants to ensure that a block of data M is also known to a prover. The protocol should exchange little information and should not leak information about the value of M.

Proposed Protocol:
V -> P: challenge c
P -> V: response r = f(M, c)

Question: What is a suitable and efficient function f?

What comes to mind first is to use a hash function, such as SHA2(c concatenate M), which may meet the objective. We could also compute SHA2(M xor c'), where c' is derived by repeating c as required to get to the length of M.

What concerns me is that SHA2(M concatenate c) will not meet the requirement. The prover could simply compute SHA2(M) partially up to the last full block of M, store the intermediate state of the hash function, and then delete the part of M that was already processed. When confronted with a challenge c the prover can pick up the state where it was left and finalize the computation without actually knowing M anymore.

Does anyone see such pitfalls with SHA2(c concatenate M) or SHA2(M xor c) or have other suggestions?

  • $\begingroup$ I don't see "such" pitfalls, but a challenge-response pair allows an eavesdropper to try as many guesses at M as it wants, so that can leak a fairly significant amount of information about M. ​ ​ $\endgroup$
    – user991
    Commented Jan 28, 2016 at 0:07
  • $\begingroup$ I think you're looking for HMAC with as key the challenge and as message the block? HMAC was basically made to prevent length extension attacks. You could also use SHA3 which is invulnerable to length-extension attacks. $\endgroup$ Commented Feb 27, 2016 at 11:03
  • $\begingroup$ It seems to me that a natural way to reach your goal and avoid your pitfalls would be to stretch c' from c using a pseudo-random generator, and then compute H(m xor c'). Also, the challenge c can be replaced by a key K, computed from a key exchange protocol (to avoid leaks to potential eavesdropper), but it involves public key operation; what are your efficiency requirements? $\endgroup$ Commented Feb 27, 2016 at 13:44

1 Answer 1


From your question, I believe that what you are looking for is a proof of storage. I will point you in the direction of one paper, and you can use that to look for other work on the topic.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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