Content deleted Content added
No edit summary |
Downsides of Provable Approach, More practical Provably Secure Hash Functions |
||
Line 32:
=== Hard problems ===
Examples of problems, that are assumed to be
* [[Discrete logarithm|
* [[Quadratic residue|
* [[Integer factorization|
* [[
=== Downsides of Provable Approach ===
* Current collision-resistant hash algorithms that have provable security reductions are too inefficient to be used in practice. In comparision to clasical 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. [[Fast Syndrome-Based hash function]] is an example.
* Constructing a hash function with provable security is much more difficult than using a intuitive approach where we just hope that the complexity of hashing algorithm is high enough to prevent adversary from finding collisions.
=== Example of (unpractical) Provably Secure Hash Function ===
Line 51 ⟶ 52:
* [[Elliptic Curve Only hash function|ECOH - Elliptic Curve Only hash function]]
* [[Fast Syndrome-Based hash function|FSB - Fast Syndrome-Based hash function]] - it can be proven that breaking FSB is at least as difficult as solving a certain NP-complete problem known as Regular Syndrome Decoding.
* [[
* [[Chaum, van Heijst, Pfitzmann hash function]] - A compression function where finding collisions is as hard as finding a [[discrete logarithm|discrete logarithm problem]] in a finite group <math>F_{2p+1}</math>.
* [[Knapsack-based hash functions]] - A family of hash functions based on the [[Knapsack problem]].
* [[The Zémor-Tillich hash function]] - A family of hash functions that rely on the arithmetic of the group of matrices [[Special linear group|SL2]]. Finding collisions is at least as difficult as finding factorization of certain elements in this group. This is supposed to be hard, at least [[PSPACE-complete]].
| |||