Paper 2005/193

VSH, an Efficient and Provable Collision Resistant Hash Function

Scott Contini, Arjen K. Lenstra, and Ron Steinfeld

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.

Note: VERSION HISTORY: This is the final version of our paper, which makes small but major changes over Version 3.57 (the previous version): The VSH algorithm now put the length at the end (instead of the beginning) and start with initial value x_0 = 1. This simplifies the security proof and removes the use of prime p_{k+1}. Version 3.57 has several sections rewritten from V3.51, and gives a proof of the Cramer-Shoup signature variant. Version 3.51 shows a discrete-log variant of VSH. Version 3.31 shows how to create a randomised trapdoor hash function based upon VSH with application to speeding up Cramer-Shoup signatures. Version 2.2 includes the following differences from Version 1.0: (1) Speedups are given to process O(log n) bits per multiply, (2) Implementation timings are given and compared to SHA1, and (3) Some new theoretical issues are addressed. Note: V2.2 is almost the same as V2.1, except some updated analysis of variation IV.