properties of a cryptographic hash function

Question

In the week 1 lecture of the bitcoin coursera course, there is a discussion of the 3 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 2^n.

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

Answer 1

Let us breakdown the problem by taking examples. 

Let’s assume you have a hash by the name ‘Roshan’. 

You pick a' and along with that you consider a random nonce r'. 

So, to compute b’, 

b’ = Roshan(r'|a')

If a' is an UTF8-encoded English text, I can tell you what a' was, and I can even tell you the value of the nonce r'. But, if a' was just a random bit-string, it would be impossible for me to tell its initial value. Therefore, ic can be concluded that ‘Roshan’ is not a hiding hash.

For the Puzzle friendliness property, 

Take a value B', and a randomly chosen value R' (say "11110011...111"), and find an A so that Roshan(R'|A) = B'. 

We can say that B'= Roshan(00101...0001 | UTF8("Bitcoin is deflationary")). And as the hash ‘Roshan’ is non-hiding, it is possible to determine an R’ (saying 00101...0001), and A (namely UTF8("Bitcoin is deflationary")), such that BadHash(R|A) = B' 

But this doesn't come of any help to you as in the puzzle you specified that you require an A that works with a different R, namely "11110011...100".

This is how we can say that the properties of Hiding and Puzzle Friendliness aren't of any equivalency. 

Answering the last question that you asked, I am not sure if there are any cryptographic hash functions that feature only one of these properties but not both.