"proof of access" schemes What is the state of the art way when implementing a scheme challenging a party to prove they have access to certain data?

What I'm looking for something along the lines of 


Give them (id-some-data, random-data, my public-key).
Request to return the signature of (some-data xor random-data) with my-public-key.
Give them (id-some-data, random-data).
Request to return hash(random-data + some-data)


So basically I'd like to verify if the other party has access to the requested data and prevent them from precalculating the proof of it.

What is the correct name for such schemes in the crypto world?

What would be the theoretical difference between the two schemes above? (other than probably higher "security" of the PubPriv key scheme compared to the hash functions available).

P.S.: I do know better than to implement own crypto ;) The above are just examples to explain what I'm looking for.
I'd go with hash(ProverPublicKey || RandomChallenge || Data) over your idea of hash(RandomChallenge || Data). Your scheme has the problem that the prover might challenge another party to prove that they have the data and forward that prove to the original challenger.

Related keywords are proof-of-retrievability, proof-of-ownership or proof-of-data-possession.