CryptoDB
VSH, an Efficient and Provable Collision Resistant Hash Function
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2005-12529,
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},
url={http://eprint.iacr.org/2005/193},
note={Eurocrypt 2006 scontini@ics.mq.edu.au 13216 received 23 Jun 2005, last revised 8 Mar 2006},
author={Scott Contini and Arjen K. Lenstra and Ron Steinfeld},
year=2005
}