Content deleted Content added
Line 40:
=== Downsides of Provable Approach ===
* Current collision-resistant hash algorithms that have provable security [[Reduction (complexity)|reductions]] are too inefficient to be used in practice. In comparison to classical hash functions, they tend to be relatively slow and do not always meet all of criteria traditionally expected of cryptographic hashes. [[Very smooth hash]] is an example.
* The proof is often a reduction to a problem with asymptotically hard [[Worst-case complexity|words-case]] or [[Average-case complexity|average-case]] complexity. Worst-case measures the difficulty of solving pathological cases rather than typical cases of the underlying problem. Even a reduction to a problem with hard average complexity offers only limited security as there still can be an algorithm that easily solves the problem for a subset of the problem space. For example, early versions of [[Fast Syndrome Based hash]]
* Constructing a hash function with provable security is much more difficult than using a classical approach where we just hope that the complex mixing of bits in the hashing algorithm is strong enough to prevent adversary from finding collisions.
| |||