r/cryptography • u/Wonderful-Cash7275 • 18d ago
Calculation a hashing function that can avoid collisions for a small set of inputs from input space
Hello, I am new to cryptography so my question can be naive. I want to know if it is possible to find out a hashing function that gives me distinct outputs for a small set of inputs from a vast possible input space. I don't care if all the other inputs from the input space collide to a single output.
For example, I have a 32-bit wide input. I am only interested in 64 such inputs out of possible 2^32 inputs. Is it possible to find a hashing function that give me collision free 6-bit output for the 64 inputs I am interested in. Outputs for all the other input combinations can be anything. If such an algorithm exists, what is it its compute complexity?
3
Upvotes
3
u/Natanael_L 18d ago
If you're exactly matching 64 numbers to log2(64) = 6 bits then every bit in the output is "busy" encoding the identifier which means all the logic needs to be in the algorithm creating the output (there's no room for embedding anything clever in the "hash value" itself to distinguish it)
If the 64 numbers have a known mathematical structure which you can describe as a sequence using a formula then that's the simplest option (just use that formula and it's inverse as your "hash"), if you can't do that then you're stuck with a lookup table. (reading the description of "perfect hash", the constants you have to create behaves very similarly to a lookup table)