[betterunix]

Cryptographic hashes are an entire category of hash functions unto themselves. The absolute minimum guarantee that a cryptographic hash makes is that for any polynomial time algorithm, the probability of the algorithm computing a pair (x,y) such that x != y and H(x) = H(y) is "negligible" i.e. is smaller than 1/p(n) for all polynomials p and large enough n; in other words, cryptographic hashes guarantee that collisions are extremely rare. Much like you can create a cipher with security that is reducible to the hardness of some problem (e.g. ElGamal is secure if the Diffie-Hellman problem is hard), it is possible to create collision resistant hashes with such security proofs, e.g. Very Smooth Hash, SWIFFT. In practice, though, we just use hashes that are believed to be security according to heuristic tests; hence the need to periodically update standard hash functions, rather than to just increase parameter sizes.

Also interesting is universal hashing, which has applicability in cryptography (for randomness extraction, among other things):

https://en.wikipedia.org/wiki/Universal_hashing