Very smooth hash


In cryptography, Very Smooth Hash is a secure cryptographic hash function invented in 2005 by Scott Contini, Arjen Lenstra and Ron Steinfeld.
Provably secure means that finding collisions is as difficult as some known hard mathematical problem. Unlike other secure collision-resistant hashes, VSH is efficient and usable in practice. Asymptotically, it only requires a single multiplication per log 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 collision 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, 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 trapdoor function used in the Cramer–Shoup signature scheme, 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 provably secure. Finding collisions 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 of certain special numbers. This is assumed to be as hard as factoring integers.
For a fixed constant c and n an integer m is a Very Smooth Number if the largest prime factor of m is at most c.
An integer b is a Very Smooth Quadratic Residue modulo n if the largest prime in bs factorization is at most c and there exists an integer x such that. The integer x is said to be a Modular Square Root of b.
We are interested only in non-trivial square roots, those where x2 ≥ n. If x2 < n, the root can be easily computed using algorithms from fields of characteristics 0, such as real field. Therefore, they are not suitable in cryptographic primitives.
Very Smooth Number Nontrivial Modular Square Root is the following problem: Let n be the product of two unknown primes of approximately the same size and let. Let be the sequence of primes. VSSR is the following problem: Given n, find such that and at least one of e0,...,ek is odd.
The VSSR assumption is that there is no probabilistic polynomial time algorithm which solves VSSR with non-negligible probability. This is considered a useless assumption for practice because it does not tell for what size of moduli VSSR is computationally hard. Instead The computational VSSR assumption' is used. It says that solving VSSR is assumed to be as hard as factoring a hard-to-factor bit modulus, where is somewhat smaller than the size of.

Examples of VSN and VSSR

Let the parameters be fixed as follows: and.
Then is a Very Smooth Number with respect to these parameters because is greater than all 's prime factors. On the other hand, is not a VSN under and.
The integer is Very Smooth Quadratic Residue modulo because it is Very Smooth Number and we have such that . This is a trivial modular square root, because and so the modulus is not involved when squaring.
The integer is also Very Smooth Quadratic Residue modulo. All prime factors are smaller than 7.37 and the Modular Square Root is since . This is thus a non-trivial root. The VSSR problem is to find given and. And we suppose that this is computationally as hard as factoring.

VSH algorithm, basic versions

Let be a large RSA composite and let the sequence of primes. Let, the block length, be the largest integer such that. Let be an -bit message to be hashed consisting of bits and assume that. To compute the hash of :
  1. x0 = 1
  2. Let, the smallest integer greater or equal to, be the number of blocks. Let for
  3. Let with be the binary representation of the message length and define for.
  4. for j = 0, 1,..., L in succession compute
  5. return xL + 1.
The function in step 4 is called the compression function.

Properties of VSH

Several improvements, speedups and more efficient variants of VSH have been proposed. None of them changes the underlying concept of the function. These improvements are called:
The VSH-DL is a discrete logarithm variant of VSH that has no trapdoor, its security depends on the difficulty of finding discrete logarithm modulo a prime p.
Very Smooth Number Discrete Logarithm is a problem where given a very smooth number, we want to find its discrete logarithm modulo some number n.
Similarly as in previous section, by we denote the -th prime. Let furthermore be a fixed constant and, be primes with and let. VSDL is the following problem: given, find integers such that with for and at least one of non-zero.
The VSDL assumption is that there is no probabilistic polynomial time algorithm which solves VSDL with non-negligible probability. There is a strong connection between the hardness of VSDL and the hardness of computing discrete logarithm modulo, which is reminiscent of, but somewhat weaker than, the connection between VSSR and integer factorization.

Security of VSH

Strong collision resistance is the only property proven for VSH. This does not imply preimage-resistance or other
important hash function properties, and the authors state that "VSH should not be used to model random oracles," and cannot be substituted into constructions that depend upon them. VSH should not be considered a general-purpose hash function as usually understood in security engineering.

Multiplicative property

VSH is multiplicative: Let x, y, and z be three bit strings of equal length, where z
consists only of zero bits and the strings satisfy x AND y = z. It is easy to see that
HH ≡ HH . As a result, VSH succumbs to a classical time-memory
trade-off attack that applies to multiplicative and additive hashes.
This fact can be used to construct a preimage attack against VSH of bits which has complexity rather than as expected.

Attack against truncated version

VSH produces a very long hash. There are no indications that
a truncated VSH hash offers security that is commensurate with the hash length.
There exists a partial collision attack on VSH truncated to least significant l bits.
The complexity of this attack against VSH is:
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.