27

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?

Garrett
  • 4,007
  • 2
  • 41
  • 59
user2191332
  • 1,059
  • 3
  • 17
  • 24

6 Answers6

14

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

user2191332
  • 1,059
  • 3
  • 17
  • 24
  • For Puzzle-friendliness:but what if you know that x is either 0 or 1? Given r and z you can easily find x. You simply try the 2 options. – – user2304458 Jun 19 '18 at 11:53
  • @user2304458 Yes, the property says that there exist no solution (to this computational puzzle) better than trying all the possible inputs. – Aditya Agarwal Aug 05 '21 at 06:27
10

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

SpiralDev
  • 7,011
  • 5
  • 28
  • 42
8

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.

David
  • 1,167
  • 15
  • 24
7

This course is extremely confusing and poorly written. read the EDIT at the end which gives another way to understand these definitions, and probably the correct one 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.

**EDIT: re-reading the definitions now, I think the function H(k|.): x-> H(k|x) is known by all parties. Hiding x means you can hide x with the function H(k|.) If I give you the value H(k|x) and the function H(k|.) then you can't find x. Thus the example I give with not being able to choose between 0 and 1 is correct. You can "solve the puzzle" (=solve for y=H(k|x)) but you can't solve for x.

Puzzle friendliness means that if I give you H(k|x) and the function H(k|.) then you can't find A value x' such that H(k|x)=H(k|x') without trying all x.

It really makes more sense that both party knows the function H(k|.) given the applications in the blockchain

ceillac
  • 167
  • 1
  • 3
  • I agree with you that in the definition of puzzle friendliness it's not clear if k is given or not to the puzzle solver. The same for the hiding problem. Do you have a better recommendation to learn the fundamentals of blockchain and cryptocurrencies? – chris elgoog Apr 17 '20 at 16:50
  • @chriselgoog Re-reading 2 years later...The way these definitions are given you could understand them in different ways. For the puzzle friendliness, if k is given then it's equivalent to reversing H. Maybe I got it wrong, from the context reading the book back then, and k is not given. Then puzzle friendliness would mean that adding a nonce doesn't not "simplify" H (to the point you could reverse it in less than 2^n trials). It actually makes more sense. Sorry I don't know other books but I'm sure there are now. If I had to learn again I would start with cryptology/cryptography – ceillac Apr 19 '20 at 01:58
  • Which course? There are several. From Princeton? – Rony Tesler Sep 03 '21 at 21:35
  • @ceillac I think in the princeton course he clearly says that k (or id or r) is given. If it's given, like you said in the answer, then you can reverse H before, no? That's also what you said in the comment I think, so maybe it would be better to edit the answer? – Rony Tesler Sep 03 '21 at 21:51
  • 1
    @Rony I added an edit but kept the 1st version too as I think both are correct mathematically – ceillac Sep 05 '21 at 06:58
0

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.

Kang
  • 545
  • 1
  • 7
  • 15
0

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 it is not quite so: An attacker can easily find x, given y=H(x), since there are only two possible hash values. He computes H(0) and H(1) and checks which one equals y. Done!

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.

J.T.
  • 194
  • 5