the complex mixing of bits in the hashing algorithm is strong enough to prevent adversary from finding collisions. The proof is often a reduction to a problem with asymptotically hard 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. Example of (impractical) Provably Secure Hash Function Hash(m) = xm mod n where n is hard to factor composite number, and x is some prespecified base value. A collision xm1 congruent to xm2 reveals a multiple m1 - m2 of the order of x. Such information can be used to factor n in polynomial time assuming certain properties of x. But the algorithm is quite inefficient because it requires on average 1.5 multiplications modulo n per message-bit. More practical provably secure hash functions VSH - Very Smooth Hash function - a provably secure collision-resistant hash function assuming the hardness of finding nontrivial modular square roots modulo composite number (this is proven to be as hard as factoring ). MuHASH ECOH - Elliptic Curve Only hash function - based on the concept of Elliptic curves, Subset Sum Problem and summation of polynomials. The security proof of the collision resistance was based on weakened assumptions and eventually a second pre-image attack was found. 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. SWIFFT - SWIFFT is based on the Fast Fourier transform and is provably collision resistant, under a relatively mild assumption about the worst-case difficulty of finding short vectors in cyclic/ideal lattices. Chaum, van Heijst, Pfitzmann hash function - A compression function where finding collisions is as hard