How to quickly determine if two sets of checksums are equal, with the same
"strength" as the individual checksums
Say you have two unordered sets of checksums, one of size N and one of
size M. Depending on the algorithm to compare them, you may not even know
the sizes but can compare N != M for a quick abort if you do.
The hashing function used for a checksum has some chance of collision,
which as a layman I'm foolishly referring to as "strength". Is there a way
to take two sets of checksums, all made from the same hashing function,
and quickly compare them (so comparing element to element is right out)
with the same basic chance of collision between two sets as there is
between two individual checksums?
For instance, one method would be to compute a "set checksum" by XORing
all of the checksums in the set. This new single hash is used for
comparing with other sets' hashes, meaning storage of size is no longer
necessary. Especially since it can be modified for the addition/removal of
an element checksum by XORing with the set's checksum without having to
recompute the whole thing. But does that reduce the "strength" of the
set's checksum compared to a brute force comparison of all the original
ones? Is there a way to conglomerate the checksums of a set that doesn't
reduce the "strength" (as much?) but still is less complex than a straight
comparison of the set elements' checksums?
No comments:
Post a Comment