jkr
05-05-2004, 06:00 PM
Hi,
Is there a simple explanation of the statement taken from the proposal at http://www.certainkey.com/dnet:
"The first collision is expected to occur after 2^64 hash's. The next trillion collisions are expected to happen
shortly after!!! "
I can believe the mean number of hashes required to reach the first collision is roughly the square root of total number of possible hash values, which gives the 2^64. But having got 2^64 hashes, the probability that the next hash is a collision will be 2^-64, so very crudely you might expect about one more collision in the next 2^64 hashes.
(Well, a bit more than one more because we will have between 2^64 and 2^65 hashes, so perhaps two or three collisions)
Where am I going wrong?
John
Is there a simple explanation of the statement taken from the proposal at http://www.certainkey.com/dnet:
"The first collision is expected to occur after 2^64 hash's. The next trillion collisions are expected to happen
shortly after!!! "
I can believe the mean number of hashes required to reach the first collision is roughly the square root of total number of possible hash values, which gives the 2^64. But having got 2^64 hashes, the probability that the next hash is a collision will be 2^-64, so very crudely you might expect about one more collision in the next 2^64 hashes.
(Well, a bit more than one more because we will have between 2^64 and 2^65 hashes, so perhaps two or three collisions)
Where am I going wrong?
John