Paper 2005/193 Original: eprint.iacr.org/2005/193 ↗

VSH, an Efficient and Provable Collision Resistant Hash Function

Abstract

We introduce VSH, {\em very smooth hash}, a new $S$-bit hash function that is provably collision-resistant assuming the hardness of finding nontrivial modular square roots of very smooth numbers modulo an $S$-bit composite. By very smooth, we mean that the smoothness bound is some fixed polynomial function of~$S$. We argue that finding collisions for VSH has the same asymptotic complexity as factoring using the Number Field Sieve factoring algorithm, i.e., subexponential in~$S$. %We show how our asymptotic argument can be turned into a practical method to %select parameters so that VSH meets a desired security level. VSH is theoretically pleasing because it requires just a single multiplication modulo the~$S$-bit composite per $\Omega(S)$ message-bits (as opposed to $O(\log S)$ message-bits for previous provably secure hashes). It is relatively practical. A preliminary implementation on a 1GHz Pentium III processor that achieves collision resistance at least equivalent to the difficulty of factoring a 1024-bit RSA modulus, runs at 1.1 MegaByte per second, with a moderate slowdown to 0.7MB/s for 2048-bit RSA security. VSH can be used to build a fast, provably secure randomised trapdoor hash function, which can be applied to speed up provably secure signature schemes (such as Cramer-Shoup) and designated-verifier signatures.