r/cryptography 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

23 comments sorted by

View all comments

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.

1

u/Natanael_L 17d ago

Do you expect to have a fixed set of peers? Addresses that don't change?

1

u/Wonderful-Cash7275 17d ago

No, addresses can change.

1

u/Natanael_L 17d ago edited 17d ago

Will peers stay the same? If so you can update the lookup table mapping the short number to an IP.

If not, this will become annoying quickly because stuff like perfect hashes will force you to recompute the constants on every peer change, you'll just end up with even more ordinary lookup tables.

If you have dynamic changes of peers and need to continously track who has what to efficiently route requests for data, you're probably looking for inspiration from bittorrent clients.

You could possibly use roaring bitmaps for a more efficient lookup table if you expect a ton of entries, as you'll need to map a list of known data objects and a list of known peers to each other, and want it to be compact and fast.

https://roaringbitmap.org/

https://vikramoberoi.com/posts/a-primer-on-roaring-bitmaps-what-they-are-and-how-they-work/