Very smooth hash
Very Smooth Hash (VSH) is a secure cryptographic hash function invented in 2005 by Scott Contini, Arjen Lenstra and Ron Steinfeld. means that finding collisions is as difficult as some known hard mathematical problem. Unlike other secure hashes, VSH is efficient and usable in practice. , it only requires a single multiplication per log(n) message-bits and uses RSA-type arithmetic. Therefore, VSH can be useful in embedded environments where code space is limited.
Two major variants of VSH were proposed. For one, finding a is as difficult as finding a nontrivial modular square root of a very smooth number modulo n. The other one uses a prime modulus p (with no ), and its security proof relies on the hardness of finding discrete logarithms of very smooth numbers modulo p. Both versions have similar efficiency.
VSH is not suitable as a substitute for a random oracle, but can be used to build a secure randomized trapdoor hash function. This function can replace the used in the , maintaining its provable security while speeding up verification time by about 50%.
VSN and VSSR
All cryptographic hash functions that are now widely used are not based on hard mathematical problems. Those few functions that are constructed on hard mathematical problems are called . is then known to be as hard as solving the hard mathematical problem. For the basic version of Very Smooth Hash function, this hard problem is to find modular square roots (VSSR) of certain special numbers (VSN).
The complexity of this attack against VSH is:
- Pre-computing the table offline:
time and space. - Finding collisions: iterations.
- Total cost: roughly , rather than
as expected from a hash function with good pseudorandomness properties.
This probably rules out the applicability of VSH in digital signature schemes which produce signatures shorter than the VSH hash result, such as elliptic-curve signature schemes.