**VSH, an Efficient and Provable Collision Resistant Hash Function**

*Scott Contini and 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.

**Category / Keywords: **hash functions, provable, practical, factoring, modular square roots, very smooth numbers

**Publication Info: **Eurocrypt 2006

**Date: **received 23 Jun 2005, last revised 8 Mar 2006

**Contact author: **scontini at ics mq edu au

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**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.

**Version: **20060309:035411 (All versions of this report)

**Short URL: **ia.cr/2005/193

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]