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

Restructuring the definitions made it a bit clearer to me.

Collision-resistance:

Given: x and h(x)

Hard to find: y that is distinct from x and such that h(y)=h(x).

Hiding:

Given: h(r|x)

Secret: x and a highly-unlikely-and-randomly-chosen r

Hard to find: y such that h(y)=h(r|x).

This is different from collision-resistance in that it doesn’t matter whether or not y=r|x.

Puzzle-friendliness:

Given: z and a highly-unlikely-and-randomly-chosen r

Hard to find: x such that h(r|x)=z (but it should exist).

This is different from collision-resistance in that even if we have an algorithm to find a collision y, the constraint that the solution must start with r may make y not a solution.

This is different from hiding, similarly, because r is a constraint for the solution for puzzle-friendliness, but not a constraint in the hiding property because y is not required to equal r|x in that case. Also, for puzzle-friendliness, x is not known to anyone beforehand (not even the puzzle proposer).

Answer 2

Let's have: y = H(x|r). Here the output is y, and inputs are r and x.

Hiding property:

Given an output of a hash function (y), it is infeasible to find an input (x). Note, r is not given.

Puzzle-friendly property:

Given an output of a hash function (y) and part of the input (r), it is difficult to find an input (x).