[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?
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? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
True, but as I mentioned, I was considering a worst case; some other cases are produced by various projections, which are indeed many-to-one. At 07:09 AM 2/26/2014, Marc LeBrun wrote:
="Henry Baker" <hbaker1@pipeline.com> we want h to be 1-1
Then h is an encryption, not a hash function that take a big set to small.
[sorry if this is redundant with rest of thread, which I can't read now]
--MLB
participants (3)
-
Cordwell, William R -
Henry Baker -
Marc LeBrun