I have a situation in which I need to combine a 32-bit datum,
G, and a 64-bit datum,
I, to produce a 64-bit datum. No two tuples with the same
I value will have the same
G value, and vice versa. Collision resistance must be very high (data corruption will result if not).
Technically, I don't need encryption, but most decently collision-resistant hash functions happen to come from the field. Some questions:
I have considered using a cryptographic hash such as SHA-256 and either slicing (i.e., subset of bits) or folding (XOR'ing subsets of bits).
Question 1: is this a reasonable approach (i.e., can anyone recommend something simpler with comparable collision resistance)?
Question 2: slice or fold? Folding might help with issues of non-uniform distribution in the subsets, but does it weaken the result? I think not, but I am not certain…
To the responders… Thank You!
@ChaosInCodes: right – collisions are very problematic, maybe fatal. This is why I am also soliciting any other ideas about how to do this (i.e., without the use of cryptographic hashes). The
I datum, in particular is sparse (being a composition of a bunch of other, smaller data, including a little slice of
G). I am continuing to work on whether I can recompose
(G,I) pairs as a 64-bit datum without using hashes… Pointers to information on the probability of collisions (given uniformly distributed, random inputs - which I don't really have), that would be helpful.
@poncho: I mean unlikely.
@RichieFrame: thanks, I'll check into these. As mentioned, I really don't need a cryptographic checksum, just a very good hashing technique.
@fgrieu: OK, the problem I am trying to solve is to represent a filesystem's inode's generation and inode number as a unique 64-bit datum. The values of I are not unique (by which I mean that at any point in time, an inode points to unique data, but the file system reuses inodes over time); the values of
G are also not unique (by which I mean that there are many inodes deployed during a given generation). The pair
(G,I) is guaranteed to be unique, but its too big!
I expect ~billion pairs, and this approach is only workable if the probability of collision is sufficiently low that I will likely retire before the first one occurs. ;-}
The tone of these responses lead me to believe that perhaps a cryptographic hash is insufficient to the need, i.e., may have too high a probability of collision given the input data. I have some background in data de-duplication, so my head went there, but perhaps it isn't the right approach.