VSH, an efficient and provable collision-resistant hash function

Scott Contini*, Arjen K. Lenstra, Ron Steinfeld

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

74 Citations (Scopus)


We introduce VSH, 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. VSH is theoretically pleasing because it requires just a single multiplication modulo the S-bit composite per ω(5) 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 USA 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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - EUROCRYPT 2006
EditorsSerge Vaudenay
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Number of pages18
ISBN (Print)3540345469, 9783540345466
Publication statusPublished - 2006
Event24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2006 - St. Petersburg, Russian Federation
Duration: 28 May 20061 Jun 2006

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2006
Country/TerritoryRussian Federation
CitySt. Petersburg


  • hashing
  • provable reducibility
  • integer factoring


Dive into the research topics of 'VSH, an efficient and provable collision-resistant hash function'. Together they form a unique fingerprint.

Cite this