3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you mean a proof that can be generated having only Y but not X, or a proof that can be verified without requiring X to be known and without revealing more about X than F(X)=Y does? (It is unavoidable to reveal some information about X, namely the fact that F(X)=Y, which e.g. when F is a bijection with a feasibly computable inverse degenerates to revealing X.) Are you asking about an interactive proof, or about a static proof? $\endgroup$ – Gilles 'SO- stop being evil' Jan 18 '17 at 21:46
  • $\begingroup$ @Gilles the later ("a proof that can be verified without requiring X to be known and without revealing more about X than F(X)=Y does"). I'm asking about a static, non-interactive proof. $\endgroup$ – MaiaVictor Jan 18 '17 at 21:48
  • 1
    $\begingroup$ I find this question confusing $\endgroup$ – paparazzo Jan 18 '17 at 23:54
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The principle of a hash function is that multiple, different values can hash to the same key. The complexity of the hashing function determines how many possible values X may have. Consequentially it becomes impossible to prove that F(X) == Y if Y is a single value. After all, if X can be either 2 or 3 and F(X) = 2*X then Y is both 4 and 6.

If F(X) is considered to be a set of possible solutions then you only have to prove that your given value 'Y' is a member of this set. The actual value of X is not a requirement to solve this problem and therefore it is possible to prove.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I suspect MaiaVictor is considering the case of a cryptographic hash function, and considering only adversaries who are computationally limited, so we can effectively assume that no one can find any collision. Or, if you prefer, think of it as a cryptographic commitment rather than a hash (there exist commitment schemes that are perfectly binding and thus have no collisions). Consequently, I don't think this answers the question that MaiaVictor probably intended to ask. I agree this should have been clearer in the question. $\endgroup$ – D.W. Jan 18 '17 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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