Back

Explore Courses Blog Tutorials Interview Questions
0 votes
2 views
in Blockchain by (4.1k points)

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?

1 Answer

0 votes
by (14.4k points)

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. 

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
asked Oct 29, 2019 in Java by Anvi (10.2k points)
Welcome to Intellipaat Community. Get your technical queries answered by top developers!

29.3k questions

30.6k answers

501 comments

104k users

Browse Categories

...