Very smooth hash

Template:Short description Template:Infobox cryptographic hash function In cryptography, Very Smooth Hash (VSH) is a Template:Not a typo 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 Template:Not a typo secure collision-resistant hashes, VSH is efficient and usable in practice. Asymptotically, it only requires a single multiplication per Template:Math 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 Template:Not a typo as difficult as finding a nontrivial modular square root of a very smooth number modulo Template:Mvar. The other one uses a prime modulus Template:Mvar (with no trapdoor), and its security proof relies on the hardness of finding discrete logarithms of very smooth numbers modulo Template:Mvar. Both versions have similar efficiency.

VSH is not suitable as a substitute for a random oracle, but can be used to build a Template:Not a typo 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 nowTemplate:When 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, this hard problem is to find modular square roots (VSSR) of certain special numbers (VSN). This is assumed to be as hard as factoring integers.

For fixed constants Template:Mvar and Template:Mvar, an integer Template:Mvar is a Very Smooth Number (VSN) if the largest prime factor of Template:Mvar is at most Template:Math.

An integer Template:Mvar is a Very Smooth Quadratic Residue modulo Template:Mvar if the largest prime in Template:Mvar's factorization is at most Template:Math and there exists an integer Template:Mvar such that Template:Math. The integer Template:Mvar is then said to be a modular square root of Template:Mvar.

We are interested only in non-trivial square roots, those where Template:Math. If Template:Math, then the root can be easily computed using algorithms from fields of characteristic 0, such as the real field. Therefore, they are not suitable in cryptographic primitives.

Very Smooth Number Nontrivial Modular Square Root (VSSR) is the following problem: Let Template:Mvar be the product of two unknown primes of approximately the same size, let Template:Math, and let Template:Math be the sequence of primes. Given Template:Mvar, find an integer Template:Mvar coprime to Template:Mvar such that $x^2\equiv {\prod }_{i=0}^k{p}_i^{e_i}(\mathrm{mod}n)$ and at least one of Template:Math is odd.

The VSSR assumption is that there is no probabilistic polynomial (in Template:Math) time algorithm which solves VSSR with non-negligible probability. This is considered a useless assumption in 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 Template:Mvar-bit modulus, where Template:Mvar is somewhat smaller than the size of Template:Mvar.

Examples of VSN and VSSR

Let the parameters be fixed as Template:Math and Template:Math.

Then Template:Math is a Very Smooth Number with respect to these parameters because Template:Math is greater than all of Template:Math's prime factors. On the other hand, Template:Math is not a VSN under these parameters.

The integer Template:Math is a Very Smooth Quadratic Residue modulo Template:Mvar because it is a Very Smooth Number (under Template:Math), and Template:Math. This is a trivial modular square root, because Template:Math and so the modulus is not involved when squaring.

The integer $b_2=15$ is also Very Smooth Quadratic Residue modulo $n$. All prime factors are smaller than 7.37 and the Modular Square Root is $x_2=20$ since $20^2=400\equiv 15$ (mod $n$). This is thus a non-trivial root. The VSSR problem is to find $x_2$ given $b_2$ and $n$. And we suppose that this is computationally as hard as factoring $n$.

The integer Template:Math is also a Very Smooth Quadratic Residue modulo Template:Mvar. All of its prime factors are smaller than 7.37, and the modular square root is Template:Math, since Template:Math. This is thus a non-trivial square root. The VSSR problem is to find Template:Mvar given Template:Mvar and Template:Mvar. This is believed to be computationally as hard as factoring Template:Mvar.

VSH algorithm, basic versions

Let Template:Mvar be a large RSA composite and let Template:Math be the sequence of primes. Let Template:Mvar, the block length, be the largest integer such that ${\prod }_{i=1}^k{p}_i<n$. Let Template:Mvar be an Template:Mvar-bit message to be hashed consisting of bits Template:Math and assume that Template:Math. To compute the hash of Template:Mvar:

1. Set Template:Math.
2. Let Template:Mvar, the smallest integer greater than or equal to Template:Math, be the number of blocks.
3. Let Template:Math for Template:Math (padding).
4. Let $\ell ={\sum }_{i=1}^k{l}_i{2}^{i-1}$ with Template:Math be the binary representation of the message length Template:Mvar and define Template:Math for Template:Math.
5. For Template:Math in succession, compute $x_{j+1}=x_j^2\prod _{i=1}^k{p}_i^{m_{jk+i}}modn$
6. Return Template:Math.

The function in step 5 is called the compression function.

Properties of VSH

• The message length does not need to be known in advance.
• Finding a collision in VSH is as hard as solving VSSR. Thus VSH is (strongly) collision-resistant, which also implies second preimage resistance. VSH has not been proven to be preimage-resistant.
• The compression function is not collision-resistant. Nonetheless, the hash function VSH is collision-resistant based on the VSSR assumption. An altered version of VSH, called VSH*, uses a collision-resistant compression function and is about 5 times quicker when hashing short messages.
• Since the output length of VSH is the length of a secure RSA modulus, VSH seems quite suitable in practice for constructing "hash-then-sign" RSA signatures for arbitrarily long messages. However, such a signature must be designed carefully to ensure its security. The naïve approach could be easily broken under a chosen-plaintext attack.
• The cost of each iteration is less than the cost of 3 modular multiplications. The basic version of VSH altogether requires one multiplication per Template:Math message bits.

Variants 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:

• Cubing VSH (instead of squaring)
• VSH with increased number of small primes
• VSH with precomputed products of primes
• Fast VSH
• Fast VSH with increased block length

VSDL and VSH-DL variant

The VSH-DL is a discrete logarithm variant of VSH that has no trapdoor; its security depends on the difficulty of finding discrete logarithms modulo a prime Template:Mvar.

Very Smooth Number Discrete Logarithm (VSDL) is a problem where, given a very smooth number, the task is to find its discrete logarithm modulo some number Template:Mvar.

As in previous section, Template:Math denotes the Template:Mvarth prime. Let furthermore Template:Mvar be a fixed constant and Template:Math be primes with Template:Math and let Template:Math. VSDL is the following problem: given Template:Mvar, find integers Template:Math such that $2^{e_1}\equiv \prod _{i=2}^k{p}_i^{e_i}(\mathrm{mod}p)$ with Template:Math for Template:Math and at least one of Template:Math is non-zero.

The VSDL assumption is that there is no probabilistic polynomial (in Template:Math) 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 logarithms modulo Template:Mvar, 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 (RSA signatures, some MACs). VSH should not be considered a general-purpose hash function as usually understood in security engineering.

Multiplicative property

VSH is multiplicative: Let Template:Mvar, Template:Mvar, and Template:Mvar be three bitstrings of equal length, where Template:Mvar consists only of zero bits and the strings satisfy Template:Math. Then Template:Math. 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 Template:Mvar bits which has Template:Math complexity rather than Template:Math as expected.

Attack against truncated version

VSH produces a very long hash (typically 1024 bits). 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 Template:Mvar least significant bits.

The complexity of this attack against VSH is:

• Pre-computing the table offline: Template:Math time and space.
• Finding collisions: Template:Math iterations.
• Total cost: roughly Template:Math, rather than Template:Math as expected from a hash function with good pseudorandomness properties.

This probablyTemplate:According to whom 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.

See also

• Cryptographic hash functions
• Provably secure cryptographic hash function