properties of a cryptographic hash function

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).


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).