In [[cryptography]], [[cryptographic hash functions]] can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problemproblems, and thus theirwhose security thus follows from rigorous mathematical proofs, [[Computational complexity theory|complexity theory]] and [[Reduction (complexity)|formal reduction]]. These functions are called Provably Secure Cryptographic Hash Functions. However this does not mean that such a function could not be broken. To construct themthese is very difficult, and only a few examples werehave been introduced. TheTheir practical use is limited.
In the second category are functions thatwhich are not based on mathematical problems, but on an ad-hoc basisconstructions, wherein which the bits of the message are mixed to produce the hash. TheyThese are then believed to be hard to break, but no such formal proof is given. Almost all widely spread hash functions fallin widespread use reside in this category. Some of these functions are already broken, and are no longer in use.
