Welcome to the resource topic for 2005/193
Title:
VSH, an Efficient and Provable Collision Resistant Hash Function
Authors: Scott Contini, Arjen K. Lenstra, 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.
ePrint: https://eprint.iacr.org/2005/193
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .