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.
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?