4 ms·
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 g
by Xk 15y ago
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.
- StavrosK 15y agoHmm, 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.