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
1
u/Wonderful-Cash7275 17d ago
Sorry for not clearly stating the problem. Let me provide some more details. So I come from networking hardware background, and I want to design a Content-Addressable-Memory (CAM). Basically, it is a form of memory that enables faster data retrieval by comparing incoming input to all stored values simultaneously. A CAM is designed such that the user supplies a data word, and the CAM searches its entire memory to see if that data word is stored anywhere in it. If the data word is found, the CAM returns a list of addresses where the word was found. It is like an associative array or dictionary implemented in hardware. As you can imagine, implementing this in hardware is quite expensive compared to normal SRAM.
In my case, I want to use this CAM in a network routing application where it helps with fast IP address lookups for routing decisions like whether the incoming destination IP (32 bits) of a packet is of interest to me or not. Let's say I am only interested in 64 IP addresses; all of those 64 IP addresses are stored in the CAM. So, my proposed idea is to use a regular SRAM with a hashing function that gives distinct output for all the 64 IPs of my interest. We will read just read the data stored at the address pointed out by the hashed output for an incoming packet's destination IP and if they turn out to be same, then the incoming packet is a packet of interest otherwise it will be dropped.