My back of an envelop calculations were a little off (not affecting the conclusions). The right approximation of the collision probability is:
P(n,k) = k^2 / (2n). It gives only about 20% error, when applied to the birthday problem (k=19 instead of 23, and in the case of 100 entries, the 50% chance of a collision is estimated at k=10, instead of the accurate value of 12). When n/k^2 is large (k^2 is small compared to n) the approximation is very good. Also, the 10^-9 chance of a collision among 128-bit blocks occurs at around k = 2^50, not 2^39. Still, they are just back of an envelop calculations, performed in 10 minutes, so there could be more errors. Laszlo > -------- Original Message -------- > Subject: RE: P1619 D4 draft > From: dtufs <[EMAIL PROTECTED]> > Date: Sat, February 25, 2006 8:25 am > To: [email protected] > > --- [EMAIL PROTECTED] wrote: > > > What you are referring to is a weak form of the > > birthday paradox > > I've never heard that birthday paradox had two > "forms". Could you describe the "weak form" in detail > please? > > > > From the strong form, you get back the week > > form (approximately)with simple arithmetic. > > How? > > > > > If you have 50% chance that the crypto breaks on > > your hard disk, it is not a secure system. > > So you are saying that a 10% chance makes a secure > system? Is the difference between 50% and 10% > considerable? A secure system is where the chance is > negligible, i.e., close to zero. Can you see why it is > infeasible to specify the _lower_ bound? (Lower bound > is two blocks.) > > > > How much chance do you want to take? > > Zero. > > > > Accepting 10% risk > > Again, where did this 10% come from? What is it based > on? The birthday bound, 2**(n/2), is commonly used > when assessing security of hash functions or RNGs. > This bound is perfectly substantiated. Collisions in > PRPs and PRFs are statistically not to be expected > sooner than after 2**(n/2) querries. For LRW this > bound is three times lower. Which gives us ~2**63.2 > querries for 128-bit blocks. This is the _upper_ > bound, yes. So going close to it is not recommended. > But this is substantiated. 10% is not based on > anything. You can get a collision after just two > querries. The _lower_ bound for PRPs is q=2. > > If you want to use 10% bound, then back it up by > something. I don't know how I would explain this limit > to my customers. It appears to be just made up (a nice > round figure). Can anyone see the problem? > > Regards, > Ian Malik > > > __________________________________________________ > Do You Yahoo!? > Tired of spam? Yahoo! Mail has the best spam protection around > http://mail.yahoo.com
