Very smooth hash
Encyclopedia
In cryptography
, Very Smooth Hash (VSH) 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(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 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 (with no trapdoor
), 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%.
. Finding collisions
is then known to be as hard as solving the 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). 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 (VSN) if the largest prime factor of m is at most (log n)c.
An integer b is a Very Smooth Quadratic Residue modulo n if the largest prime in bs factorization is at most (log n)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
. 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 (VSSR) 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
(in
) 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 
.
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 (under 
) and we have 
such that 
(mod 
). 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 
(mod 
). 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 
.
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 
:
The function in step 4 is called the compression function.
, its security depends on the difficulty of finding discrete logarithm modulo a prime p.
Very Smooth Number Discrete Logarithm (VSDL) 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 
. CSDL 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
(in
) 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.
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.
consists only of zero bits and the strings satisfy x AND y = z. It is easy to see that
H(z)H(x OR y) ≡ H(x)H(y) (mod n). 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.
a truncated VSH hash offers security that is commensurate to the hash length.
Their exists a Partial Collision Attacks on VSH truncated to least significant l bits.
The complexity of this attack against 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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, Very Smooth Hash (VSH) is a secure cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
invented in 2005 by Scott Contini, Arjen Lenstra and Ron Steinfeld.
Provably secure
Provably secure cryptographic hash function
In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, complexity theory and formal reduction. These...
means that finding collisions is as difficult as some known hard mathematical problem. Unlike other secure collision-resistant
Collision resistance
Collision resistance is a property of cryptographic hash functions: a hash function is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H = H, and a ≠ b.Every hash function with more inputs than outputs will necessarily have...
hashes, VSH is efficient and usable in practice. Asymptotically
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
, 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 collision
Collision resistance
Collision resistance is a property of cryptographic hash functions: a hash function is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H = H, and a ≠ b.Every hash function with more inputs than outputs will necessarily have...
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 trapdoor
Trapdoor function
A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction without special information, called the "trapdoor"...
), 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
Random oracle
In cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...
, but can be used to build a secure randomized trapdoor hash function. This function can replace the trapdoor function
Trapdoor function
A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction without special information, called the "trapdoor"...
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 secureProvably secure cryptographic hash function
In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, complexity theory and formal reduction. These...
. Finding collisions
Collision resistance
Collision resistance is a property of cryptographic hash functions: a hash function is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H = H, and a ≠ b.Every hash function with more inputs than outputs will necessarily have...
is then known to be as hard as solving the 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). This is assumed to be as hard as factoring integers
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
.
For a fixed constant c and n an integer m is a Very Smooth Number (VSN) if the largest prime factor of m is at most (log n)c.
An integer b is a Very Smooth Quadratic Residue modulo n if the largest prime in bs factorization is at most (log n)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
. If x2 < n, the root can be easily computed using algorithms from fields of characteristicsCharacteristic (algebra)
In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...
0, such as real field. Therefore they are not suitable in cryptographic primitives.
Very Smooth Number Nontrivial Modular Square Root (VSSR) 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
PP (complexity)
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...
(in
) 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 factoringInteger factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
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 (under ) and we have such that (mod ). 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 (mod ). 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 :
- x0 = 1
- Let
, the smallest integer greater or equal to 
, be the number of blocks. Let 
for 
(padding) - Let
with 
be the binary representation of the message length 
and define 
for 
. - for j = 0, 1,..., L in succession compute
- return xL + 1.
The function in step 4 is called the compression function.
Properties of VSH
- The message length does not need to be known in advance.
- A most important theorem states that 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 pre-image resistant.
- A curious feature of VSH is that 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*, has the compression function collision resistant and furthermore 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 naive approach could be easily broken under CPA (chosen plaintext attack)Ciphertext indistinguishabilityCiphertext indistinguishability is a property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message they encrypt...
. - EfficiencyAnalysis of algorithmsTo analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
: The cost of each iteration is less than the cost of 3 modular multiplications. The basic version of VSH altogether requires single multiplication per
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 trapdoorTrapdoor function
A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction without special information, called the "trapdoor"...
, its security depends on the difficulty of finding discrete logarithm modulo a prime p.
Very Smooth Number Discrete Logarithm (VSDL) is a problem where given a very smooth number, we want to find its discrete logarithm
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
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 . CSDL 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
PP (complexity)
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...
(in
) 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 resistanceCollision resistance
Collision resistance is a property of cryptographic hash functions: a hash function is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H = H, and a ≠ b.Every hash function with more inputs than outputs will necessarily have...
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
Random oracle
In cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...
,” and cannot be substituted into constructions that depend upon them (RSA signatures, some MACs
Message authentication code
In cryptography, a message authentication code is a short piece of information used to authenticate a message.A MAC algorithm, sometimes called a keyed hash function, accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a MAC...
). 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 zconsists only of zero bits and the strings satisfy x AND y = z. It is easy to see that
H(z)H(x OR y) ≡ H(x)H(y) (mod n). 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 (typically 1024 bits). There are no indications thata truncated VSH hash offers security that is commensurate to the hash length.
Their exists a Partial Collision Attacks on VSH truncated to least significant l bits.
The complexity of this attack against 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.
See also
- Cryptographic hash functions
- Provably secure cryptographic hash functionProvably secure cryptographic hash functionIn cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, complexity theory and formal reduction. These...