VSH, An Efficient and Provable Collision Resistant Hash Function

We introduce VSH, very smooth hash, a new hash function for which finding collisions is provably reducible to finding nontrivial modular square roots of very smooth numbers modulo a composite integer n. By very smooth, we mean that the smoothness bound is some fixed polynomial function of the bitlength N of n. We show that if collisions for VSH can, asymptotically, be found faster than factoring n using the Number Field Sieve factoring algorithm (NFS), then n can be factored faster than by means of the NFS. Furthermore, we show how our asymptotic argument can be turned into a practical method to select n so that VSH meets a desired security level. Our hardness assumption - and thereby the collision resistance of VSH - is thus linked to the current state of the art of integer factorization.