Re:The FBI stole an Instapaper server in an unrelated raid
by Xk on Thursday June 23, 2011 @03:05PM
(#2689343)
Point taken, it's probably true that the probability that G(F(P)) == G(F(Q)) given F(P) != F(Q) is less than 1 in 2^128. But it's probably also true that it's greater than 0.
Clearly it's impossible to be less than zero. So no matter what you do, Defining H(X) to be G(F(X)) will have strictly more collisions than F(X).
The reason I would argue it's greater than zero is that if a function H existed such that H(X) will never collide for X less than 2^128, it would probably have some cryptographic weakness.
Re:The FBI stole an Instapaper server in an unrelated raid
by StavrosK on Thursday June 23, 2011 @03:09PM
(#2689353)
Hmm, you're right indeed, since they're additive. I should have said that the second layer is less likely to collide than the first, not than both combined.
Clearly it's impossible to be less than zero. So no matter what you do, Defining H(X) to be G(F(X)) will have strictly more collisions than F(X).
The reason I would argue it's greater than zero is that if a function H existed such that H(X) will never collide for X less than 2^128, it would probably have some cryptographic weakness.