Search code examples
hashcryptographyblockchain

properties of a cryptographic hash function

In a bitcoin Coursera course, there is a discussion of the three properties of a cryptographic hash functions:

Collision-resistance: A hash function H is said to be collision resistant if it is infeasible to find two values, x and y, such that x != y, yet H(x)=H(y).

Hiding: A hash function H is hiding if: when a secret value r is chosen from a probability distribution that has high entropy, then given H(r ‖ x) it is infeasible to find x. ‖ means concatenation of two strings.

Puzzle friendliness: A hash function H is said to be puzzle-friendly if for every possible n-bit output value y, if k is chosen from a distribution with high entropy, then it is infeasible to find x such that H(k ‖ x) = y in time significantly less than 2n.

Puzzle friendliness seems to be a more detailed description of hiding. Is there any significant differences between the two? Are there hash functions with one of the properties but not both?

Solution

  • I had the same thought, and the difference is indeed subtle. I had to think about this awhile.

    Suppose you had a hash, BadHash. You pick x' and a random nonce r', compute y' = BadHash(r'|x'), and give me y'. It turns out that if x' is UTF8-encoded English text, I am able to tell you what x' was, and (though not strictly necessary), I can even tell you r'. If x' happened to be just a random bit-string, I'd be out of luck. But no matter, this is clearly not a hiding hash.

    Now the puzzle: I give you a value Y', and a randomly chosen value R' (say "11110011...100"), and ask you to find an x such that BadHash(R'|x) = Y'. Good news: it turns out that Y'= BadHash(00101...0001 | UTF8("Bitcoin is deflationary")). So because BadHash is non-hiding (plus), you can determine an R (namely 00101...0001), and and x (namely UTF8("Bitcoin is deflationary")), such that BadHash(R|x) = Y' But this doesn't help you, because the puzzle specified that you need an x that works with a different R, namely "11110011...100". So you haven't solved the puzzle.

    You see, then, that the two properties aren't equivalent. As to whether there are indeed hashes with one property but not the other -- that I don't know.