Difference between revisions of "VSH"

From The ECRYPT Hash Function Website
 
Line 5: Line 5:
 
* max. message length: < 2<sup>64</sup> bits
 
* max. message length: < 2<sup>64</sup> bits
 
* compression function: 512-bit message block, 160-bit chaining variable
 
* compression function: 512-bit message block, 160-bit chaining variable
* Specification:
 
 
-->
 
-->
 +
* Specification: http://csrc.nist.gov/groups/ST/hash/documents/LENSTRA_vsh.pdf
 +
 +
<bibtex>
 +
@MISC{nistContiniLS05,
 +
  author = {Scott Contini and Arjen Lenstra and Ron Steinfeld},
 +
  title = {VSH, an Efficient and Provable Collision Resistant Hash Function},
 +
  howpublished = {NIST - First Cryptographic Hash Workshop, October 31-November 1},
 +
  year = {2005},
 +
  abstract = {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 integer $n$. 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 only $O(\frac{1}{S})$ multiplications modulo the $S$-bit composite $n$ per message-bit (as opposed to $\Omega(\frac{1}{\mbox{log}S})$ multiplications for previous provably secure hashes). It is also practical. A preliminary implementation on a 1GHz Pentium III processor that achieves collision resistance at least equivalent to the diffculty 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.},
 +
  url = {http://csrc.nist.gov/groups/ST/hash/documents/LENSTRA_vsh.pdf},
 +
}
 +
</bibtex>
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==

Revision as of 15:43, 10 March 2008