Security of cryptographic hash functions: Difference between revisions

Revision as of 18:37, 9 January 2019

Revision as of 11:02, 19 August 2019

Line 27:

==Provably secure hash functions==

In this approach, we base the security of hash function on some hard mathematical problem and we prove that finding collisions of the hash functions is as hard as breaking the underlying problem. This gives mucha somewhat stronger notion of security than just relying on complex mixing of bits as in the classical approach.

A cryptographic hash function has '''provable security against collision attacks''' if finding collisions is provably [[Polynomial-time reduction|polynomial-time reducible]] from problem P which is supposed to be unsolvable in polynomial time. The function is then called provably secure, or just provable.

It means that if finding collisions would be feasible in polynomial time by algorithm A, we could find and use polynomial time algorithm R (reduction algorithm) that would use algorithm A to solve problem P, which is widely supposed to be unsolvable in polynomial time. That is a contradiction. This means, that finding collisions cannot be easier than solving P.

However, this only indicates that finding collisions is difficult in 'some' cases, as not all instances of a computationally hard problem are typically hard. Indeed, very large instances of NP-hard problems are routinely solved, while only the hardest are practically impossible to solve.

Hash functions with the proof of their security are based on mathematical functions.