Security of cryptographic hash functions: Difference between revisions

Revision as of 01:41, 10 September 2019

Revision as of 00:58, 30 July 2020

Line 32:

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.