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

This course is extremely confusing and poorly written.

In the hiding problem, you are trying to find x, knowing the value H(r|x) (and knowing H of course). But you don't know r! For example the set for x could be {0,1} but you can't decide between 0 or 1 because adding a secret r to x mixes all the possible hashes.

In the puzzle friendly problem, k (or r) is given! The problem here is to try all the possible x till you find one that gives the correct hash y . So you will end up finding one but it will take time. (The reason to have k (or r) in the definition is confusing, it just means we can't cheat by having reversed H before).

In the hiding problem even if you try all possible r and x for H before. It will not work because you could find r',x',r'',x'' such that H(r'|x') =H(r''|x''). And since you don't know which value of r is the correct one then it is impossible to find x.

Answer 2

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.

Answer 3

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

Answer 4

Assume that x is the outcome of a coin toss, ie. x is 0 or 1. Given H(x) noone should be able to find x, but... An attacker can easily find x, given y=H(x), since there there are only two possible hash values. He computes H(0) and H(1) and checks which one equals y.

Now, assume that you prepend a large random key to x and you compute H(k x). If the key is secret, the attacker cannot find x easily, since he would have to try a lot of possible secret keys.

This is actually on the course slides :-) , but not really explained in words.

Answer 5

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 6

Consider this algo: Take any text file and assume a=1, b=2, c=3 and so on and calculate the sum for all the letters and if the net sum is less than 5 you win an award. Lets say you didn't win the first time, so you add some arbitrary text to the end of this file(nonce) and do this calculation again, until you win.

This algo is puzzle friendly but not good at hiding since you can easily guess what effect the nonce will have on the output.