Suppose U={0,1}^n. Then we can _project_ h(x) onto some smaller # of bits to compute a smaller hash function. But as we project further & further, the probabilities become more & more suspect, because the expected deviations aren't there. At 11:47 AM 2/25/2014, Cordwell, William R wrote:
Detect by means other than having enough values so that not having a collision is suspect?
-----Original Message----- From: math-fun-bounces+cordwell=sandia.gov@mailman.xmission.com [mailto:math-fun-bounces+cordwell=sandia.gov@mailman.xmission.com] On Behalf Of Henry Baker Sent: Tuesday, February 25, 2014 12:17 PM To: math-fun@mailman.xmission.com Subject: [EXTERNAL] [math-fun] Stupid question about hash functions
Suppose we have a hash function h(x)=y, x,y in universe U, n=|U|.
(We have a simplified situation in which the domain = range.)
"Collisions" in hash functions are really bad, due to the Birthday Paradox, so we want h to be 1-1, which in this case means a permutation of U.
But permutations are a vanishingly small % of all the functions from U -> U; i.e., n! << n^n
n!/n^n ~ sqrt(2 pi n)/exp(n)
Shouldn't it get easier & easier to detect a non-random function from U -> U as n increases?
Shouldn't this lack of randomness be exploitable?