Given the hash of a collection, H(X), can I build a proof that F(X) == Y, without having X?

Given a cryptographic fingerprint of a collection, K == hash(X), an arbitrary function F, and a value Y, is it possible to build a short proof that F(X) == Y that doesn't require having X? I.e., a proof that Y is the result of applying F to some X such that hash(X) == K?

Yes, this is possible. Use a zero knowledge proof (of knowledge). If F is computable in polynomial time, then there exists a polynomial-time zero-knowledge proof of the property you want, i.e., given K,Y, the prover can construct a proof that there exists X such that H(X)=K and F(X)=Y. Amazingly, this proof is "zero-knowledge": it reveals nothing about X (other than the property is true).

If you don't care about the zero knowledge part, you can just use an interactive proof system.

Zero-knowledge proofs can be made non-interactive using standard techniques.

There's tons of work on this in the cryptographic research literature. I can't explain the ideas in the length of an answer here, so I suggest you spend some quality time studying this material. However, while the theory is elegant and beautiful, you're probably going to find the generic schemes are not very practical and the performance overhead is significant. Therefore, if you actually want to do this in practice, you'll want to focus on a specific function F and see whether you can build a custom protocol specialized to that particular function F.

StackExchange Computer Science Q#68945, answer score: 5