International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: VSH, an Efficient and Provable Collision Resistant Hash Function

Scott Contini
Arjen K. Lenstra
Ron Steinfeld
Search ePrint
Search Google
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.
  title={VSH, an Efficient and Provable Collision Resistant Hash Function},
  booktitle={IACR Eprint archive},
  keywords={hash functions, provable, practical, factoring, modular square roots, very smooth numbers},
  note={Eurocrypt 2006 13216 received 23 Jun 2005, last revised 8 Mar 2006},
  author={Scott Contini and Arjen K. Lenstra and Ron Steinfeld},