Re: cryptographic hash functions versus non-cryptographic hash functions

Kristian Gjøsteen wrote:


What does "conditional entropy of the output" mean.


Exactly what "conditional entropy" meant for Shannon.

What does "sorting the input regarding the entropy

> of the output" mean?

Naively expressed: Create a table which maps all inputs to all outputs. Now sort regarding the output and delete all duplicate entries. Now sort the input. Instead of bruteforcing, just check for all entries in the input tabel (which are about (1-1/e)*k).

Now a real implementation might use hash chains instead, whereas the average time for finding a collision, or the average length of a chain, would be 1/e lower than expected.

> What does the parenthical remark mean?

So far we don't know if an approach as stated above could be implemented in general without exponential effort, but the problem is that its possibility doesn't violate the hash's cryptographic properties.
.

Relevant Pages
Quantcast