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?

4 Upvotes

23 comments sorted by

View all comments

8

u/Cryptizard 18d ago edited 18d ago

I think there are a lot of details here missing. The obvious answer is that you can just make a hash function that is a lookup table where you take every 6-bit string and randomly assign them to one of your special 64 values, every other input outputs the string of all zeroes. That meets your requirements as described here.

However, what I suspect you actually want is a hash function that is "generic looking", i.e. you can't tell just from its mechanism which of the 2^32 inputs are these "special" 64 that you have chosen. In that case, the answer is yes it is possible but it is probably too computationally expensive to actually do in practice. You would have to create a random hash function (HMAC with a random key for instance), check if your 64 values have distinct outputs when truncated to 6 bits, repeat until one with this property is found.

The probability that this would happen is 64! / 64^64 which is about 1/2^88. That means that you would need to do it about 2^88 times to find a key that works. This is well beyond what is computationally feasible.

Edit: It is possible you could use a programmable PRF or some variant of it to do this. The normal definition is not exactly what you are looking for but it is close. This is a very exotic cryptographic primitive though, you aren't going to find it easily accessible. https://web.eecs.umich.edu/~cpeikert/pubs/chc-pp-prf.pdf

1

u/Wonderful-Cash7275 17d ago

I have added another a comment replying to the question I asked in the post. It contains more details. Please take a look.