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 collisionresistant 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)$ messagebits (as opposed to $O(\log S)$ messagebits 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 1024bit RSA modulus, runs at 1.1 MegaByte per second, with a moderate slowdown to 0.7MB/s for 2048bit 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 CramerShoup) and designatedverifier 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 CramerShoup signature variant. Version 3.51 shows a discretelog variant of VSH. Version 3.31 shows how to create a randomised trapdoor hash function based upon VSH with application to speeding up CramerShoup 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.
Metadata
 Available format(s)
 PDF PS
 Publication info
 Published elsewhere. Eurocrypt 2006
 Keywords
 hash functionsprovablepracticalfactoringmodular square rootsvery smooth numbers
 Contact author(s)
 scontini @ ics mq edu au
 History
 20060309: last of 11 revisions
 20050624: received
 See all versions
 Short URL
 https://ia.cr/2005/193
 License

CC BY
BibTeX
@misc{cryptoeprint:2005/193, author = {Scott Contini and Arjen K. Lenstra and Ron Steinfeld}, title = {VSH, an Efficient and Provable Collision Resistant Hash Function}, howpublished = {Cryptology ePrint Archive, Paper 2005/193}, year = {2005}, note = {\url{https://eprint.iacr.org/2005/193}}, url = {https://eprint.iacr.org/2005/193} }