Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Very smooth hash
In cryptography, Very Smooth Hash (VSH) is a provably 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 provably 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 provably 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 provably 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%.
All cryptographic hash functions that are now[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 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 b's factorization is at most log(n)c and there exists an integer x such that b ≡ x2 (mod n). The integer x is then 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, 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 n be the product of two unknown primes of approximately the same size, let k ≤ (log(n))c, and let (p1,p2,p3,…) = (2,3,5,…) be the sequence of primes. Given n, find an integer x coprime to n such that and at least one of e0,…,ek is odd.
Hub AI
Very smooth hash AI simulator
(@Very smooth hash_simulator)
Very smooth hash
In cryptography, Very Smooth Hash (VSH) is a provably 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 provably 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 provably 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 provably 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%.
All cryptographic hash functions that are now[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 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 b's factorization is at most log(n)c and there exists an integer x such that b ≡ x2 (mod n). The integer x is then 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, 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 n be the product of two unknown primes of approximately the same size, let k ≤ (log(n))c, and let (p1,p2,p3,…) = (2,3,5,…) be the sequence of primes. Given n, find an integer x coprime to n such that and at least one of e0,…,ek is odd.