Content deleted Content added
→The meaning of "hard": the "difficulty" of a problem depends on its size - give a practical example |
|||
Line 46:
* The proof is often a reduction to a problem with asymptotically hard [[Worst-case complexity|worst-case]] or [[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]] turned out to be insecure. This problem was solved in the latest version.
[[SWIFFT]] is an example of a hash function that circumvents these security problems. It can be shown that for any algorithm that can break SWIFFT with probability P within an estimated time T, we can find an algorithm that solves the ''worst-case'' scenario of a certain difficult mathematical problem within time T' depending on T and P.{{citation needed|date=June 2014}}
===Example of (unpractical) Provably Secure Hash Function===
| |||