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.

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
2006-03-09: last of 11 revisions
2005-06-24: received
See all versions
Short URL
https://ia.cr/2005/193
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.