VSH, an Efficient and Provable Collision-Resistant Hash Function

We introduce VSH,

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

.

VSH is theoretically pleasing because it requires just a single multiplication modulo the

S

-bit composite per Ω(

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.